趣味编程:函数式链表的快速排序(参考答案)
2009-09-02 10:58 by 老赵, 6289 visits之前我提出了一个“趣味编程”,模仿Haskell的方式对一个链表进行快速排序。在那篇文章中我解释了Haskell列表的结构,并给出了ImmutableList的基础实现。快速排序的例子很多,多做也没有意思。这题虽然打着“快速排序”的旗帜,但事实上这里的关键在于实现ImmutableList数据结构的相关操作——否则为什么叫“函数式链表”的快速排序呢?。
一开始,我提出使用null来表示一个空链表,不过RednaxelaFX指出应该使用Null Object Pattern来表现。因此我修改了文章的代码示例。不过后来RednaxelaFX同学指出,其实我的做法并没有按照他的理解进行。我也认为他的做法更确切一些,因此也对代码进行了修改。于是这次我给出的“参考答案”,便参考了他的部分实现方式。
ImmutableList结构的定义如下:
public abstract class ImmutableList<T> : IEnumerable<T> { public abstract T Head { get; } public abstract ImmutableList<T> Tail { get; } public abstract bool IsEmpty { get; } #region IEnumerable<T> Members public IEnumerator<T> GetEnumerator() { var current = this; while (!current.IsEmpty) { yield return current.Head; current = current.Tail; } } #endregion #region IEnumerable Members IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } #endregion }
与上一篇文章给出的定义不同,ImmutableList<T>被定义为一个抽象类,包含一个ImmutableList的成员抽象与相关方法。ImmutableList抽象类有两个具体实现:分别表示空链表(EmptyImmutableList)和非空链表(NonEmptyImmutableList)。两种实现都非常简单:
public abstract class ImmutableList<T> : IEnumerable<T> { public static readonly ImmutableList<T> Empty = new EmptyImmutableList<T>(); ... } internal sealed class EmptyImmutableList<T> : ImmutableList<T> { public EmptyImmutableList() { } public override T Head { get { throw new InvalidOperationException("an empty list has no head."); } } public override ImmutableList<T> Tail { get { throw new InvalidOperationException("an empty list has no tail."); } } public override bool IsEmpty { get { return true; } } } internal class NonEmptyImmutableList<T> : ImmutableList<T> { public NonEmptyImmutableList(T head, ImmutableList<T> tail) { this.m_head = head; this.m_tail = tail; } private T m_head; public override T Head { get { return this.m_head; } } private ImmutableList<T> m_tail; public override ImmutableList<T> Tail { get { return this.m_tail; } } public override bool IsEmpty { get { return false; } } }
EmptyImmutableList实现了ImmutableList,并让其Head和Tail属性都抛出异常。在整个ImmutableList体系中,EmptyImmutableList和NonEmptyImmutableList类都是对外部隐藏的(因此被定义为internal),用户可以操作的唯独只是ImmutableList抽象类。在这里,为了方便起见,我们定义了一个全局唯一的EmptyImmutableList对象,放在ImmutableList的静态只读属性Empty中,在任何需要使用“空链表”的情况下,都不需要重新生成EmptyImmutableList类。
接下来便是关键了,我们需要创建一些ImmutableList在快速排序中所必要的操作。例如,构建一个链表,其中只包含一个元素:
public abstract class ImmutableList<T> : IEnumerable<T> { public static readonly ImmutableList<T> Empty = new EmptyImmutableList<T>(); public static ImmutableList<T> Create(T element) { return new NonEmptyImmutableList<T>(element, Empty); } }
请注意,由于ImmutableList是唯一对外公开的接口,因此实际上这些方法都是定义在ImmutableList上的。那么再想想,快速排序还需要什么操作?没错,就是两个链表的连接操作,这里我把它定义为“+”操作:
public static ImmutableList<T> operator +(ImmutableList<T> headList, ImmutableList<T> tailList) { if (headList == null) throw new ArgumentNullException("headList"); if (tailList == null) throw new ArgumentNullException("tailList"); if (headList.IsEmpty) return tailList; if (tailList.IsEmpty) return headList; ... }
这里我们要想一下,把两个链表连接起来之后结果是怎么样的?假设有list1和list2两个链表:
1 -> 2 -> 3 ↖ list1 4 -> 5 -> 6 ↖ list2
如果执行result = list1 + list2,那么最终的结果是什么呢?应该是这样的:
1 -> 2 -> 3 ↖ list1 1 -> 2 -> 3 -> 4 -> 5 -> 6 ↖ result ↖ list2
由于链表是不可变的,因此我们必须把list1的所有元素复制为result的前部,但是list2完全可以直接作为另一个链表的尾部。因此,最后两个链表连接后的结果会像上面所示。在这里,我们可以使用这样的代码完成这个功能:
public abstract class ImmutableList<T> : IEnumerable<T> { ... public static ImmutableList<T> Create(params T[] elements) { if (elements == null) throw new ArgumentNullException("elements"); return Create(elements, Empty); } public static ImmutableList<T> Create(IEnumerable<T> elements) { if (elements == null) throw new ArgumentNullException("elements"); return Create(elements, Empty); } private static ImmutableList<T> Create(IEnumerable<T> elements, ImmutableList<T> tail) { return NonEmptyImmutableList<T>.FromEnumerable(elements, tail); } public static ImmutableList<T> operator +(ImmutableList<T> headList, ImmutableList<T> tailList) { ... return Create(headList, tailList); } ... } internal class NonEmptyImmutableList<T> : ImmutableList<T> { public static ImmutableList<T> FromEnumerable(IEnumerable<T> elements, ImmutableList<T> tail) { NonEmptyImmutableList<T> result = null, last = null; foreach (var item in elements) { var newNode = new NonEmptyImmutableList<T>(item, Empty); if (last == null) { result = last = newNode; } else { last.m_tail = newNode; last = newNode; } } if (last != null) { last.m_tail = tail; } return result ?? tail; } ... }
具体的实现方式是NonEmptyImmutableList的FromEnumerable方法。这个方法有些“特别”,因为它直接修改了m_tail私有变量的值。这是因为,由于传入的IEnumerable是单向的,但是构造一个链表时,使用“正常操作”只能“从后往前”构造。这里NonEmptyImmutableList算是“以权谋私”了一回,利用职权便利提高了“性能”。
ImmutableList的连接操作实现完成后,我们便可以为其添加一些额外的辅助方法了。如Filter:
public static class ImmutableListExtensions { public static ImmutableList<T> Filter<T>(this ImmutableList<T> source, Func<T, bool> predicate) { if (source == null) throw new ArgumentNullException("source"); if (predicate == null) throw new ArgumentNullException("predicate"); if (source.IsEmpty) return source; return ImmutableList<T>.Create(source.Where(predicate)); } ... }
有了Filter之后,QuickSort便是轻而易举的:
public static class ImmutableListExtensions { ... public static ImmutableList<T> QuickSort<T>(this ImmutableList<T> list, Func<T, T, int> compare) { if (list == null) throw new ArgumentNullException("list"); if (compare == null) throw new ArgumentNullException("compare"); return list.IsEmpty ? list : list.Tail.Filter(e => compare(e, list.Head) < 0).QuickSort(compare) + ImmutableList<T>.Create(list.Head) + list.Tail.Filter(e => compare(e, list.Head) >= 0).QuickSort(compare); } }
看一下,是不是和Haskell代码的含义非常接近?
qsort [] = [] qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
使用一下:
var random = new Random(); var source = new List<int>(); for (int i = 0; i < 10; i++) source.Add(random.Next()); var sourceList = ImmutableList<int>.Create(source); var sortedList = sourceList.QuickSort((x, y) => x - y); foreach (var i in sourceList) Console.WriteLine(i); Console.WriteLine(); foreach (var i in sortedList) Console.WriteLine(i);
至此,您有什么疑问吗?本文所有的代码可以访问http://gist.github.com/179520。如果您感兴趣的话,可以再试试看以下两个问题。
- ImmutableList的快速排序已经完成了,那么您是否可以尝试着进行归并排序(Merge Sort)?
- 能否模拟ImmutableList构造一个ImmutableStack?我不是指“封装ImmutableList”,而是直接编写一个ImmutableStack,需要实现Pop,Push和Peek三种操作。
前排坐着慢慢看