Hello World
Spiga

趣味编程:函数式链表的快速排序

2009-08-27 17:50 by 老赵, 7437 visits

前一段时间有朋友问我,以下这段Haskell快速排序的代码,是否可以转化成C#中等价的Lambda表达式实现:

qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

我当时回答,C#中缺少一些基础的数据结构,因此不行。经过补充之后,就没有任何问题了。后来,我觉得这个问题挺有意思,难度适中,也挺考察“基础编程”能力的,于是就自己写了一个。如果您感兴趣的话,也不妨一试。

这段代码是经典的,常用的体现“函数式编程”省时省力的例子,用短短两行代码实现了一个快速排序的确了不起。您可能不了解Haskell,那么我在这里先解释一下。

首先,这里用到了函数式编程语言中最常用的一种数据结构:不可变的链表。这个数据结构事实上是一个单向链表,并且是“不可变”的。这种数据结构在F#中也有存在,它的结构用大致是这样的:

可见,这是一种递归的数据结构。如果我们把这种数据结构叫做是ImmutableList的话,那么每个ImmutableList对象就会包含一个元素的“值”,以及另一个ImmutableList对象(在上图中,每个框就是一个ImmutableList对象)。对于每个ImmutableList对象来说,这个“值”便是它的“头(Head)”,而内部的ImmutableList对象则是它的“尾(Tail)”。如果用C#来表示的话,ImmutableList在C#中的定义可能就是这样的:

public class ImmutableList<T> : IEnumerable<T>
{
    public readonly static ImmutableList<T> Empty = new ImmutableList<T>(default(T));

    private ImmutableList(T head, ImmutableList<T> tail)
    {
        this.Head = head;
        this.Tail = tail;
    }

    public T Head { get; private set; }

    public ImmutableList<T> Tail { get; private set; }

    ...
}

您一定意识到了,ImmutableList是一个不可变的链表数据结构,一旦构造之后就再也没有办法修改它的Head与Tail。此外,这里使用Empty来表示一个空链表1。因此,我们使用一个ImmutableList对象便可以代表整个链表,并可以通过Tail来遍历链表上所有的元素:

public class ImmutableList<T> : IEnumerable<T>
{
    ...

    #region IEnumerable<T> Members

    public IEnumerator<T> GetEnumerator()
    {
        var current = this;
        while (current != Empty)
        {
            yield return current.Head;
            current = current.Tail;
        }
    }

    #endregion

    #region IEnumerable Members

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    #endregion
}

我们再来观察Haskell代码,这段代码分为两行:

qsort [] = []
qsort (x:xs) = ...

这两行都定义了qsort函数,不过参数不同。这种做法在Haskell里被称为“模式匹配”,qsort后面的参数即是“模式”。第一行代码的参数“指明”是一个空链表,因此只有为qsort传入一个空的链表才会执行等号后的逻辑。如果为qsort函数传入的链表不为空,那么它即可被匹配为head和tail两部分,这在Haskell中表示为(head:tail)。因此,在调用第二行的qsort函数时,x会自动绑定为head元素,而xs会自动绑定为tail——结合之前的解释,我们可以知道x是“元素”类型,而xs是另一个链表(可能为空)。

由于C#没有Haskell的模式匹配方式,因此只能在方法内部使用if(或三元运算符?:)进行逻辑控制:

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");

        if (list == ImmutableList<T>.Empty)
        {
            ...
        }
        else
        { 
            ...
        }
    }
}

我们将QuickSort定义为ImmutableList的扩展方法,接受一个比较函数,最终则返回一个排序后的新的链表——因为ImmutableList是不可变的。

然后,我们再回到Haskell的代码,我们可以看出,第一行qsort函数由于接受了一个空链表,因此排序后的结果自然也是一个空链表。而第二行qsort则是一个较为标准的快速排序实现(快速排序的原理大致是:取一个元素作为pivot,先把那些比pivot小的元素放到pivot之前,再把比pivot大的放到pivot之后,然后对pivot的前后两部分分别采取快速排序。递归至最后,则整个链表排序完成):

qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

在上面这行代码中,filter高阶函数的作用是对一个链表进行过滤,并返回一个新的链表。它的第一个参数为过滤条件(如(< x)或(>= x),它们都是匿名函数),而第二个参数则是被过滤的目标。(这里即为xs,它是qsort参数的tail)。“++”运算符在Haskell中的含义是连接两个链表,并返回连接的结果。

