How are lists implemented in Haskell (GHC)?

Posted by eman on Stack Overflow See other posts from Stack Overflow or by eman
Published on 2010-04-22T07:35:17Z Indexed on 2010/04/22 9:03 UTC
Read the original article Hit count: 481

Filed under:
|
|

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. 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!

© Stack Overflow or respective owner

Related posts about haskell

Related posts about linked-list