Phlex wrote:
Donald Bruce Stewart wrote:
Imagine updating a node in a tree by just detaching and reattaching a pointer.
[1] [1] / \ / \ [2] [3] update node 5 [2] [3] / \ with value 7 / \ [4] [5] [4] *
and share the rest of the structure. Since the rest isn't mutable anyway, you can share all over.
That's precisely the thing i don't understand. In order to update node 3 with a new pointer, i need to mutate it, so i need to recreate it, and so on up to node 1.
Yes, that's correct, I think Dons shared a bit too much here :) [1] [1'] / \ / \ [2] [3] update node 5 [2] [3'] / \ / \ [4] [5] [4] [5'] You have to recreate all nodes that point directly or indirectly to 5, but you can share all the other nodes like 2 and 4 that have no forward pointers to 5. Note that creating new nodes is dead simple, there's no effort involved on the programmer's part. Here's an example that rotates the top of a binary tree: data Tree a = Leaf a | Node (Tree a) (Tree a) rotateRight :: Tree a -> Tree a rotateRight (Node (Node a b) c) = Node a (Node b c) The top two nodes are recreated with the constructor Node but a,b and c are shared.
Now in this example, it's ok since that's a regular tree and the process can be automated, but when each node has a different type, it can become quite hairy.
Yes and no. The point is that if you can't automate it, you have to code it by hand anyway which constitutes most of the hairiness. But I know what you mean and there's a nice way to do that with multi-parameter type classes. Let's assume a data structure data Universe = Universe [Galaxy] data Galaxy = Galaxy [Planet] data Planet = Planet { name :: String, size :: Double } The insight is that in order to reference a planet inside the universe structure, you have to know the path from the top. In other words, you have to know that's it's the 2nd planet from the 4th galaxy before you look up its name. If you don't throw that information away, you can use it to update it as well. In effect, the Universe behaves like a finite map with composite keys. {-# OPTIONS_GHC -fglasgow-exts -#} import Prelude hiding (lookup) class Map map key a | map key -> a where lookup :: key -> map -> Maybe a adjust :: (a -> a) -> key -> map -> map instance Map [a] Int a where lookup 0 [x] = Just x lookup 0 _ = Nothing lookup k (x:xs) = lookup (k-1) xs lookup _ _ = Nothing adjust f 0 [x] = [f x] adjust _ 0 xs = error "Index out of range" adjust f k (x:xs) = x : adjust f (k-1) xs adjust f _ xs = error "Index out of range" instance Map Universe Int Galaxy where lookup k (Universe gs) = lookup k gs adjust f k (Universe gs) = Universe (adjust f k gs) instance Map Galaxy Int Planet where lookup k (Galaxy ps) = lookup k ps adjust f k (Galaxy ps) = Galaxy (adjust f k ps) instance (Map m k m', Map m' k' a) => Map m (k,k') a where lookup (k,k') m = lookup k m >>= lookup k' adjust f (k,k') m = adjust (adjust f k') k m You can lookup the 2nd planet in the 4th galaxy with lookup (4,2) universe :: Maybe Planet and you can update it via adjust (\planet -> planet {name = "Earth"}) (4,2) universe Thanks to type-classes and overloading, you can still access single galaxies with lookup 4 universe :: Maybe Galaxy Regards, apfelmus