列表在 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 之类的记忆库共享。