Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
6  
It 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# –  Oded Dec 24 '12 at 20:00
3  
I 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) –  jozefg Dec 25 '12 at 0:23
    
This answer, related to running time instead of memory consumption, may also be interesting for you: stackoverflow.com/questions/1990464/… –  9000 Dec 25 '12 at 3:10
    
You might find this interesting: en.wikipedia.org/wiki/Static_single_assignment_form –  Sean McSomething Feb 13 '13 at 17:13
add comment

5 Answers

up vote 23 down vote accepted

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).

share|improve this answer
add comment

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 42, 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.

share|improve this answer
1  
Out of interest, which implementation of which languages do reuse space as you described near the end? –  delnan Dec 24 '12 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. –  sepp2k Dec 24 '12 at 22:43
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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 | |
    +---+     | +---+      +---+      +---+ |
              +-----------------------------+
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.