Are some data structures more suitable for functional programming than others?

Question

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?

Answer 1

The book Purely Functional Data Structures covers your questions in depth, and includes a great mix of theory and implementations primarily in ML - the appendix also contains Haskell implementations so you should be able to follow along with a bit of extra page turning. It is a pretty good (though difficult in parts) read if you are really interested in a thorough answer to your questions. Having said that I think ephemient gave a superb short answer.

edit: Steven Huwig provided a link to the thesis that the book started as. While I haven't read through it the only big thing missing (judging from the table of contents) are the Haskell implementations.

Answer 2

• Yes. Typically tuples, lists, and partially-evaluated functions are very common data structures in functional programming languages. Mutable data structures, like arrays and (real) hash tables, are used much less because they don't fit in as well with Haskell. SML (which is also functional, but not lazy) can use arrays more naturally than Haskell, but lists are still more common because they map well to recursive algorithms.
• I'm not sure how to answer this. A problem for who?
• There exist implementations of associative arrays ("hash table" equivalent) which can continue to share most of their underlying structure even after different updates. I believe GHC's Data.Map does; also, Edison has quite a few lazy/functional-friendly data structures.