Are some data structures more suitable for functional programming than others?
- by Rob Lachlan
In Real World Haskell, there is a section titled "Life without arrays or hash tables" where the authors suggest that list and trees are preferred in functional programming, whereas an array or a hash table might be used instead in an imperative program.
This makes sense, since it's much easier to reuse part of an (immutable) list or tree when creating a new one than to do so with an array.
So my questions are:
Are there really significantly different usage patterns for data structures between functional and imperative programming?
If so, is this a problem?
What if you really do need a hash table for some application? Do you simply swallow the extra expense incurred for modifications?