C#函数式编程入门之快速排序解决方案

C#函数式编程入门之快速排序
之前有人提出C#实现Currying太难看，也有人提出了F#。于是我又用F#写了下之前的那几个例子程序
第一个

    let add x y = x + y

    let mutable i = add 3 4

    printfn "%d" i

第二个

    let addTen x = add 10 x

    let mutable i = add 3 4

    let mutable j = addTen i

    printfn "%d" j

第三个

    let eval x y z = y x z

    let add x y = x + y

    let mutable i = eval 3 add 5

    printfn "%d" i

第四个

    let eval x y z = y x z

    let sub x y = x - y

    let mutable i = eval 8 sub 1

    printfn "%d" i

最后一个

    let outputArray = Array.iter (fun x -> printfn "%d" x)

    outputArray [| 1; 2; 3; 4; 5 |] 

和C#的版本一比较，真是太优雅了！

好了，开始正题：

之前我在论坛贴了一个神奇的程序，用Lisp进行的快速排序

quicksort [] = []

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)

    where

        lesser = filter (< p) xs

        greater = filter (>= p) xs

有人表示看天书一样，为了解释原理，我用C#改写了一个，代码稍微猥琐了点，但是还是很简洁的：

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;


namespace ConsoleApplication1

{

    class Program

    {        

        static void Main(string[] args)

        {

            Func<Func<int, int, bool>, Func<int[], int[]>> filter =

                x => new Func<int[], int[]>(y => y.Skip(1).Where(z => x(y[0], z)).ToArray());

            Func<int[], int[]> qsort = x => x;

            Func<int[], int[]> lesser = dt => filter((x, y) => y < x)(dt);

            Func<int[], int[]> greater = dt => filter((x, y) => y >= x)(dt);

            qsort = dt => dt.Length > 1 

                ? qsort(lesser(dt)).Concat(new int[] { dt[0] }).Concat(qsort(greater(dt))).ToArray()

                : dt;

            int[] data = { 4, 3, 1, 4, 6, 7, 5, 9, 3, 11, 1, 2, 11 };

            var result = qsort(data);

            foreach (int x in result) Console.WriteLine(x);

        }

    }

}

运行：

1
1
2
3
3
4
4
5
6
7
9
11
11
Press any key to continue . . .

简单解释下，其实这个不用我废话，如果快速排序的原理你没有忘记的话。
快速排序的思路就是根据某个元素（我这里用第一个元素）为参照，把数据分成两堆，小的一堆在左边，大的在右边，参照数据在中间，然后分别对左右两堆递归整理，直到某一堆只有一个元素为止，此时，数据就是排好序的了。

说说程序猥琐在什么地方，复杂的类型声明这个不用提，也不用提数组的连接，因为除非使用代码块，没办法在Lambda表达式内再嵌套定义Lambda表达式，只好让lesser和greater后面跟着难看的(dt)。

最后用F#实现一次：

[<EntryPoint>]

let main argv = 

    let lesser (x: int array) = Array.filter (fun i -> i < x.[0]) x.[1..]

    let greater (x: int array) = Array.filter (fun i -> i >= x.[0]) x.[1..]

    let rec qsort (p: int array) = 

        match p.GetLength(0) with