How are lists implemented in Haskell (GHC)?
- by eman
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!