趣味编程：函数式链表的快速排序（参考答案）
2009-09-02 10:58 by 老赵, 6238 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三种操作。
前排坐着慢慢看