48

我只是对 Haskell 中列表的一些确切实现细节感到好奇(GHC 特定的答案很好)——它们是简单的链表,还是有任何特殊的优化?进一步来说:

  1. 是否length(!!)(例如)必须遍历列表?
  2. 如果是这样,它们的值是否以任何方式缓存(即,如果我调用length两次,是否必须两次迭代)?
  3. 访问列表后面是否涉及遍历整个列表?
  4. 是否记住了无限列表和列表推导?(即,对于fib = 1:1:zipWith (+) fib (tail fib),每个值是递归计算的,还是依赖于先前计算的值?)

任何其他有趣的实现细节将不胜感激。提前致谢!

4

3 回答 3

43

列表在 Haskell 中没有特殊的操作处理。它们的定义就像:

data List a = Nil | Cons a (List a)

只是有一些特殊的符号:[a]for List a[]forNil(:)for Cons。如果您定义相同并重新定义所有操作,您将获得完全相同的性能。

因此,Haskell 列表是单链接的。由于惰性,它们经常被用作迭代器。 sum [1..n]在恒定空间中运行,因为此列表中未使用的前缀会随着总和的进行而被垃圾收集,并且在需要它们之前不会生成尾部。

至于#4: Haskell 中的所有值都被记忆,除了函数不为它们的参数保留一个备忘录表。所以当你fib像你一样定义时,结果将被缓存,第 n 个斐波那契数将在 O(n) 时间内被访问。但是,如果您以这种明显等效的方式定义它:

-- Simulate infinite lists as functions from Integer
type List a = Int -> a

cons :: a -> List a -> List a
cons x xs n | n == 0    = x
            | otherwise = xs (n-1)

tailF :: List a -> List a
tailF xs n = xs (n+1)

fib :: List Integer
fib = 1 `cons` (1 `cons` (\n -> fib n + tailF fib n))

(花点时间注意与您的定义的相似性)

然后结果不共享,第 n 个斐波那契数将在 O(fib n)(指数)时间内访问。您可以说服函数与诸如data-memocombinators 之类的记忆库共享。

于 2010-04-22T08:53:19.553 回答
12

据我所知(我不知道其中有多少是特定于 GHC 的)

  1. length并且(!!)必须遍历列表。

  2. 我认为列表没有任何特殊优化,但有一种技术适用于所有数据类型。

    如果你有类似的东西

    foo xs = bar (length xs) ++ baz (length xs)
    

    然后length xs将计算两次。

    但是如果你有

    foo xs = bar len ++ baz len
      where len = length xs
    

    那么它只会被计算一次。

  3. 是的。

  4. 是的,一旦计算了命名值的一部分,它就会被保留,直到名称超出范围。(语言不需要这个,但这是我理解实现行为的方式。)

于 2010-04-22T08:03:20.267 回答
11

如果是这样,它们的值是否以任何方式缓存(即,如果我调用 length 两次,是否必须两次迭代)?

GHC 不执行完整的 Common Subexpression Elimination。例如:

{-# NOINLINE aaaaaaaaa #-}
aaaaaaaaa :: [a] -> Int
aaaaaaaaa x = length x + length x

{-# NOINLINE bbbbbbbbb #-}
bbbbbbbbb :: [a] -> Int
bbbbbbbbb x = l + l where l = length x

main = bbbbbbbbb [1..2000000] `seq` aaaaaaaaa [1..2000000] `seq` return ()

给予-ddump-simpl

Main.aaaaaaaaa [NEVER Nothing] :: forall a_adp.
                                  [a_adp] -> GHC.Types.Int
GblId
[Arity 1
 NoCafRefs
 Str: DmdType Sm]
Main.aaaaaaaaa =
  \ (@ a_ahc) (x_adq :: [a_ahc]) ->
    case GHC.List.$wlen @ a_ahc x_adq 0 of ww_anf { __DEFAULT ->
    case GHC.List.$wlen @ a_ahc x_adq 0 of ww1_Xnw { __DEFAULT ->
    GHC.Types.I# (GHC.Prim.+# ww_anf ww1_Xnw)
    }
    }

Main.bbbbbbbbb [NEVER Nothing] :: forall a_ado.
                                  [a_ado] -> GHC.Types.Int
GblId
[Arity 1
 NoCafRefs
 Str: DmdType Sm]
Main.bbbbbbbbb =
  \ (@ a_adE) (x_adr :: [a_adE]) ->
    case GHC.List.$wlen @ a_adE x_adr 0 of ww_anf { __DEFAULT ->
    GHC.Types.I# (GHC.Prim.+# ww_anf ww_anf)
    }

注意aaaaaaaaa调用GHC.List.$wlen两次。

(实际上,因为x需要保留在 中aaaaaaaaa,所以比 慢了 2x 以上bbbbbbbbb。)

于 2010-04-22T08:54:45.370 回答