本文通过在 Haskell 中生成 Fibonacci 数列这个例子讨论了 Haskell 中 list comprehension 是如何转换为
Haskell Kernel 的，借此可以理解 Haskell 的 list comprehension 是如何工作的。
一、例子
Fibonacci 数列的定义:
F_n = 0 if n = 0
1 if n = 1
F_(n-1) + F_(n-2) if n >= 2
在 Haskell 中应该如何生成 F_n 呢？当然，可以直接将 F_n 的定义翻译为 Haskell 代码。但是，也可以使用
list comprehension 来实现:
-- fib1.hs
-- fibonacci sequence, DOESN'T WORK
fibs = 0 : 1 : [ x + y | x <- fibs, y <- tail fibs ]
看起来这个实现是应该可以得到 Fibonacci 数列，可是取前十个数字时得到如下结果:
> take 10 fibs
[0,1,1,1,1,1,1,1,1,1]
这个结果显然不对。交换下 x, y 的位置试试:
-- fib2.hs
-- fibonacci sequence, DOESN'T WORK
fibs = 0 : 1 : [ x + y | y <- tail fibs, x <- fibs ]
同样取前是个数字:
> take 10 fibs
[0,1,1,2,2,3,3,4,4,5]
也不是期望的结果。为什么是这样呢? Haskell 中的 list comprehension 是如何工作的?
二、Haskell 中的 list comprehension 是如何工作的?
按照 Haskell 98 Report Sect. 3.11 List Comprehension, Haskell 中 list comprehension 的一般形式为
[ e | q_1, ... , q_n ] (n >= 1), 其中 q_i 称为 qualifier, 而 pat <- exp 这种形式的 qualifier 称为
generator。
[ e | q_1, ... , q_n ] 这个表达式的意义 Haskell 98 Report 是这样描述的：
"Such a list comprehension returns the list of elements produced by evaluating e in the successive
environments created by the nested, depth-first evaluation of the generators in the qualifier list."
转换成 Haskell Kernel 后就是：
[ e | p <- l, Q ] = let ok p = [ e | Q ]
ok _ = []
in concatMap ok l
其中 Q 是剩余的 qualifier。
1) 对 fib1.hs 的解释
按照上面的说法，
-- fib1.hs
fibs = 0 : 1 : [ x + y | x <- fibs, y <- tail fibs ]
会被转换为:
fibs = 0 : 1 :
let ok x = [ x + y | y <- tail fibs ]
ok _ = []
in concatMap ok fibs
而 ok x = [ x + y | y <- tail fibs ] 会进一步被转换为:
ok x = let ok1 y = [ x + y ]
ok1 _ = []
in concatMap ok1 (tail fibs)
fibs 的第一、第二个数字分别是 0 和 1，那第三个呢？第三个数字是通过如下方式获取的:
head $ ok 0 -- x = 0
= head $ ok1 1 -- y = 1
= head $ [ 0 + 1 ] -- ok1 的定义
因此第三个数字为 1。第四个数字通过如下方式获取:
second $ ok 0 -- x = 0；x 的值不变
= second $ ok1 1 -- y = 1; y 的值仍为 1
= second $ [_, 0 + 1]
因此第四个数字仍为 1。
实际上，由于 fibs 本身是无穷数列，因此 fibs 的第三到第N个数字就是如下数列的第一到第(N-2)个数字:
ok 0
= concatMap ok1 (tail fibs)
= concatMap (\y -> [ 0 + y ]) (tail fibs)
另外，通过 ghc -ddump-ds -c fib1.hs 可以获取 fibs = 0 : 1 : [ x + y | x <- fibs, y <- tail fibs ]
desugar 后的结果:
==================== Desugar ====================
Rec {
$dNum_aaT :: GHC.Num.Num GHC.Num.Integer
[]
$dNum_aaT = GHC.Num.$f3
Fib.fibs :: [GHC.Num.Integer]
[Exported]
[]
Fib.fibs =
GHC.Base.:
@ GHC.Num.Integer
lit_a7r
(GHC.Base.:
@ GHC.Num.Integer
lit_a7t
(__letrec {
ds_dgu :: [GHC.Num.Integer] -> [GHC.Num.Integer]
[]
ds_dgu =
\ (ds_dgv :: [GHC.Num.Integer]) ->
case ds_dgv of ds_dgv {
[] -> GHC.Base.[] @ GHC.Num.Integer;
: ds_dgw ds_dgx ->
let {
x_a5G :: GHC.Num.Integer
[]
x_a5G = ds_dgw } in
__letrec {
ds_dgy :: [GHC.Num.Integer] -> [GHC.Num.Integer]
[]
ds_dgy =
\ (ds_dgz :: [GHC.Num.Integer]) ->
case ds_dgz of ds_dgz {
[] -> ds_dgu ds_dgx;
: ds_dgA ds_dgB ->
let {
y_a5I :: GHC.Num.Integer
[]
y_a5I = ds_dgA
} in GHC.Base.: @ GHC.Num.Integer (+_aaC x_a5G y_a5I) (ds_dgy ds_dgB)
};
} in ds_dgy (GHC.List.tail @ GHC.Num.Integer fibs_a7n)
};
} in ds_dgu fibs_a7n))
$dNum_aaV :: GHC.Num.Num GHC.Num.Integer
[]
$dNum_aaV = $dNum_aaT
+_aaC :: GHC.Num.Integer -> GHC.Num.Integer -> GHC.Num.Integer
[]
+_aaC = GHC.Num.+ @ GHC.Num.Integer $dNum_aaV
fromInteger_aaU :: GHC.Num.Integer -> GHC.Num.Integer
[]
fromInteger_aaU = fromInteger_aaS
lit_a7t :: GHC.Num.Integer
[]
lit_a7t = fromInteger_aaU (GHC.Num.S# 1)
fromInteger_aaS :: GHC.Num.Integer -> GHC.Num.Integer
[]
fromInteger_aaS = GHC.Num.fromInteger @ GHC.Num.Integer $dNum_aaT
lit_a7r :: GHC.Num.Integer
[]
lit_a7r = fromInteger_aaS (GHC.Num.S# 0)
fibs_a7n :: [GHC.Num.Integer]
[]
fibs_a7n = Fib.fibs
end Rec }
从中可以清楚的看到 list comprehension 被转换成了嵌套的 concatMap，以及上面 ok, ok1 的定义。
2) fib2.hs 的解释
fib2.hs 的情况和 fib1.hs 类似，留做练习 :-)
fib1.hs 和 fib2.hs 无法得到正确的结果，皆是因为在 Haskell 的 list comprehension 中，对各个 generator
的求值是有特定顺序的。那么，在 Haskell 中如何通过 list comprehension 生成 Fibonacci 数列？
三、在 Haskell 中如何通过 list comprehension 生成 Fibonacci 数列？
如何只使用 Haskell 98，那么没有什么办法。但若使用 GHC 的 parallel list comprehension 扩展，则可采用如下实现:
-- fib3.hs
{-# LANGUAGE ParallelListComp #-}
module Fibonacci where
-- fibonacci sequence
fibs = 0 : 1 : [ x + y | x <- fibs | y <- tail fibs ]
取前十个数字:
> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]
是预期的结果。
Parallel list comprehension 按照 GHC 手册(Sect. 8.3.4. Parallel List Comprehensions)的说法，是:
"Parallel list comprehensions are a natural extension to list comprehensions. List comprehensions can
be thought of as a nice syntax for writing maps and filters. Parallel comprehensions extend this to
include the zipWith family."
这句话的具体意思参见 GHC 用户手册对 parallel list comprehension 的描述。另外也可参见 ghc 对 fib3.hs desugar
后的结果。
最后，既然 parallel list comprehension 可看作是 zipWith 的 syntax sugar，那么 Fibonacci 数列自然也是可以通过
直接使用 zipWith 来实现了，如下:
-- fib4.hs
-- fibonacci sequence
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
