Send Beginners mailing list submissions to
[email protected]
To subscribe or unsubscribe via the World Wide Web, visit
http://www.haskell.org/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
[email protected]
You can reach the person managing the list at
[email protected]
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. Question about data structures (Russ Abbott)
2. Re: Question about data structures (Daniel Fischer)
3. Re: Question about data structures (Russ Abbott)
4. Re: Question about data structures (Daniel Schoepe)
5. Re: Question about data structures (Daniel Fischer)
6. Re: Question about data structures (Russ Abbott)
----------------------------------------------------------------------
Message: 1
Date: Wed, 24 Nov 2010 11:40:02 -0800
From: Russ Abbott <[email protected]>
Subject: [Haskell-beginners] Question about data structures
To: beginners <[email protected]>
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
I would appreciate some advice about the best way to manipulate data
structures in Haskell.
Let's assume I have what in an OO language would be a class with a number of
instance variables. When I want to change one of the values of one of those
instance variables in Haskell I must rebuild the entire structure. Even
worse, if one of those instance variables is a reference to another data
structure, then when I change that referenced data structure, I am forced to
rebuild my top level variable. For example.
data Struct1 = Struct1 {var1 :: Struct11, var2 :: Struct1, ... }
data Struct11 = Struct11 {var11 :: ... }
Let's assume I have x :: Struct1 and that I change the value of var11 . var1
$ x. Doesn't that require that I rebuild x?
Is there a better way?
Thanks.
*
-- Russ*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20101124/4603d844/attachment-0001.html
------------------------------
Message: 2
Date: Wed, 24 Nov 2010 21:26:34 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Question about data structures
To: [email protected], [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Wednesday 24 November 2010 20:40:02, Russ Abbott wrote:
> I would appreciate some advice about the best way to manipulate data
> structures in Haskell.
>
> Let's assume I have what in an OO language would be a class with a
> number of instance variables. When I want to change one of the values
> of one of those instance variables in Haskell I must rebuild the entire
> structure. Even worse, if one of those instance variables is a
> reference to another data structure, then when I change that referenced
> data structure, I am forced to rebuild my top level variable. For
> example.
>
> data Struct1 = Struct1 {var1 :: Struct11, var2 :: Struct1, ... }
> data Struct11 = Struct11 {var11 :: ... }
>
> Let's assume I have x :: Struct1 and that I change the value of var11 .
> var1 $ x. Doesn't that require that I rebuild x?
No, x doesn't change.
What you probably mean is
y = x{ var1 = (var1 x){ var11 = somethingNew } }
Then y shares all fields except var1 with x, the var1 field of y must be
built, but it shares everything except the var11 field with (var1 x).
Since values are immutable, the bulk of the structure is shared between an
original value and a modified one (except if the structures are very small
so there's little to share, but then building is cheap, or the modification
changes very much of the structure, but then the modification would be
expensive also in a language with mutable values).
>
> Is there a better way?
>
> Thanks.
> *
> -- Russ*
------------------------------
Message: 3
Date: Wed, 24 Nov 2010 13:12:37 -0800
From: Russ Abbott <[email protected]>
Subject: Re: [Haskell-beginners] Question about data structures
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
Cool. I wasn't aware of that notation. It doesn't quite get to the issue
though.
The problem I'm concerned about is the need to define y in the first place.
If one is chasing through a data structure and finds a need to change
something buried within it, it seems necessary to rebuild everything
that includes the changed thing. That is, I can't change a component of
somethingNew without creating y. The point is there's nothing about x that
changed, and there may be nothing about (var1 x) that changed, and there may
be nothing about var11 . var1 $ x that changed, etc. Yet one is apparently
forced to keep track of and reconstruct all those elements.
Another example is to imagine a Tree in which the leaves contain "objects."
If I want to change a property of one of those leaf objects, I am forced to
rebuild all the ancestor nodes of that leaf down to rebuilding the root.
One way to avoid that is for the leaves to refer to their objects through a
Map. Then changing a leaf object requires only that the value associated
with key represented by the leaf be (re-)inserted into the Map. The Tree
itself need not change at all.
But that trick isn't always available. In the example we are talking about
we can't make a Map where they keys are the instance variable names and the
values are their values. That would seem to do the job, but since the
values are of different types, we can't create such a Map.
So now what?
*
-- Russ *
On Wed, Nov 24, 2010 at 12:26 PM, Daniel Fischer
<[email protected]>wrote:
> On Wednesday 24 November 2010 20:40:02, Russ Abbott wrote:
> > I would appreciate some advice about the best way to manipulate data
> > structures in Haskell.
> >
> > Let's assume I have what in an OO language would be a class with a
> > number of instance variables. When I want to change one of the values
> > of one of those instance variables in Haskell I must rebuild the entire
> > structure. Even worse, if one of those instance variables is a
> > reference to another data structure, then when I change that referenced
> > data structure, I am forced to rebuild my top level variable. For
> > example.
> >
> > data Struct1 = Struct1 {var1 :: Struct11, var2 :: Struct1, ... }
> > data Struct11 = Struct11 {var11 :: ... }
> >
> > Let's assume I have x :: Struct1 and that I change the value of var11 .
> > var1 $ x. Doesn't that require that I rebuild x?
>
> No, x doesn't change.
> What you probably mean is
>
> y = x{ var1 = (var1 x){ var11 = somethingNew } }
>
> Then y shares all fields except var1 with x, the var1 field of y must be
> built, but it shares everything except the var11 field with (var1 x).
>
> Since values are immutable, the bulk of the structure is shared between an
> original value and a modified one (except if the structures are very small
> so there's little to share, but then building is cheap, or the modification
> changes very much of the structure, but then the modification would be
> expensive also in a language with mutable values).
>
> >
> > Is there a better way?
> >
> > Thanks.
> > *
> > -- Russ*
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20101124/b463c22e/attachment-0001.html
------------------------------
Message: 4
Date: Wed, 24 Nov 2010 22:26:39 +0100
From: Daniel Schoepe <[email protected]>
Subject: [Haskell-beginners] Re: Question about data structures
To: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset=utf-8
Russ Abbott <[email protected]> writes:
> Cool. I wasn't aware of that notation. Â It doesn't quite get to the
> issue though.
>
> The problem I'm concerned about is the need to define y in the first
> place. If one is chasing through a data structure and finds a need to
> change something buried within it, it seems necessary to rebuild
> everything that includes the changed thing.  That is, I can't change
> a component of somethingNew without creating y. The point is there's
> nothing about x that changed, and there may be nothing about (var1 x)
> that changed, and there may be nothing about var11 . var1 $ x that
> changed, etc. Yet one is apparently forced to keep track of and
> reconstruct all those elements.Â
>
The data-accessor package makes those changes more syntactically
lightweight:
http://hackage.haskell.org/package/data-accessor
http://hackage.haskell.org/package/data-accessor-template
> Another example is to imagine a Tree in which the leaves contain
> "objects." Â If I want to change a property of one of those leaf
> objects, I am forced to rebuild all the ancestor nodes of that leaf
> down to rebuilding the root.
You could define a function like mapTree, or mapLeaves along with the
data structure, that recurses over the tree and applies a function to
its components. This also allows changing a leaf without going through
the entire tree manually:
> mapLeaves (\leaf -> if leaf == wantedLeaf then modifiedLeaf else leaf) tree
If you're concerned about memory usage when "rebuilding" the data
structures, Daniel Fischer's previous statements still apply: The
modified data structure will share everything with the old one except
for the changed parts.
Regards,
Daniel
------------------------------
Message: 5
Date: Wed, 24 Nov 2010 22:52:29 +0100
From: Daniel Fischer <[email protected]>
Subject: Re: [Haskell-beginners] Question about data structures
To: [email protected]
Cc: [email protected]
Message-ID: <[email protected]>
Content-Type: text/plain; charset="utf-8"
On Wednesday 24 November 2010 22:12:37, Russ Abbott wrote:
> Cool. I wasn't aware of that notation. It doesn't quite get to the
> issue though.
>
> The problem I'm concerned about is the need to define y in the first
> place. If one is chasing through a data structure and finds a need to
> change something buried within it, it seems necessary to rebuild
> everything that includes the changed thing.
In general, values are immutable, so you can't "change something buried
within it". You have to build a new value containing some of the old stuff
and a new part. Building the new value usually consists mostly of copying a
couple of pointers (plus building the new part of course), so isn't too
expensive normally.
You can have mutable values in the IO or (ST s) monads, if you need them.
> That is, I can't change a
> component of somethingNew without creating y. The point is there's
> nothing about x that changed,
The thing with the changed component is not x anymore.
> and there may be nothing about (var1 x)
> that changed, and there may be nothing about var11 . var1 $ x that
> changed, etc. Yet one is apparently forced to keep track of and
> reconstruct all those elements.
The compiler takes care of that.
>
> Another example is to imagine a Tree in which the leaves contain
> "objects." If I want to change a property of one of those leaf objects,
You can't in general, the thing with a different property is a different
object.
> I am forced to rebuild all the ancestor nodes of that leaf down to
> rebuilding the root.
Yes (well, not you, the compiler does it), except if your tree contains
mutable objects (IORefs/STRefs for example).
>
> One way to avoid that is for the leaves to refer to their objects
> through a Map. Then changing a leaf object requires only that the value
> associated with key represented by the leaf be (re-)inserted into the
> Map. The Tree itself need not change at all.
Oh, it will. If you change a Map, you get a new one, thus you get a new
tree containing the new Map.
>
> But that trick isn't always available. In the example we are talking
> about we can't make a Map where they keys are the instance variable
> names and the values are their values. That would seem to do the job,
> but since the values are of different types, we can't create such a Map.
>
> So now what?
Well, what's the problem with the compiler copying some nodes?
Normally, that doesn't cost very much performance, if it does in your case,
we'd need to know more to suggest the best way to go.
> *
> -- Russ *
>
------------------------------
Message: 6
Date: Wed, 24 Nov 2010 14:02:57 -0800
From: Russ Abbott <[email protected]>
Subject: Re: [Haskell-beginners] Question about data structures
To: Daniel Fischer <[email protected]>
Cc: [email protected]
Message-ID:
<[email protected]>
Content-Type: text/plain; charset="iso-8859-1"
OK. So putting a Map at Leaf nodes doesn't solve the problem. (Apparently
I haven't been able to communicate what I see as the problem.)
The problem that I'm trying to get to is the need to write excessive code
for something that would require a lot less code in an OO world. It's not a
matter of execution time or space. It's a matter of the amount of code one
is required to write.
*
-- Russ *
On Wed, Nov 24, 2010 at 1:52 PM, Daniel Fischer <[email protected]>wrote:
> On Wednesday 24 November 2010 22:12:37, Russ Abbott wrote:
> > Cool. I wasn't aware of that notation. It doesn't quite get to the
> > issue though.
> >
> > The problem I'm concerned about is the need to define y in the first
> > place. If one is chasing through a data structure and finds a need to
> > change something buried within it, it seems necessary to rebuild
> > everything that includes the changed thing.
>
> In general, values are immutable, so you can't "change something buried
> within it". You have to build a new value containing some of the old stuff
> and a new part. Building the new value usually consists mostly of copying a
> couple of pointers (plus building the new part of course), so isn't too
> expensive normally.
>
> You can have mutable values in the IO or (ST s) monads, if you need them.
>
> > That is, I can't change a
> > component of somethingNew without creating y. The point is there's
> > nothing about x that changed,
>
> The thing with the changed component is not x anymore.
>
> > and there may be nothing about (var1 x)
> > that changed, and there may be nothing about var11 . var1 $ x that
> > changed, etc. Yet one is apparently forced to keep track of and
> > reconstruct all those elements.
>
> The compiler takes care of that.
>
> >
> > Another example is to imagine a Tree in which the leaves contain
> > "objects." If I want to change a property of one of those leaf objects,
>
> You can't in general, the thing with a different property is a different
> object.
>
> > I am forced to rebuild all the ancestor nodes of that leaf down to
> > rebuilding the root.
>
> Yes (well, not you, the compiler does it), except if your tree contains
> mutable objects (IORefs/STRefs for example).
>
> >
> > One way to avoid that is for the leaves to refer to their objects
> > through a Map. Then changing a leaf object requires only that the value
> > associated with key represented by the leaf be (re-)inserted into the
> > Map. The Tree itself need not change at all.
>
> Oh, it will. If you change a Map, you get a new one, thus you get a new
> tree containing the new Map.
>
> >
> > But that trick isn't always available. In the example we are talking
> > about we can't make a Map where they keys are the instance variable
> > names and the values are their values. That would seem to do the job,
> > but since the values are of different types, we can't create such a Map.
> >
> > So now what?
>
> Well, what's the problem with the compiler copying some nodes?
> Normally, that doesn't cost very much performance, if it does in your case,
> we'd need to know more to suggest the best way to go.
>
> > *
> > -- Russ *
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
http://www.haskell.org/pipermail/beginners/attachments/20101124/e9cf6707/attachment.html
------------------------------
_______________________________________________
Beginners mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/beginners
End of Beginners Digest, Vol 29, Issue 35
*****************************************
