如何实现趣味编程中的函数式链表快速排序算法？

本文共计1384个文字，预计阅读时间需要6分钟。

当然可以。以下是对您提供的文本的简写版本，不超过100个字：

友问：以下Haskell排序代码，能否转化为C？

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

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

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

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

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

可见，这是一种递归的数据结构。如果我们把这种数据结构叫做是ImmutableList的话，那么每个ImmutableList对象就会包含一个元素的“值”，以及另一个ImmutableList对象（在上图中，每个框就是一个ImmutableList对象）。