从素数生成看 Haskell 的简洁性

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
primes = sieve [2..]
sieve (p:xs) = p : sieve [x| x <- xs , x `mod` p /=0 ]
primes = sieve [2..] sieve (p:xs) = p : sieve [x| x <- xs , x `mod` p /=0 ]
primes = sieve [2..]
sieve (p:xs) = p : sieve [x| x <- xs , x `mod` p /=0 ]

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

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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]++;
}
}
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]++; } }
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 中,又能怎么写呢?

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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)]]
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)]]
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 是极其类似的,看代码:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
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) # 构造新序列
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) # 构造新序列
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 总是能用短小精悍的代码在众多语言中脱颖而出。比如斐波那契数列的生成:

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
fibonaccis = 1 : 1 : zipWith (+) fibonaccis (tail fibonaccis)
fibonaccis = 1 : 1 : zipWith (+) fibonaccis (tail fibonaccis)
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 的一大重要动力。

分享到

KAAAsS

喜欢二次元的程序员,喜欢发发教程,或者偶尔开坑。(←然而并不打算填)

相关日志

  1. 没有图片
  2. 没有图片
  3. 没有图片
  4. 没有图片

评论

还没有评论。

在此评论中不能使用 HTML 标签。