Haskell（GHC）是如何实现的？
我只是好奇Haskell中的一些确切的实现细节（GHC特定的答案是好的） – 他们是天真的链表，还是他们有任何特殊的优化？ 进一步来说：
- 做
length和(!!)（例如）必须遍历列表？ - 如果是这样，他们的值是以任何方式caching（即，如果我叫两次，它将不得不迭代两次）？
- 访问列表后面是否涉及遍历整个列表？
- 是无限的列表和列表理解memoized？ （即，对于
fib = 1:1:zipWith (+) fib (tail fib)，每个值是recursion计算还是依赖于以前的计算值？）
任何其他有趣的实现细节将不胜感激。 提前致谢！
在Haskell中列表没有特殊的操作处理。 它们的定义如下：
data List a = Nil | Cons a (List a)
只是有一些特殊的符号： [a] List a ， [] Nil和(:)为Cons 。 如果定义相同并重新定义了所有操作，则会获得完全相同的性能。
因此，Haskell列表是单链接的。 由于懒惰，他们经常用作迭代器。 sum [1..n]在恒定的空间中运行，因为这个列表的未使用的前缀是随着总和的推进而被垃圾回收的，并且尾巴在需要之前不会被生成。
至于＃4：Haskell中的所有值都被记忆了，除了函数没有为它们的参数保留备注表。 所以当你像你这样定义fib时，结果将被caching，第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）（这是指数）时间被访问。 您可以说服函数与数据memocombinators这样的memoization库共享。
如果是这样，他们的值是以任何方式caching（即，如果我叫两次，它将不得不迭代两次）？
GHC不执行完整的通用子expression式消除 。 例如：
{-# 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 ，所以比bbbbbbbbb慢2 bbbbbbbbb 。）
据我所知（我不知道这是多lessGHC具体）
-
length和(!!)DO必须遍历列表。 -
我不认为列表有任何特别的优化，但是有一种适用于所有数据types的技术。
如果你有类似的东西
foo xs = bar (length xs) ++ baz (length xs)那么
length xs将被计算两次。但是，如果你有
foo xs = bar len ++ baz len where len = length xs那么它只会被计算一次。
-
是。
-
是的，一旦计算了一个命名值的一部分，它就被保留，直到名称超出范围。 （语言不需要这个，但这是我理解实现的行为。）
