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

[Chaddaï Fouché]

On Tue, Aug 17, 2010 at 4:08 PM, C Gosch <ch.gosch at googlemail.com> wrote:
>> 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 :)


In fact this is not even a case of optimization by the compiler (it
doesn't have to "figure it out") but simply a consequence of the
evaluation model chosen for Haskell. Think of the "delete" function on
list for instance :

> delete _ [] = []
> delete e (x:xs) = if e == x then xs else x : delete e xs

It delete the first occurrence of e in the list. If you follow the
logic of this code, you'll see that the part of the list after the
first occurrence of e will be shared with the result of delete. This
is automatic and apparent in the code since you said "if x == e then
_xs_", in most language you could do the same, but you would then have
to be very cautious since modification of your old list would also
change your new list (and only if you modified the part after the
first "e"), making this a very dangerous function and in practice this
solution wouldn't be proposed by a sane library. In Haskell this
function is perfectly safe since you _can't_ modify the old list, it
is immutable.

When you understand this, you'll see that there's plenty of
interesting data structures that allow manipulations to share the
greatest part of the structure thus allowing to efficiently use
immutable data structure in many more situation than you would have
thought. Chris Okasaki "Purely Functional Data Structure" is an
excellent introduction to this world (where the efficient data
structure may not be the same as in your imperative programs).

-- 
Jedaï