At this point, you may be wondering why Haskell uses singly linked lists so much, when one might think an array/vector type might be more generally useful.

The thing about functional languages, and in particular pure functional languages such as Haskell, is that you don't generally have things like looping constructs; instead, you represent your data in a form which implies such a construct. In particular, when you might use a for/foreach loop in other languages, in a functional language you use a singly linked list and a map or fold over the list. (Some object-oriented languages do this as well; consider the "each" method in Smalltalk or Ruby.)

In a pure functional language like Haskell, this can lead to optimizations you would not get from an explicit foreach loop: since values are immutable and can be generated lazily, a compiler can more easily recognize that it doesn't need to generate or maintain a list at all but just consume values as they are generated. Languages that use foreach loops often can only do this optimization in specific cases: for example, in Perl a foreach loop on a constant numeric range is optimized this way, but not others; in Ruby, it's much harder to do this at all because the "each" method needs to be resolved to a list object; and commercial Smalltalk implementations generally have quite a lot of behind the scenes intelligence to try to recognize and optimize these kinds of cases without falling into the same trap as e.g. Ruby.
--