我只是对 Haskell 中列表的一些具体实现细节感到好奇(GHC 特定的答案很好)——它们是朴素的链表,还是有任何特殊的优化?更具体地说:
length
和(!!)
(例如)是否必须迭代列表?- 如果是这样,它们的值是否以任何方式缓存(即,如果我调用
length
两次,是否必须迭代两次)? - 访问列表后面是否涉及迭代整个列表?
- 无限列表和列表推导式是否已被内存? (即,对于
fib = 1:1:zipWith (+) fib (tail fib)
,每个值是递归计算的,还是依赖于先前计算的值?)
任何其他有趣的实现细节将不胜感激。提前致谢!
最佳答案
列表在 Haskell 中没有特殊的操作处理。它们的定义如下:
data List a = Nil | Cons a (List a)
只需使用一些特殊符号:[a]
表示 List a
,[]
表示 Nil
和 (:)
代表缺点
。如果您定义相同的操作并重新定义所有操作,您将获得完全相同的性能。
因此,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 .
关于haskell - Haskell (GHC) 中的列表是如何实现的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2688986/