Haskell 的 List Comprehension 是如何工作的

Question

Haskell 的 List Comprehension 是如何工作的

    本文通过在 Haskell 中生成 Fibonacci 数列这个例子讨论了 Haskell 中 list comprehension 是如何转换为 Haskell Kernel 的，借此可以理解 Haskell 的 list comprehension 是如何工作的。所谓的 Haskell Kernel 或者 Kernel 是 Haskell 98 Report 中描述的一种简单的 Functional 语言，和 GHC 中的 Core 类似。

一、例子

    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 来实现:

2.         -- fib1.hs
3.         -- fibonacci sequence, DOESN'T WORK
4.         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 的位置试试:

2.         -- fib2.hs
3.         -- fibonacci sequence, DOESN'T WORK
4.         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 后就是：

2.         [ e | p <- l, Q ]       = let ok p = [ e | Q ]
3.                                              ok _ = []
4.                                          in concatMap ok l

复制代码
    其中 Q 是剩余的 qualifier。

    1) 对 fib1.hs 的解释

    按照上面的说法，

2.         -- fib1.hs
3.         fibs = 0 : 1 : [ x + y | x <- fibs, y <- tail fibs ]

复制代码
    会被转换为:

2.         fibs = 0 : 1 :
3.             let ok x = [ x + y | y <- tail fibs ]
4.                  ok _ = []
5.             in concatMap ok fibs

复制代码
    而 ok x = [ x + y | y <- tail fibs ] 会进一步被转换为:

2.         ok x = let ok1 y = [ x + y ]
3.                         ok1 _ = []
4.                    in concatMap ok1 (tail fibs)

复制代码
    fibs 的第一、第二个数字分别是 0 和 1，那第三个呢？第三个数字是通过如下方式获取的:

2.              head $ ok 0               -- x = 0
3.         =   head $ ok1 1            -- y = 1
4.         =   head $ [ 0 + 1 ]        -- ok1 的定义

复制代码
    因此第三个数字为 1。第四个数字通过如下方式获取:

2.              second $ ok 0             -- x = 0；x 的值不变
3.         =   second $ ok1 1          -- y = 1; y 的值仍为 1
4.         =   second $ [_, 0 + 1]

复制代码
    因此第四个数字仍为 1。

    实际上，由于 fibs 本身是无穷数列，因此 fibs 的第三到第N个数字就是如下数列的第一到第(N-2)个数字:

2.              ok 0
3.         =   concatMap ok1 (tail fibs)
4.         =   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 扩展，则可采用如下实现:

2.         -- fib3.hs
3.         {-# LANGUAGE ParallelListComp #-}
5.         module Fibonacci where
7.         -- fibonacci sequence
8.         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)

[ 本帖最后由 MMMIX 于 2008-10-11 23:22 编辑 ]

Answer 1

原帖由 flw 于 2008-10-12 08:55 发表

我一般都是在 vim 里面调整好，然后复制上来。
只要 BBS 用的是等宽字体，并且发帖时使用了 code 标签，那么这样做一般可以保证对齐不变。

我试了下，这样也达不到预期效果(拷贝过来时就歪了 :em11: )，不知道怎么回事。

[ 本帖最后由 MMMIX 于 2008-10-12 10:49 编辑 ]

Answer 2

原帖由 MMMIX 于 2008-10-11 23:27 发表

不过在编辑窗口太难预测最终的显示结果了，这给格式调整带来了许多问题。

我一般都是在 vim 里面调整好，然后复制上来。
只要 BBS 用的是等宽字体，并且发帖时使用了 code 标签，那么这样做一般可以保证对齐不变。

Answer 3

原帖由 flw 于 2008-10-11 20:31 发表

呵呵，我给你改成用新宋体，看上去比以前好一些了。

不过在编辑窗口太难预测最终的显示结果了，这给格式调整带来了许多问题。

Answer 4

原帖由 MMMIX 于 2008-10-11 15:17 发表
代码实在太难对齐了 :em11:

呵呵，我给你改成用新宋体，看上去比以前好一些了。

Answer 5

代码实在太难对齐了 :em11: