列表是如何在 Haskell (GHC) 中实现的? [英] How are lists implemented in Haskell (GHC)?

问题描述

我只是对 Haskell 中列表的一些确切实现细节感到好奇(特定于 GHC 的答案很好)——它们是幼稚的链表，还是有任何特殊的优化?更具体地说:

I was just curious about some exact implementation details of lists in Haskell (GHC-specific answers are fine)--are they naive linked lists, or do they have any special optimizations? More specifically:

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

1. Do length and (!!) (for instance) have to iterate through the list?
2. If so, are their values cached in any way (i.e., if I call length twice, will it have to iterate both times)?
3. Does access to the back of the list involve iterating through the whole list?
4. Are infinite lists and list comprehensions memoized? (i.e., for fib = 1:1:zipWith (+) fib (tail fib), will each value be computed recursively, or will it rely on the previous computed value?)

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

Any other interesting implementation details would be much appreciated. Thanks in advance!

推荐答案

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

Lists have no special operational treatment in Haskell. They are defined just like:

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

只是有一些特殊的符号:[a] 表示 List a，[] 表示 Nil 和 (:) 用于 Cons.如果您定义相同并重新定义所有操作，您将获得完全相同的性能.

Just with some special notation: [a] for List a, [] for Nil and (:) for Cons. If you defined the same and redefined all the operations, you would get the exact same performance.

因此，Haskell 列表是单链接的.由于懒惰，它们经常被用作迭代器.sum [1..n] 在常量空间中运行，因为这个列表中未使用的前缀会随着求和的进行而被垃圾收集，并且直到需要它们才会生成尾部.

Thus, Haskell lists are singly-linked. Because of laziness, they are often used as iterators. sum [1..n] runs in constant space, because the unused prefixes of this list are garbage collected as the sum progresses, and the tails aren't generated until they are needed.

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

As for #4: all values in Haskell are memoized, with the exception that functions do not keep a memo table for their arguments. So when you define fib like you did, the results will be cached and the nth fibonacci number will be accessed in O(n) time. However, if you defined it in this apparently equivalent way:

-- 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` (
 -> fib n + tailF fib n))

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

(Take a moment to note the similarity to your definition)

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

Then the results are not shared and the nth fibonacci number will be accessed in O(fib n) (which is exponential) time. You can convince functions to be shared with a memoization library like data-memocombinators.

这篇关于列表是如何在 Haskell (GHC) 中实现的?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！