之前对于函数式编程语言一直没有系统学习过，只是在 C# 、Objective-C 等语言中接触过闭包等概念，但这些只是函数式编程的一点皮毛。当然这也正说明了函数式编程语言对传统面向过程/面向对象编程语言的深刻影响。

与 Scala 仍然兼容面向过程/面向对象不同，Haskell 是一种纯粹的函数式编程语言。

最近一段时间对 Haskell 的学习，几乎颠覆了以往面向过程、面向对象编程形成的思维定式。

其中印象最深的一点就是递归思维，Learn You a Haskell for Great Good! 中的原话是:

Thinking recursively.

也许你会觉得递归是个很平常的东西，比如：求阶乘、Fabonacci 数列、二叉树遍历等，都会用到。但是，在 Haskell 的世界，递归几乎无处不在。作为一门函数式编程语言，它更强调对问题本身的描述，而不是对求解过程的描述。

以下是 Learn You a Haskell for Great Good! 中对递归的一段表述:

Recursion is important to Haskell because unlike imperative languages, you do computations in Haskell by declaring what something is instead of declaring how you get it.

That’s why there are no while loops or for loops in Haskell and instead we many times have to use recursion to declare what something is.

很多在其他语言中你根本想不到用递归的问题，在这里都可以用递归轻松搞定。你几乎可以完全告别 for 循环之类的东西。

求 list 最大项

对于这个问题，习惯面向过程编程的程序员几乎不用思考就能给出实现：

• 定义一个变量 max ，初始值置为首个(或最后一个)元素;

• 遍历 list ，逐项和 max 比较，如果更大则替换;

而在 Haskell 中借助 (x:xs) 模式匹配和递归，不用遍历就可以实现：

• 直接将 head 和 tail (除首项外的其他元素)中的最大元素作比较;

• 对 tail 部分递归调用求最大项;

• 递归终止条件: 单元素 list 最大项就是本身;

代码如下:

funcMaximum :: (Ord a) => [a] -> a
funcMaximum [] = error "Empty list!"
funcMaximum [x] = x
funcMaximum (x:xs)
	| x > maxTail = x
	| otherwise = maxTail
	where maxTail = funcMaximum xs

可以看到，根本不需要用 for 循环遍历！

求 list 长度

同样，在面向过程编程中，我们通常的解决方式也是需要遍历 list 的。

受上面那个问题的启发，这里仍然可以利用类似的思路解决:

• 整个 list 长度等于 tail 长度 + 1;

• 对 tail 部分递归地求长度;

• 递归终止条件: 空 list 长度为 0;

代码如下:

funcLength :: [a] -> Int
funcLength [] = 0
funcLength (_:xs) = 1 + funcLength xs

list 反转

这个问题如果不用递归，也是需要遍历。利用 Haskell 中的 ++ 运算符和递归也能很容易解决(递归终止条件依然是单元素)：

funcReverse :: [a] -> [a]
funcReverse [x] = [x]
funcReverse (x:xs) = funcReverse xs ++ [x]

可以看到，Haskell 写出的代码不仅简洁，而且更加符合自然语言，可读性更强。

判断 list 是否包含某元素

面向过程编程中，这个问题应该是最容易想到遍历而不会想到递归的。

Haskell 中的递归解决思路如下:

• 直接将这个元素和 head 比较: 相等则返回 True ，不相等则对 tail 部分递归求解;

• 递归终止条件: 空 list 直接返回 False ;

代码如下:

funcContains :: (Eq a) => [a] -> a -> Bool
funcContains [] a = False
funcContains (x:xs) a
	| x == a = True
	| otherwise = xs `funcContains` a

这里为了在调用时使表达式更接近自然语序，特意将 funcContains 函数定义为中缀表达式形式。

取 list 前 n 个元素

借助 : 运算符，同样可以很方便地用递归方式实现:

• 取 head ，并递归地从 tail 中取前 n - 1 个元素;

• 将 head 和 tail 的前 n - 1 个元素使用 : 运算符构造新的 list;

• 递归终止条件: n <= 0 或 list 为空时，直接返回空 list;

代码如下:

funcTake :: (Num n, Ord n) => [a] -> n -> [a]
funcTake _ n
	| n <= 0 = []
funcTake [] _ = []
funcTake (x:xs) n = x : xs `funcTake` (n-1)

这里同样将函数定义为中缀表达式形式。

快速排序

接下来不妨再来看一个经典的运用递归解决的问题: 快速排序。

虽然其他语言写出来的代码也很简洁(一般 20 行以内)，但分治、递归的过程还是会比较麻烦(可参考我之前写的 Golanng 版本实现)。

而得益于 list comprehension 接近数学语言的描述能力、强大的 (x:xs) 模式匹配和 ++ 运算符，Haskell 版本的代码显然更加优雅(这里选取第一个元素为初始 pivot ):

funcQuickSort :: (Ord a) => [a] -> [a]
funcQuickSort [] = []
funcQuickSort (x:xs) =
	let smallerSorted = funcQuickSort [a | a <- xs, a <= x]
	    biggerSorted = funcQuickSort [a | a <- xs, a > x]
	in smallerSorted ++ [x] ++ biggerSorted

这个版本对于 Haskell 程序员来说绝对是最难忘的，也是最快、最容易写出来的。

不过要论简洁，似乎 Erlang 版本更胜一筹。以下代码来自知乎，没系统学过 Erlang ，未作求证。

funcQuickSort([]) -> [];
funcQuickSort([H|T]) -> funcQuickSort([E|E<-T, E<H]) ++ [H] ++ funcQuickSort([E|E<-T, E>=H]).

但是由于二者同为函数式编程语言，除了 Haskell 特有的函数类型声明，代码主体部分其实并没有太大差异。

上面的两个版本都使用了接近数学语言的描述方式，其实在 Haskell 中借助 filter 函数还可以使得代码更加简洁、易读(其第一个参数为过滤条件函数):

funcQuickSort :: (Ord a) => [a] -> [a]
funcQuickSort [] = []
funcQuickSort (x:xs) =
	let smallerSorted = funcQuickSort (filter (<x) xs)
	    biggerSorted = funcQuickSort (filter (>x) xs)
	in smallerSorted ++ [x] ++ biggerSorted

二叉搜索树

BinarySearchTree 的很多操作也会用到递归。Haskell 的实现代码依然足够简洁易读。

首先定义数据结构:

data BinaryTree a = Empty | Node a (BinaryTree a) (BinaryTree a) deriving (Eq, Show)

可以看到，上面的代码描述是如此接近 BinarySearchTree 的自然语言定义！

插入元素:

insertValue :: (Ord a) => a -> BinaryTree a -> BinaryTree a
insertValue x Empty = Node x Empty Empty
insertValue x (Node a left right)
	| x == a = Node x left right
	| x < a = Node a (insertValue x left) right
	| x > a = Node a left (insertValue x right)

判断是否包含某元素:

hasValue :: (Ord a) => a -> BinaryTree a -> Bool
hasValue x Empty = False
hasValue x (Node a left right)
	| x == a = True
	| x < a = hasValue x left
	| x > a = hasValue x right

删除元素过程稍显复杂: 要分左右子树是否为空等几种情况讨论，还要定义获取最小子节点的函数，具体可参考我的 Golang 实现。这里不再赘述。

虽然使用递归会对效率有影响，而且 Haskell 本身偏学术，商业应用不多。但是这种思维方式对我们平常开拓编程思路还是大有裨益的。

这里是我写的所有 Haskell Demo。

参考:

• Learn You a Haskell for Great Good!

• Real World Haskell