[Haskell-beginners] 2 Questions: mutable data and copying results

C Gosch ch.gosch at googlemail.com
Tue Aug 17 10:08:49 EDT 2010


Hi Johan,
thanks for the quick answer!

2010/8/17 Johan Tibell <johan.tibell at gmail.com>
      The second question is this: say I have some functions working with a
data type, say a graph.

> Some of them might want to change the graph and return a new graph as a
>> result.
>> If they change say only one graph node, it would be extremely bad for
>> performance if the whole graph got copied
>> any time such a change takes place. Is the compiler smart enough to make
>> the code only copy the parts
>> that have changed (copying lazily, so to speak)? Is that even possible?
>>
>
> Since the graph is immutable most of the nodes in the new graph are shared
> with nodes in the old graph. This is know as path copying and is everywhere
> persistent ("immutable") data structures are used. Updating a data structure
> (e.g. a tree) typically requires O(log n) nodes to be copied.
>
>
So that means the compiler figures this out for my own data structures, or
do I have to take care that copying is done this way?
Sorry for my ignorance, I'm still learning :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100817/81b305ec/attachment.html


More information about the Beginners mailing list