Hello World
Spiga

趣味编程:函数式链表的快速排序(参考答案)

2009-09-02 10:58 by 老赵, 5019 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三种操作。
Creative Commons License

本文基于署名 2.5 中国大陆许可协议发布,欢迎转载,演绎或用于商业目的,但是必须保留本文的署名赵劼(包含链接),具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言

Add your comment

20 条回复

  1. Gnie
    *.*.*.*
    链接

    Gnie 2009-09-02 11:00:00

    前排坐着慢慢看

  2. 邀月
    *.*.*.*
    链接

    邀月 2009-09-02 11:01:00

    有时真怀疑老赵是不是职业写手,真是高产!

  3. 码转[未注册用户]
    *.*.*.*
    链接

    码转[未注册用户] 2009-09-02 11:10:00

    码转

  4. 老赵
    admin
    链接

    老赵 2009-09-02 11:36:00

    @邀月
    把你平时想到的都写出来就可以了。

  5. 温景良(Jason)
    *.*.*.*
    链接

    温景良(Jason) 2009-09-02 11:38:00

    想到了,但是写不出来

  6. Breeze Woo
    *.*.*.*
    链接

    Breeze Woo 2009-09-02 11:39:00

    老赵最近很迷恋趣味编程啊

  7. 老赵
    admin
    链接

    老赵 2009-09-02 11:42:00

    @温景良(Jason)
    要练习。

  8. 老赵
    admin
    链接

    老赵 2009-09-02 11:42:00

    @Breeze Woo
    锻炼编程能力很重要。

  9. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-09-02 12:11:00

    老赵在这里使用的是尾插法,我使用的头插法,导致结果是反序的,不符合输入的顺序。我再去改进一下。

  10. 老赵
    admin
    链接

    老赵 2009-09-02 12:18:00

    @Kevin Dai
    什么方法没有关系,但是结果一定要是正确的……
    就像RednaxelaFX用的就是从最后开始构造一个链表,也是正确的。

  11. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-09-02 12:36:00

    @Jeffrey Zhao
    RednaxelaFX给出的代码在不断构建新链表时,将新构建的结点放在上次构建的前面,是逆序的,但是由于是他的代码从Length-1开始遍历,最终的结果还是和输入的顺序相吻合。
    老赵给出的代码中,Create的一个重载方法采用的是FromEnumerable,也就是尾插法,就确保了顺序。否则用户输入{1,3,4,6},程序给出的链表却是{6,4,3,1},这样不符合常规呀。

    继续改进去了。

  12. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-09-02 12:39:00

    Matthew Podwysocki给出的FunctionalCSharp库中好像包含了ImmutableStack<T>,ImmutableQueue<T>,ImmutableList<T>,但是完成的不全面。

  13. 蓝蓝的天
    *.*.*.*
    链接

    蓝蓝的天 2009-09-02 13:00:00

    学习

  14. CoolCode
    *.*.*.*
    链接

    CoolCode 2009-09-02 13:22:00

    简直无敌了

  15. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-09-02 13:34:00

    @Kevin Dai

    Kevin Dai:
    @Jeffrey Zhao
    RednaxelaFX给出的代码在不断构建新链表时,将新构建的结点放在上次构建的前面,是逆序的,但是由于是他的代码从Length-1开始遍历,最终的结果还是和输入的顺序相吻合。
    老赵给出的代码中,Create的一个重载方法采用的是FromEnumerable,也就是尾插法,就确保了顺序。否则用户输入{1,3,4,6},程序给出的链表却是{6,4,3,1},这样不符合常规呀。

    继续改进去了。


    对“表”来说,从后向前构造才是“正向的”,呵呵。比较的有反思维顺序。看看Haskell的表的字面量的语法糖就知道,底下的cons运算符(:)是右结合的,像[1, 2, 3]是1 : 2 : 3 : [],实际也是先运算3 : [],然后2 : [3],然后1 : [2, 3],得到[1, 2, 3]。
    就看F#之类默认eager求值的语言,表的这种只能从后向前构造的性质就决定了某些操作非常“昂贵”,能避免就应该避免。向表的尾部添加元素(Append)是一个,连接两个表(Concat)是一个,把表的顺序逆转(Reverse)又是一个,还用用到这些操作的一些函数。经常是“啊,遍历后要保持顺序”=>“用右折叠吧”=>“耗资源好多 T T”……

    @Jeffrey Zhao
    支持IEnumerable<T>的工厂方法这点我挺喜欢的,赞。我在Of()用params数组其实也是作弊,为了能不递归;不过在Concat()里我就还是用递归了,方便……
    另外我才发现我本来不是要写NotImplementedException的,手滑了 T T

    嗯,还有就是在泛型类里定义静态方法有时候用起来会比较烦,因为静态方法只能通过类型来引用,而泛型类型需要提供类型参数才可以用,所以写起来长。所以我才写了非泛型的静态类来包装那些静态方法,让C#编译器来解决类型问题 XD

  16. 韦恩卑鄙
    *.*.*.*
    链接

    韦恩卑鄙 2009-09-02 15:07:00

    手滑了 你们都是坏人 以上

  17. 独行侠
    *.*.*.*
    链接

    独行侠 2009-09-02 16:34:00

    博主,如果北大青鸟不是好鸟的话,能否推荐一下国内还没有好一点的培训机构??

  18. 老赵
    admin
    链接

    老赵 2009-09-02 22:16:00

    @独行侠
    我对培训机构了解不多。

  19. youke[未注册用户]
    *.*.*.*
    链接

    youke[未注册用户] 2009-09-03 10:37:00

    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);
    还请博主详解一下

  20. 老赵
    admin
    链接

    老赵 2009-09-03 10:44:00

    @youke
    看一下上一片文章里的“题目”吧,有详细解释的。

发表回复

登录 / 登录并记住我 ,登陆后便可删除或修改已发表的评论 (请注意保留评论内容)

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

评论内容(大于5个字符):

  1. Your Name yyyy-MM-dd HH:mm:ss

使用Live Messenger联系我