从素数生成看 Haskell 的简洁性

最近有空就在看 Haskell，真是越看越觉得这个语言有意思。在知乎（原回答 @阅千人而惜知己的）找到了一份很有意思的求素数代码，非常简洁，我觉得很能体现这个语言的特点。

primes = sieve [2..]
sieve (p:xs) = p : sieve [x| x <- xs , x `mod` p /=0 ]

其实本质思想就是 Eratosthenes 筛法。核心函数就是 sieve，大致处理过程是这样：读入一个列表，并取出第一个元素 p。然后筛选出不能被 p 整除的剩余数字，递归求解。这里提及一下，[2..] 是 Haskell 列表的一个神奇的特性，即支持无限列表。这个 Haskell 的 lazy 特性有很大的关系。类似的算法在 CPP 中可以这么表示：

bool primes[maxn];                           
for (int i = 2; i < sqrt(maxn+0.5); i++) {   
	if (!primes[i]) {                        
		for (int j = i + i; j < maxn; j += i)
			primes[j]++;
	}
}

需要注意的是，这段代码的结果并不是一个内容为 2-maxn 内素数的数组，而是记录 2-maxn 间的数字是不是素数的一个布尔数组。那么，如果是放在同样具有列表解析的 Python 中，又能怎么写呢？

primes = [x for x in range(2, maxn) if x not in [j for i in range(2, int(math.sqrt(maxn + 0.5))) for j in range(i + i, maxn, i)]]

这段代码体现了 python 列表解析的一个特点 —— 很难看懂。不过其算法本质还是和 CPP 版本相同。

百度的时候还发现了大牛廖雪峰的另一种操作，即采用 generator 的形式构造一个序列并 filter。这种 lazy 的处理方法和 Haskell 是极其类似的，看代码：

def _odd_iter():  # 构造偶数序列
    n = 1
    while True:
        n = n + 2
        yield n

def _not_divisible(n):
    return lambda x: x % n > 0

def get_primes():
    yield 2
    it = _odd_iter()  # 初始序列
    while True:
        n = next(it)  # 返回序列的第一个数
        yield n
        it = filter(_not_divisible(n), it)  # 构造新序列

看来看去，似乎 Haskell 的版本真的很简单舒服。的确，在处理诸如递归这种问题上，FP 总是能用短小精悍的代码在众多语言中脱颖而出。比如斐波那契数列的生成：

fibonaccis = 1 : 1 : zipWith (+) fibonaccis (tail fibonaccis)

fibonacci !! 12 输出 233，结果正确。这段代码也是 Haskell 简洁性的高度体现。其中，tail 想到与后移整个数列，之后通过 zipWith 函数的处理将两个数列相加，以此来达到 F (n)=F (n-1)+F (n-2) 的效果。我们可以试验下，比如：zipWith (+) [1,1,2] (tail [1,1,2]) 的结果是 [2,3]。所以大致就是一个移动数组并叠加的过程。

虽然说这样高度精简的代码由于不直观，并不太适合在实际的项目中使用，况且其他语言的稍长的代码甚至可能在效率上更优，但这仍不影响 Haskell 表现其独有的简洁及优雅的魅力。而这也正是我们研究 FP 的一大重要动力。