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

[Johan Tibell]

Hi Christian!

On Tue, Aug 17, 2010 at 2:34 PM, C Gosch <ch.gosch at googlemail.com> wrote:

> I have two more beginner questions: I ran into texts mentioning types of
> "mutable" data.
> Does that mean the data is actually changed in place? How would I go about
> implementing such a data type,
> as I expect much higher performance in some applications? Do I do that with
> the Foreign module and Ptr
> types?
>

Yes, by mutable data we mean data that changes in place. There are several
ways to use mutable data in Haskell: mutable variables and arrays in the ST
monad, IORefs, MVars (for concurrent access), and Ptrs (although these
should mostly be used for foreign function calls).


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

-- Johan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/beginners/attachments/20100817/7d59fdb3/attachment-0001.html