In functional programming since almost all data structure are immutable, when the state has to change a new structure is created. Does this mean a lot more memory usage? I know the object oriented programming paradigm well, now I'm trying to learn about the functional programming paradigm. The concept of everything being immutable confuses me. It would seem like the a program using immutable structures would require much more memory than a program with mutable structures. Am I even looking at this in the right way?
In functional programming, does having most of the data structures immutable require more memory usage?
9It can mean that, but most immutable data structures reuse the underlying data for the changes. Eric Lippert has a great blog series about immutability in C#– OdedDec 24, 2012 at 20:00
3I would take a look at Purely Functional Data Structures, It's a great book that is written by the same guy who wrote most of Haskell's container library (though the book is primarily SML)– daniel gratzerDec 25, 2012 at 0:23
1This answer, related to running time instead of memory consumption, may also be interesting for you: stackoverflow.com/questions/1990464/…– 9000Dec 25, 2012 at 3:10
1You might find this interesting: en.wikipedia.org/wiki/Static_single_assignment_form– Sean McSomethingFeb 13, 2013 at 17:13
The only correct answer to this is "sometimes". There are a lot of tricks that functional languages can use to avoid wasting memory. Immutability makes it easier to share data between functions, and even between data structures, since the compiler can guarantee that the data won't be modified. Functional languages tend to encourage the use of data structures that can be used efficiently as immutable structures (for instance, trees instead of hash tables). If you add laziness into the mix, like many functional languages do, that adds new ways to save memory (it also adds new ways of wasting memory, but I'm not going to go into that).
In functional programming since almost all data structure are immutable, when the state has to change a new structure is created. Does this mean a lot more memory usage?
That depends on the data structure, the exact changes you performed and, in some cases, the optimizer. As one example let's consider prepending to a list:
list2 = prepend(42, list1) // list2 is now a list that contains 42 followed // by the elements of list1. list1 is unchanged
Here the additional memory requirement is constant - so is the runtime cost of calling
prepend. Why? Because
prepend simply creates a new cell which has
42 as its head and
list1 as its tail. It does not have to copy or otherwise iterate over
list2 to achieve this. That is, except for the memory required to store
list2 reuses the same memory that is used by
list1. Since both lists are immutable, this sharing is perfectly safe.
Similarly, when working with balanced tree structures, most operations require only a logarithmic amount of additional space because everything, but one path of the tree may be shared.
For arrays the situation is a bit different. That's why, in many FP languages, arrays are not that commonly used. However, if you do something like
arr2 = map(f, arr1) and
arr1 is never used again after this line, a smart optimizer can actually create code that mutates
arr1 instead of creating a new array (without affecting the behavior of the program). In that case the performance will be as in an imperative language of course.
1Out of interest, which implementation of which languages do reuse space as you described near the end?– user7043Dec 24, 2012 at 21:33
@delnan At my university there was a research language called Qube, which did that. I don't know whether there's any used-in-the-wild language that does this, though. However Haskell's fusion can achieve the same effect in many cases.– sepp2kDec 24, 2012 at 22:43
Naive implementations would indeed expose this problem - when you create a new data structure instead of updating an existing one in-place, you have to have some overhead.
Different languages have different ways of dealing with this, and there are a few tricks most of them use.
One strategy is garbage collection. The moment the new structure has been created, or shortly after, references to the old structure go out of scope, and the garbage collector will pick it up instantly or soon enough, depending on the GC algorithm. This means that while there is still an overhead, it is only temporary, and won't grow linearly with the amount of data.
Another one is picking different kinds of data structures. Where arrays are the go-to list data structure in imperative languages (usually wrapped in some sort of dynamic-reallocation container such as
std::vector in C++), functional languages often prefer linked lists. With a linked list, a prepend operation ('cons') can reuse the existing list as the new list's tail, so all that really gets allocated is the new list head. Similar strategies exist for other types of data structures - sets, trees, you name it.
And then there's lazy evaluation, à la Haskell. The idea is that data structures you create aren't fully created immediately; instead, they are stored as "thunks" (you can think of these as recipes for constructing the value when it's needed). Only when the value is needed does the thunk get expanded into an actual value. This means that memory allocation can be deferred until evaluation is necessary, and at that point, several thunks can be combined in one memory allocation.
I only know a little about Clojure and it's Immutable Data Structures.
Clojure provides a set of immutable lists, vectors, sets and maps. Since they can't be changed, 'adding' or 'removing' something from an immutable collection means creating a new collection just like the old one but with the needed change. Persistence is a term used to describe the property wherein the old version of the collection is still available after the 'change', and that the collection maintains its performance guarantees for most operations. Specifically, this means that the new version can't be created using a full copy, since that would require linear time. Inevitably, persistent collections are implemented using linked data structures, so that the new versions can share structure with the prior version.
Graphically, we can represent something like this:
(def my-list '(1 2 3)) +---+ +---+ +---+ | 1 | ---> | 2 | ---> | 3 | +---+ +---+ +---+ (def new-list (conj my-list 0)) +-----------------------------+ +---+ | +---+ +---+ +---+ | | 0 | --->| | 1 | ---> | 2 | ---> | 3 | | +---+ | +---+ +---+ +---+ | +-----------------------------+
In addition to what has been said in other answers, I would like to mention the Clean programming language, which supports so-called unique types. I do not know this language but I suppose that unique types support some kind of "destructive update".
In other words, while the semantics of updating a state is that you create a new value from an old one by applying a function, the uniqueness constraint can allow the compiler to reuse data objects internally because it knows that the old value will not be referenced any more in the program after the new value has been produced.
For more details, see e.g. the Clean homepage and this wikipedia article