因此,这行代码的含义为:把小于x的元素使用qsort函数排序,连接上x元素,再连接上大于等于x的元素排序后的结果。于是,最后的结果便是一个排好序的链表。

值得注意的是,由于链表是种不可变的数据结构,因此无论是qsort函数,filter函数,还是++运算符,它们都会返回一个新的链表,而不会对原有链表作任何修改。这点是和我们传统所做的“数组排序”相比有所不同的地方。

现在,您就来尝试实现那个QuickSort方法吧。您可以为ImmutableList补充所需的成员,只要保持ImmutableList的各种特性不变,并实现快速排序便可以了。

 

注1:原本我使用null来表示一个空链表,但是RednaxelaFX同学指出,如果使用null来表示一个空链表,在实际操作时便会造成一些特殊的情况发生。例如,对于一个null使用foreach会抛出NullReferenceException,这就要求在foreach的时候进行判断,颇为不易。因此,这里构造了一个Empty常量来表示空链表,属于Null Object Pattern的典型应用。

Creative Commons License

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

Add your comment

88 条回复

  1. egmkang
    *.*.*.*
    链接

    egmkang 2009-08-27 17:51:00

    额...绝对甲状腺功能亢进....
    这么高产

  2. 老赵
    admin
    链接

    老赵 2009-08-27 17:52:00

    @egmkang
    想到什么写什么,你平时一定也会想到很多东西,只是没有写出来的习惯罢了。

  3. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-08-27 17:55:00

    先占个座,下班回家

  4. egmkang
    *.*.*.*
    链接

    egmkang 2009-08-27 17:55:00

    @Jeffrey Zhao
    有时候想出来的东西,没有建设性,加上人懒,就算了

  5. 麒麟.NET
    *.*.*.*
    链接

    麒麟.NET 2009-08-27 17:57:00

    在回家的路上用手机看

  6. 老赵
    admin
    链接

    老赵 2009-08-27 18:00:00

    @egmkang
    多想一步,做得比别人在任何地方好一点点,都可以写成博客。

  7. 向老赵致敬[未注册用户]
    *.*.*.*
    链接

    向老赵致敬[未注册用户] 2009-08-27 18:02:00

    即将下班之际来想老赵致敬!!
    你太强大了!偶像啊!

  8. Gnie
    *.*.*.*
    链接

    Gnie 2009-08-27 18:05:00

    老赵很强悍吗,顶你个肺!

  9. egmkang
    *.*.*.*
    链接

    egmkang 2009-08-27 18:13:00

    @Jeffrey Zhao

    好一点点,这难度太高了...

  10. 老赵
    admin
    链接

    老赵 2009-08-27 18:16:00

    @egmkang
    任何地方啊。
    你比它OO,比它迅速,比它优雅,比它简单,比它清晰,在某个特别的情况下比它nb……都可以。

  11. egmkang
    *.*.*.*
    链接

    egmkang 2009-08-27 18:18:00

    @Jeffrey Zhao

    我只是比什么都不懂的菜鸟强一点,所以就算了...

  12. T.t.T!Ck.¢#
    *.*.*.*
    链接

    T.t.T!Ck.¢# 2009-08-27 19:24:00

    qsort([]) ->
    [];
    qsort([H | T]) ->
    qsort([ X || X <- T, X < H ]) ++ [H] ++ qsort([ X || X <- T, X >= H ]).



    路过

    写一段Erlang的来支持一下

    支持小胖子
    ^_^

  13. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-08-27 19:50:00

    Dim qsort = Fix(Of IEnumerable(Of Integer))(Function(f) Function(a) If(a.Count > 0, f(a.Skip(1).Where(Function(x) x < a(0))).Concat(Enumerable.Repeat(a(0), 1)).Concat(f(a.Skip(1).Where(Function(x) x >= a(0)))), Enumerable.Empty(Of Integer)))
    


    VB版。。勉强可以写成一行

  14. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-08-27 19:55:00

    Fix的实现。。虽然老赵已经见过100遍了。应该视为内置函数,因为没有确实写不了递归的。

    Function Fix(Of T)(ByVal f As Func(Of Func(Of T, T), Func(Of T, T))) As Func(Of T, T)
        Return Function(x) f(Fix(f))(x)
    End Function
    

  15. 老赵
    admin
    链接

    老赵 2009-08-27 20:20:00

    @T.t.T!Ck.¢#
    Erlang和Haskell的其实可以说是一模一样的,呵呵。

  16. 老赵
    admin
    链接

    老赵 2009-08-27 20:20:00

    @装配脑袋
    哈哈……不带你玩。
    我见一次VB的Lambda会想一次,为什么同样的功能,VB比C#强,C#却比VB简单,为什么就不能各取所长,现在总有些遗憾。

  17. sssssss——范德萨[未注册用户]
    *.*.*.*
    链接

    sssssss——范德萨[未注册用户] 2009-08-27 20:31:00

    @Jeffrey Zhao
    老赵 msn能 说下吗?请教 个 问题

  18. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-27 20:31:00

    @Jeffrey Zhao
    话说老赵的表定义的说明貌似有点瑕疵?
    表确实是递归定义的结构,因此定义中应该包含递归定义三要素的第一样:basis step(另外两个是recursive step和closure step)。表的basis就是空表,是个特殊值;老赵的定义覆盖了recursive step的情况,也就是head跟tail的那部分;重复应用recursive step就是closure step,很多时候是默认的所以很多人就不在意了。
    除非老赵想的是用null来标识空表……但null有问题,如果一个“表”的head跟tail都是null就将其视为空表的话,那如果T是值类型的话head就无法是null了。

    我只是想说这个实现细节可能得注意下……

  19. 老赵
    admin
    链接

    老赵 2009-08-27 20:41:00

    @RednaxelaFX
    你说的没错,把null视为空链表,我文章里也写了,现在去标红一下,呵呵。
    一个FuncList对象的head和tail都为null,表示长度为1的链表,其中唯一的元素为null。

    其实FuncList的定义就和学数据结构时一直玩的单链表的Node是一样的

    public class Node<T>
    {
        public T Value { get; private set; }
        public Node<T> Next { get; private set; }
    }
    

  20. 老赵
    admin
    链接

    老赵 2009-08-27 20:43:00

    @sssssss——范德萨
    页面右下角。

  21. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-27 20:50:00

    Jeffrey Zhao:
    @RednaxelaFX
    你说的没错,把null视为空链表,我文章里也写了,现在去标红一下,呵呵。
    一个表的head和tail都为null,表示长度为1的链表,这个唯一的节点中包含一个为null的元素。


    嗯我写漏了,两种情况:第一种我刚才说了,head和tail都是null的情况不合适;第二种情况就是把空表用null表示。因为null不是任何类型的值(虽然可以转换为任意可空类型),所以对它操作会有诸多问题,如把null当作FuncList<T>之后,在foreach里用它……<shock>bang</shock>

    我的建议是构造一个static readonly FuncList<T> Empty成员来表示这个特例,而不是用null。这也算是所谓null object pattern吧,虽然我不想这么叫它。如果C#能有不可空的引用类型就好了……

  22. 老赵
    admin
    链接

    老赵 2009-08-27 20:59:00

    @RednaxelaFX
    你说的有道理……我应该改一下……
    // 我觉得的确就是null object pattern,呵呵。

  23. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-08-27 21:06:00

    洗过澡来实现C#版的。

  24. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-27 21:14:00

    @Jeffrey Zhao

    Jeffrey Zhao:
    @RednaxelaFX
    你说的有道理……我应该改一下……
    // 我觉得的确就是null object pattern,呵呵。


    从实现的角度看,是null object pattern没错。我不想这么叫它是因为我不想从实现出发去套模式,而是想从抽象概念出发去引出“特例”存在的必要性然后自然的引出Empty(或者叫Nil也可以……我喜欢Empty多些 =v=)

  25. 老赵
    admin
    链接

    老赵 2009-08-27 21:17:00

    @RednaxelaFX
    模式就是从实践中总结出来的啊,你只是通过实践又一次得出了null object pattern了,呵呵。
    null object pattern不一定要取名的null的,null只是个概念,取名是根据领域来的。
    比如这里是链表,因此叫做Empty,如果是一个User,那可能就应该叫Anonymous。

  26. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-27 21:21:00

    @Jeffrey Zhao
    嗯,确实是从实践又跑到了模式里 XD
    老赵页面右下角的WLM点了之后很久都load不出来 T T

  27. OOLi
    *.*.*.*
    链接

    OOLi 2009-08-27 21:35:00

    老赵真是勤奋啊,顶,这篇看不明白

  28. 老赵
    admin
    链接

    老赵 2009-08-27 21:38:00

    @RednaxelaFX
    网速问题吧……
    // 照你的说法改好了,嘿嘿。

  29. 老赵
    admin
    链接

    老赵 2009-08-27 22:33:00

    @Kevin Dai
    基于IEnumerable<int>的C#版是这样的……但是这不是这题的本意……

    static Func<T, T> Fix<T>(Func<Func<T, T>, Func<T, T>> f)
    {
        return x => f(Fix(f))(x);
    }
    
    var qsort = Fix<IEnumerable<int>>(f => l => l.Any() ? f(l.Skip(1).Where(e => e < l.First())).Concat(Enumerable.Repeat(l.First(), 1)).Concat(f(l.Skip(1).Where(e => e >= l.First()))) : Enumerable.Empty<int>());
    

  30. 蛙蛙王子
    *.*.*.*
    链接

    蛙蛙王子 2009-08-27 23:39:00

    T.t.T!Ck.¢#:
    qsort([]) ->
    [];
    qsort([H | T]) ->
    qsort([ X || X <- T, X < H ]) ++ [H] ++ qsort([ X || X <- T, X >= H ]).



    路过

    写一段Erlang的来支持一下

    支持小胖子
    ^_^


    发现死小风行,打死,吃肉

  31. 飞林沙
    *.*.*.*
    链接

    飞林沙 2009-08-27 23:45:00

    ++ [x] ++

    我没学过Haskell,不过这在Erlang中不是说效率非常低么

  32. 老赵
    admin
    链接

    老赵 2009-08-28 00:04:00

    @飞林沙
    Haskell也一样,而且效率低的原因应该也很明显吧,这是数据结构决定的。
    The Art of Unix Programming上写,很多时候关键的是数据结构的建立,接下来使用什么算法是自然而然的事情了。

  33. T.t.T!Ck.¢#
    *.*.*.*
    链接

    T.t.T!Ck.¢# 2009-08-28 00:23:00

    蛙蛙王子:

    T.t.T!Ck.¢#:
    qsort([]) ->
    [];
    qsort([H | T]) ->
    qsort([ X || X <- T, X < H ]) ++ [H] ++ qsort([ X || X <- T, X >= H ]).



    路过

    写一段Erlang的来支持一下

    支持小胖子
    ^_^


    发现死小风行,打死,吃肉



    晕。。。被你发现了。。。不要在别人的地盘打骂。。。。

  34. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 05:48:00

    我的实现(猛点链接),敬请拍砖 =v=
    (原链接已挂,更新了新链接)

  35. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-08-28 08:14:00

    RednaxelaFX:我的实现(猛点链接),敬请拍砖 =v=



    那个基于IEnumerable和Fix的实现,可是我先给出来的哦……

  36. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 08:39:00

    @装配脑袋
    ^ ^ 我帖里没指出名字看来引起不满了。引用了老赵的版本因为我那帖主要关注C#,别无他意,请别在意
    Y组合子的写法还很多呢,在函数一层不利用语言本身的递归也能行。参考这个?当然我也是看到过别人用类似的写法才记住的,呵呵~
    虽然在函数一层避开了递归,但在类型声明上还是没避开。带类型的lambda演算真难 T T

  37. 老赵
    admin
    链接

    老赵 2009-08-28 09:11:00

    @装配脑袋
    是的是的,脑袋最厉害了!

  38. 徐少侠
    *.*.*.*
    链接

    徐少侠 2009-08-28 09:17:00

    老赵走太远了哦

    俺再不多花点脑力,快要逐渐跟不上形势了

    所谓术业有专攻,快要整不明白了,呵呵

  39. 老赵
    admin
    链接

    老赵 2009-08-28 09:19:00

    @RednaxelaFX
    你的NonEmptyImmutableList和EmptyImmutableList是很常见的用法,见了很多次,不过我为什么就没有想起来呢,唉……
    可能是以前见的大都不是纯OO的做法,而是用Discriminated Union或Case Class来实现的吧。
    还有ImmutableList的名字也比我取的好,这两方面到时候就再“抄”你一次吧……哦,名字已经抄了,嘿嘿。

  40. 老赵
    admin
    链接

    老赵 2009-08-28 09:22:00

    @徐少侠
    趣味编程,和智力题一样,应该算是给脑子作保健操才对啊,呵呵。

  41. dytes
    *.*.*.*
    链接

    dytes 2009-08-28 09:28:00

    完全被老赵知识的深度与广度所折服。

  42. ddyy[未注册用户]
    *.*.*.*
    链接

    ddyy[未注册用户] 2009-08-28 10:09:00

    public readonly static ImmutableList<T> Empty = new ImmutableList<T>(default(T)); 这个写法有问题吧?

  43. 老赵
    admin
    链接

    老赵 2009-08-28 10:49:00

    @ddyy
    我试过没有问题的。

  44. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-08-28 10:51:00

    RednaxelaFX:
    @装配脑袋
    ^ ^ 我帖里没指出名字看来引起不满了。引用了老赵的版本因为我那帖主要关注C#,别无他意,请别在意
    Y组合子的写法还很多呢,在函数一层不利用语言本身的递归也能行。参考这个?当然我也是看到过别人用类似的写法才记住的,呵呵~
    虽然在函数一层避开了递归,但在类型声明上还是没避开。带类型的lambda演算真难 T T



    想要容易地记住Lambda形式的不动点组合字,请参考Ivony的口诀。。
    另外我这篇文章中的也给了一个直接Lambda函数的实现。

  45. 装配脑袋
    *.*.*.*
    链接

    装配脑袋 2009-08-28 11:05:00

    发现我以前写的文章版面比现在漂亮。。郁闷中。。。

  46. 沐枫
    *.*.*.*
    链接

    沐枫 2009-08-28 11:09:00

    lambda不能写递归,实在麻烦

  47. ddyy[未注册用户]
    *.*.*.*
    链接

    ddyy[未注册用户] 2009-08-28 11:09:00

    ImmutableList<T>”不包含采用“1”参数的构造函数 那我这为什么有这个错误呢,请指教

  48. 沐枫
    *.*.*.*
    链接

    沐枫 2009-08-28 11:26:00

    不好意思,可以写递归。
    在C#中,这道题,我最佳只能写到下面这样:

    var data = new MyList<int> { 8, 7, 2, 3, 4, 9, 1, 5, 0 };
    
    Func<MyList<int>, MyList<int>> Qsort = null;
    Qsort = (xs) =>
        xs
        ? Qsort(xs.Filter(x => x < xs.First())) + xs.First() + Qsort(xs.Filter(x => x > xs.First()))
        : xs;
                    
    var result = Qsort(data);
    


    MyList<T>是一个List<T>,然后多了+和Filter,以及bool隐式转换。

  49. 老赵
    admin
    链接

    老赵 2009-08-28 11:28:00

    @ddyy
    自己补充一个构造函数阿。

  50. 老赵
    admin
    链接

    老赵 2009-08-28 11:31:00

    @沐枫
    bool隐式转换是什么?Filter和+是需要的,没问题的。
    不过你这个不是递归,递归要写成一行的。
    其他的差不多吧,虽然没有体现出ImmutableList的Head和Tail。
    我是希望可以遵守ImmutableList的Head和Tail结构的做法。

  51. 沐枫
    *.*.*.*
    链接

    沐枫 2009-08-28 11:40:00

    @Jeffrey Zhao

    我不是要在ImmutableList上增加程序,而是想尽量使程序简洁到与Haskell或erlang相比美的地步,总算差强人意做到了。

    Func<MyList<int>, MyList<int>> Qsort = null;
    Qsort = (xs) =>
        xs
        ? Qsort(xs.Filter(x => x < xs.First())) + xs.First() + Qsort(xs.Filter(x => x > xs.First()))
        : xs;
    


    不好的地方是数据要用MyList,不过还好,可以在MyList中定义各种数据的转换,从而使Qsort能支持多种数据。

    使用方法,就是上次的回复。


    Jeffrey Zhao:
    @沐枫
    bool隐式转换是什么?



    判断xs是否为空,一般做法是: xs.Count() != 0 ? ... : ...;
    增加bool的隐式转换,可以使这一句简化为: xs ? ... : ...;

  52. 沐枫
    *.*.*.*
    链接

    沐枫 2009-08-28 11:45:00

    Jeffrey Zhao:
    不过你这个不是递归,递归要写成一行的。


    我也想写成一行。可惜编译器告诉我,写成一行以后Qsort是 “Use of unassigned local variable 'Qsort'”

  53. 老赵
    admin
    链接

    老赵 2009-08-28 11:47:00

    @沐枫
    嗯嗯,好吧,不过我还是按照我的想法来吧,呵呵。

  54. 老赵
    admin
    链接

    老赵 2009-08-28 11:47:00

    @沐枫
    所以说不能这样写啊,这就是困难的地方。
    上面的脑袋已经给出答案了,我也列了个C#版的。

  55. 沐枫
    *.*.*.*
    链接

    沐枫 2009-08-28 11:50:00

    @Jeffrey Zhao
    可以这样写,只不过是从一行变成两行,还挺清晰,运行结果也非常正确。
    :)

  56. 老赵
    admin
    链接

    老赵 2009-08-28 12:10:00

    @沐枫
    我的意思是,这样写就不算递归了,递归必须写成一行。
    你这样写虽然清晰,但是其含义不是递归,只不过是针对引用的调用了。
    如果你没有理解的话,我一会儿写篇简单的文章解释一下吧。

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

    韦恩卑鄙 2009-08-28 12:23:00

    Jeffrey Zhao:
    @RednaxelaFX
    你说的没错,把null视为空链表,我文章里也写了,现在去标红一下,呵呵。
    一个FuncList对象的head和tail都为null,表示长度为1的链表,其中唯一的元素为null。

    其实FuncList的定义就和学数据结构时一直玩的单链表的Node是一样的

    public class Node<T>
    {
        public T Value { get; private set; }
        public Node<T> Next { get; private set; }
    }
    


    其实我的枚举树也是用 T[0] 代替null 的 -0-

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

    韦恩卑鄙 2009-08-28 12:32:00

    Jeffrey Zhao:
    @egmkang
    任何地方啊。
    你比它OO,比它迅速,比它优雅,比它简单,比它清晰,在某个特别的情况下比它nb……都可以。


    恩恩 一直以此为标准

  59. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 12:59:00

    @装配脑袋

    Jeffrey Zhao:
    @装配脑袋
    是的是的,脑袋最厉害了!


    顶~等我回头想去编辑我的blog加上脑袋的ID时,blog就又断网了……你们能在断网前看到我真高兴 TvT

    装配脑袋:
    想要容易地记住Lambda形式的不动点组合字,请参考Ivony的口诀。。
    另外我这篇文章中的也给了一个直接Lambda函数的实现。


    多谢,又多了些记法,呵呵。我平时记在心的里就是人家的系徽Y F = F (Y F) =v=

    @Jeffrey Zhao

    Jeffrey Zhao:
    @RednaxelaFX
    你的NonEmptyImmutableList和EmptyImmutableList是很常见的用法,见了很多次,不过我为什么就没有想起来呢,唉……
    可能是以前见的大都不是纯OO的做法,而是用Discriminated Union或Case Class来实现的吧。
    还有ImmutableList的名字也比我取的好,这两方面到时候就再“抄”你一次吧……哦,名字已经抄了,嘿嘿。


    嗯,不过说到底我写的那个就是啰嗦,人家两行解决的代码我给弄出了200行。我这是明知道自己写不短了,干脆破罐子破摔啊
    ……当然最关键的部分勉强也可以算两行吧(QuickSortCore<T>())。
    NonEmptyImmutableList跟EmptyImmutableList的写法都是照抄DLR的Expression Tree v2的形式。

    较早期的ETv2的设计是在共同基类Expression上保存一个域来记录NodeType,派生类在调用基类构造器时将实际的NodeType传进去。后来发现DLR这种位于底层的库如果吃很多内存影响太大,所以他们用尽了一切办法来减少内存使用,例如把一些循环从foreach改为for来减少IEnumerator实例的个数,又例如把NodeType变为Expression类上的抽象属性,由每个派生类提供getter实现,里面返回常量。这样就从每个Expression实例都需要带着一个域来表示其NodeType变为每个Expression的具体类型的虚方法表里多了一项,比较划算。
    现在的ETv2里像MethodCallExpression之类的都有很多特化版本,能少用域就少用,能不用数组就不用。

    看惯了这种写法之后我也习惯性的照搬了。所以在EmptyImmutableList里根本就没有保存_head和_tail,反正它也不需要那两个域(但没省多少,因为它是单例;我忘了加上私有构造器了)。

  60. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 13:11:00

    早上看到消息说今天白天blog又要断网,本来是想把帖发到园子的。但是在编辑器里折腾了半天弄出来的效果都很糟,以前一直没调教出好用的模板,这下就麻烦了 T T

    @沐枫

    沐枫:
    @Jeffrey Zhao
    可以这样写,只不过是从一行变成两行,还挺清晰,运行结果也非常正确。
    :)


    Jeffrey Zhao:
    @沐枫
    我的意思是,这样写就不算递归了,递归必须写成一行。
    你这样写虽然清晰,但是其含义不是递归,只不过是针对引用的调用了。
    如果你没有理解的话,我一会儿写篇简单的文章解释一下吧。


    嘿嘿,我来抢。看看这段代码足够说明问题了:
    using System;
    
    static class Program {
        static void Main(string[] args) {
            Func<int, int> fac = null;
            fac = x => x > 1 ? x * fac(x - 1) : x;
            Console.WriteLine(fac(5)); // 120
            
            var facAlias = fac;
            fac = x => {
                Console.WriteLine("You screwed up, dude");
                return x;
            };
            Console.WriteLine(facAlias(5)); // 20
        }
    }
    

    真递归的lambda,赋值给别的委托之后,即便修改源委托的指向也不会改变其递归的性质。

  61. 老赵
    admin
    链接

    老赵 2009-08-28 13:19:00

    @RednaxelaFX
    干,被你抢了。我刚才都开始写代码了:

    Func<int, int> fib = null;
    fib = x => x <= 1 ? x : fib(x - 1) + fib(x - 2);
    for (var i = 0; i < 10; i++) Console.WriteLine(fib(i));
    
    var anotherFib = fib;
    fib = x => x;
    for (var i = 0; i < 10; i++) Console.WriteLine(anotherFib(i));
    

  62. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 13:21:00

    @Jeffrey Zhao
    抢垒成功……||||
    果然需要简单的例子时不时fib就是fac么,哈哈

  63. 老赵
    admin
    链接

    老赵 2009-08-28 13:22:00

    @RednaxelaFX
    我也来挑刺,你的阶乘写错了,哈哈。不应该是:

    fac = x => x > 1 ? x * fac(x - 1) : x;
    
    而应该是
    fac = x => x > 1 ? x * fac(x - 1) : 1;
    

  64. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 13:24:00

    @Jeffrey Zhao

    Jeffrey Zhao:
    @RednaxelaFX
    我也来挑刺,你的阶乘写错了,哈哈。不应该是:

    fac = x => x > 1 ? x * fac(x - 1) : x;
    
    而应该是
    fac = x => x > 1 ? x * fac(x - 1) : 1;
    


    确实……正常范围内一样,错误范围内就不一样了 T T
    哦对了还有0……
    那老赵的fib也……

  65. 老赵
    admin
    链接

    老赵 2009-08-28 13:27:00

    @RednaxelaFX
    咦,我的fib是
    fib(0) = 1
    fib(1) = 1
    ...

  66. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 13:30:00

    @Jeffrey Zhao
    嗯我看到了……(羞
    要是考虑扔进去的是负数的状况嘛……在错误范围内那样写fib也是一糟糕。诶其实都写了那么多次了这种函数我居然还写错,抢垒抢晕乎了 XDD

  67. 老赵
    admin
    链接

    老赵 2009-08-28 13:38:00

    @RednaxelaFX
    你那200行是在补充ImmutableList基础结构,怎么能算进去,说到底QuickSort其实也就一行啊。这是我写的:

    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);
    }
    

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

    韦恩卑鄙 2009-08-28 13:51:00

    你害得我很头疼

  69. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 13:57:00

    @Jeffrey Zhao
    嗯,不错。到最核心的部分其实都差不了多少,毕竟原本的Haskell代码摆在那里。我是为了避免每次都检查null所以把递归部分拆出来了。要是原始代码是其它版本的话,翻出来的C#代码也会跟着变。

    Ruby里的数组连接也是重载了加号,平时用着也没觉得怎么不好。不过换个语境在这里重载加号我有点不习惯,concat用惯了(汗

  70. 老赵
    admin
    链接

    老赵 2009-08-28 14:20:00

    @RednaxelaFX
    Concat没有问题,其实是一回事。我最痛恨的其实是语言中的括号……
    如果能像Scala一样,把括号都省了该有多好。
    1 + 2等价于1.+(2),A.Fuck(B)可以写成A Fuck B,多美妙。
    Scala就是一堆堆语法糖组成的,所以号称Scalable Language。

  71. 老赵
    admin
    链接

    老赵 2009-08-28 14:22:00

    @韦恩卑鄙
    下次可以用ImmuableList写点其它东西玩,也是不错的。

  72. RednaxelaFX
    *.*.*.*
    链接

    RednaxelaFX 2009-08-28 14:26:00

    @Jeffrey Zhao
    嗯,我也是不喜欢括号和嵌套。所以像是碰到要多个参数SelectMany的时候我宁可用查询表达式的语法,没括号。
    说到不要括号,Ioke也不错。不过我觉得我可能给SICP折磨多了之后已经放弃抵抗括号多的问题了 T T

  73. klvk
    *.*.*.*
    链接

    klvk 2009-08-28 16:47:00

    哦 厉害厉害 写来试试看

  74. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-08-30 09:21:00

    @Jeffrey Zhao
    我准备用递归和yield return来解决,呵呵,是你的本意啊?

  75. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-08-30 09:45:00

    大致设想:

    
    
    
    yield return QuickSort(list.Where(item => item < pivot).Select(x=>x));
    yield return list.Where(item => item == pivot).Select(x=>x);
    yield return QuickSort(list.Where(item => item > pivot).Select(x=>x));
    

  76. 老赵
    admin
    链接

    老赵 2009-08-30 13:08:00

    @Kevin Dai
    QuickSort都的签名都已经给出了,你这么做的含义是什么呢?

  77. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-08-30 14:08:00

    你给出的QuickSort中的第二个参数是用来比较的。我的意思是:

    先选择pivot,然后按照此pivot,把利用IEnumerable<T>的Where(x=>x<pivot)扩展方法进行筛选出小于pivot的元素,然后在这些小于pivot的元素上递归调用QuickSort,然后再根据Where扩展方法筛选出等于pivot的元素,然后再筛选出大于pivot的元素,再调用QuickSort。将这这三步的结果合成便是排序结果了。

  78. 老赵
    admin
    链接

    老赵 2009-08-30 14:17:00

    @Kevin Dai
    首先,代码写完整再说吧,其中某个步骤没有太大意义的。
    其次,我的本意是模仿Haskell的版本。
    // 还有,你每行最后都加Select(x => x)做什么呢?

  79. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-08-30 15:09:00

    @Jeffrey Zhao
    “你每行最后都加Select(x => x)做什么呢? ” 我刚刚也发现这个问题了。

  80. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-08-30 17:31:00

    @Jeffrey Zhao
    我的意思也是如Haskell那段代码那样,根据Head筛选出比Head小的元素进行快速排序(递归调用),排序后的结果再拼接上Head,然后再筛选出比Head大的元素进行快速排序(递归调用),然后再拼接这一步的结果。

  81. 老赵
    admin
    链接

    老赵 2009-08-30 18:02:00

    @Kevin Dai
    不要光说,要写出代码来。QuickSort方法很简单,这题的关键是支持这段代码的基础数据结构ImmutableList。
    例如,RednaxelaFX的ImmutableList及辅助函数写了近200行,而QuickSort的核心才1行。

  82. Kevin Dai
    *.*.*.*
    链接

    Kevin Dai 2009-08-30 19:39:00

    @Jeffrey Zhao
    你的意思是完成整个ImmutableList的实现啊,我一直认为也就一个快速排序的实现。

  83. 老赵
    admin
    链接

    老赵 2009-08-30 19:58:00

    @Kevin Dai
    不用完整,够用就好。
    只做快速排序太容易了,这篇文章的标题就是“函数式链表的快速排序”。
    此外,文章里也都给出ImmutableList的定义了,我想已经够明白了吧……

  84. abruzzi
    *.*.*.*
    链接

    abruzzi 2009-09-01 09:27:00

    这个页面的布局有点乱了,中分?代码部分有的都折行了,不好看。

  85. EricWen
    *.*.*.*
    链接

    EricWen 2009-09-01 11:10:00

    强顶下。

  86. EricWen
    *.*.*.*
    链接

    EricWen 2009-09-01 11:17:00

    有没有完整代码啊。
    让菜鸟能弄懂点。

  87. 老赵
    admin
    链接

    老赵 2009-09-01 13:12:00

    @EricWen
    这只是题目,还没有解答呢

  88. 老赵
    admin
    链接

    老赵 2009-09-01 13:13:00

    @abruzzi
    其实是右边固定,左边自适应,呵呵。

发表回复

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

昵称:(必填)

邮箱:(必填,仅用于Gavatar

主页:(可选)

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

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

使用Live Messenger联系我