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

Asked 2009-03-01T02:51:35.810

23

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?

data-structures functional-programming immutability

Edit Report

1 Answer

1

Functional programs tend to put more emphasis on recursion. This, in turn, suggests the use of recursive algorithms and recursive data structures. Both lists and trees are recursive structures (the "next" link on a list is another list, and the children of a tree node are both trees).

You may want to reconsider if you're looking at extra expense on an algorithm. Why does the hash table (which is O(1) for a non-recursive algorithm) incur an extra expense? What advantage are you gaining by using it, as opposed to a tree or list?

answered 2009-03-01T03:49:33.767

Your Answer