如何在haskell(ghc)中实现列表?

名单在哈斯克尔没有特殊的操作处理。它们的定义如下:

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

只是有一些特殊的符号: [a] 对于 List a , [] 对于 Nil 和 (:) 对于 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个fibonacci数将在o(fib n)(指数)时间内被访问。你可以说服函数与一个像 data-memocombinators .

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

GHC does not perform full 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 需要保留在 AAAAAAAA ,比 bbbbbbbbb )

据我所知(我不知道这其中有多少是针对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. 是的,一旦计算了命名值的一部分,它将被保留,直到名称超出范围。 (语言不需要这样做,但这是我理解实现行为的方式。)