Are Haskell lists actually implemented as linked lists? I would have thought they were compiled as "array lists" like Python (arrays of pointers, but with extra space pre-allocated to make extending cheap)
> Are Haskell lists actually implemented as linked lists?
Yes, the type "[]" from the Prelude is a linked list.
> I would have thought they were compiled as "array lists" like Python (arrays of pointers, but with extra space pre-allocated to make extending cheap)
No, and that doesn't quite work for immutable types, since there's nothing you can do with the "extra space pre-allocated". You can't mutate it! Nonetheless, rope-like structures will work fine, and there are surely plenty of them floating around.
The main point of linked lists in Haskell is that you can compute them lazily. So a Haskell list is more like a python "generator", a callback function that gives you the next element. This is nice because we don't need a separate interface for generators, streams, ranges, etc.; they are all just lists in Haskell.
If you force computation of a whole list sand save it, the representation in memory would be just a basic linked list. But that's not really recommended as it's a quite inefficient way to store and work with non-tiny amounts data.
There are also true arrays in Haskell which are not very useful due to reasons.
Perhaps the most flexible structures we have are various tree-based array implementations, similar to Clojure's arrays.
