Haskell（GHC）中如何实现列表？ [英] How are lists implemented in Haskell (GHC)?

问题描述

我只是对Haskell中列表的确切实现细节感兴趣（GHC特定的答案很好） - 它们是天真的链表吗？还是它们有特殊的优化？更具体地说：

1. 做长度和（!! ）（例如）必须遍历列表？


2. 如果是这样，它们的值是以任何方式缓存的（例如，如果我调用长度两次，它是否必须迭代两次）？


3. 访问列表后面是否涉及迭代整个列表？
>

4. 记忆无限的列表和列表解析吗？ （即，对于 fib = 1：1：zipWith（+）fib（tail fib），每个值是递归计算还是依赖于以前的计算值？ ）

其他有趣的实现细节将不胜感激。在此先感谢！

解决方案

Haskell中没有特殊的操作处理。它们的定义如下：

 数据List a = Nil |缺点a（列表a）
  

只需要一些特殊的符号： [a] 为列出， [] 为无和（：）为缺点。如果你定义了相同的并重新定义了所有的操作，你将获得完全相同的性能。

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

至于＃4：Haskell中的所有值都是记忆的，除了函数不会为其参数保留备注表。所以当你像你一样定义 fib 时，结果将被缓存，第n个斐波那契数将在O（n）时间被访问。但是，如果你用这种明显相同的方式定义它：

   - 将无限列表模拟为Integer 
类型的函数列表a = Int  - > a 
 
 cons :: a  - >列表a  - >列出
 cons x xs n | n == 0 = x 
 |否则= xs（n-1）
 
 tailF ::列表a  - >列出一个
 tailF xs n = xs（n + 1）
 
 fib :: List Integer 
 fib = 1`cons`（1`cons`（\\\
  - > ;请注意与您的定义相似的地方） 
 
 
然后结果不被共享，第n个斐波纳契数将在O（fib n）（指数）时间被访问。您可以说服函数与像数据memocombinators 这样的memoization库共享。
 
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:

Do length and (!!) (for instance) have to iterate through the list?
If so, are their values cached in any way (i.e., if I call length twice, will it have to iterate both times)?
Does access to the back of the list involve iterating through the whole list?
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!
解决方案
Lists have no special operational treatment in Haskell.  They are defined just like:
data List a = Nil | Cons a (List a)
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.

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.

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` (\n -> fib n + tailF fib n))
(Take a moment to note the similarity to your definition)

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屋！