Phlex:

Hello all,

I'm coming from the OO world, and there's something i don't quite understand in the way haskellers manipulate data (as all functional programmers i guess).

Let's say i have a deep nested data structure. Universe containing galaxies, containing solar systems, containing planets, containing countries, containing inhabitants, containing ...whatever.

Using the OO paradigm, once i get a reference to an inhabitant, i can update it quite easily (say by changing it's age), and that's the end of it.

On the other side, using the functional paradigm, it seems to me that the function i use in order to create a _new_ inhabitant with a different age will need to have knowledge of the country over it, the planet ..and so on up to the universe...as i need to update all these structures to reflect the change. This is pretty bad and most probably doesn't need to be like this.

So here I am hoping for you all to give me some pointers on how this is done "the functional way".

Nope, its not done like that. You share as much of the original structure as you can, as a general principle. 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. -- Don

Hello Phlex, Sunday, June 3, 2007, 11:41:29 AM, you wrote:

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 true

Now in this exemple, 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.

may be all that you need is structure update syntax? data Planet = Planet { age :: Double , weight :: Double ..... } updatePlanet p = p {age=(age p)*2} the same applies to updating nested structures. you just return updated structure on each level of processing -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Phlex writes:

The thing is, now that i have my planet p... i want to change it's age ... and get back the new state of the universe...

It is true, there is often a significant amount of "boilerplate" code needed to wrap a simple planet-change nested deep within a universe structure. There has been lots of research into easing the pain of creating this outer traversal code - search for "Scrap your boilerplate", "compos", "Play", "generic traversal" (in conjunction with "Haskell"). Regards, Malcolm

Hello Phlex, Sunday, June 3, 2007, 12:34:26 PM, you wrote:

So i need to do something like this :

changePlanetAge universe galaxy planet age = ...lots of code, returning a new universe And the same code for all functions updating any of the properties of my planet ... And the same code for all functions updating properties of a country on this planet...

while in the OO paradigm, i only need to do

changlePlanetAge planet age = ...just what you wrote

i think that problem is that you think in imperative paradigm. you want to update the whole universe structure each time when one children is born. the solution is to work on lower levels and change your algorithms to group changes in substructures together just one example: i parse config file in my program, i.e. i need function that returns setting given section and entry name: configData configFileContents sectionName entryName in imperative paradigm i will probably scan whole file each time i need an entry. in Haskell, i just split the whole config file into sections and extract entries from appropriate sections. imagine the opposite task, i will probably group entries together and concat them into sections and then concat sections into the whole config file while in imperative programming each new update will change the global structure change your mind, Neo! ;) -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Tillmann Rendel wrote:

Hello,

Phlex wrote:

...

changePlanetAge universe galaxy planet age = ...lots of code, returning a new universe And the same code for all functions updating any of the properties of my planet ... And the same code for all functions updating properties of a country on this planet...

In functional programming, problems of the kind "and the same code for all functions doing something related" are most often solved by introducing higher order functions. Let's try to decompose the problem as follows:

(1) change an attribute (2) change a planet by changing one of it's attributes (3) change a galaxy by changing one of it's planets (4) change an universe by changing one of it's galaxies.

(1) is done by functions of type (Attribute -> Attribute). We will construct them on the fly.

For (2), we need functions for each attribute of a planet.

type Name = String type Age = Integer data Planet = Planet Name Age

-- lift name changer to planet changer changeName :: (Name -> Name) -> Planet -> Planet changeName f (Planet n a) = Planet (f n) a

-- lift age changer to planet changer changeAge :: (Age -> Age) -> Planet -> Planet changeAge f (Planet n a) = Planet n (f a)

we need one of these functions for each attribute of each object. they correspond to setter-Methods in oop.

For (3), we have to select one of the planets in a galaxy to be changed. Let's assume integer indices for all planets.

type Galaxy = [Planet]

-- lift planet changer to galaxy changer changePlanet :: Integer -> (Planet -> Planet) -> Galaxy -> Galaxy changePlanet 0 f (p:ps) = f p : ps changePlanet n f (p:ps) = p : changePlanet (pred n) f ps

For (4), we have to select one of the galaxies in a universe to be changed. Let's assume integer indices again.

type Universe = [Galaxy]

-- lift galaxy changer to universe changer changeGalaxy :: Integer -> (Galaxy -> Galaxy) -> Universe -> Universe changeGalaxy 0 f (g:gs) = f g : gs changeGalaxy n f (g:gs) = g : changeGalaxy (pred n) f gs

Oups, that's the same as (3), up to renaming of types and variables. Let's refactor it to

-- lift element changer to list changer changeElement :: Integer -> (a -> a) -> [a] -> [a] changeElement f 0 (x:xs) = f x : xs changeElement f n (x:xs) = x : changeListElement f (pred n) xs

-- provide nicer names changePlanet = changeElement changeGalaxy = changeElement

Let's see how we can use this:

To set the name of the second planet of the third galaxy to "earth":

(changeGalaxy 2 $ changePlanet 1 $ changeName $ const "earth") univ

To increase the age of the same planet by 1:

(changeGalaxy 2 $ changePlanet 1 $ changeAge $ succ) univ

Using map instead of changeElement, we can change all galaxies or planets at once:

-- provide nicer names changeGalaxies = map changePlanets = map

To set the name of the first planet in all galaxies to "first":

(changeGalaxies $ changePlanet 0 $ changeName $ const "first") univ

To increase the age of all planets by one:

(changeGalaxies $ changePlanets $ changeAge $ succ) univ

A possible next step is to use typeclasses as supposed by apfelmus to access elements of different structures in a uniform way.

Tillmann

This is very informative, and easier to grasp for such a newbie as me. So the idea is to take the "changing function" down the chain, i knew this couldn't be that hard ! Still this requires indeed to think different, I guess i'm up for quite a few exercises in order to wrap my mind around this. That's the kind of information that's missing from all these tutorials i found around the web. Thank you, Sacha

On 6/3/07, Tillmann Rendel wrote:

In functional programming, problems of the kind "and the same code for all functions doing something related" are most often solved by introducing higher order functions. Let's try to decompose the problem as follows: [snip]

Now I've got one question ;). Is it *efficient* to go down this way? You are recreating (parts of) two lists and checking every planet, every time you need to change something. Maybe using a Map instead of a list would at least let the complexity go down a little bit? Or am I missing something? Cheers, =) -- Felipe.

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

apfelmus wrote:

Phlex wrote:

...

Donald Bruce Stewart wrote:

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

This answers precisely my question. Hiding the access/update methods behind a common interface, that's the key ... Thanks a lot, Sacha

hi there,

Let's say i have a deep nested data structure. Universe containing galaxies, containing solar systems, containing planets, containing countries, containing inhabitants, containing ...whatever.

Using the OO paradigm, once i get a reference to an inhabitant, i can update it quite easily (say by changing it's age), and that's the end of it.

but that approach limits you to about one choice for modelling your problem: a big ball of interlinked updateable references. every time you update anything, you update everything, because that is all there is. so you've reached "the end of it" for your modelling process before you've even started to think about how best to model your problem. haskell does have updateable references, so you could replicate that approach, though i'd suspect there'd be very few cases where this could actually be recommended. so here are two alternative, related approaches, to give you an idea of what is possible: data Universe = U [Galaxy] deriving Show data Galaxy = G [SolarSystem] deriving Show data SolarSystem = S [Planet] deriving Show type Planet = String u = U [G [S ["mercury","venus","earth","mars"]]] -- it's a small world a) work inside the outer structures, by moving the work inwards, to the target traverseU g traverse (U gs) = U (here++(traverse this:there)) where (here,this:there) = splitAt g gs traverseG s traverse (G ss) = G (here++(traverse this:there)) where (here,this:there) = splitAt s ss traverseS p traverse (S ps) = S (here++(traverse this:there)) where (here,this:there) = splitAt p ps so, to work on a planet, you'd visit its solar system, then do the work there: workOnPlanet [g,s,p] work = traverseU g (traverseG s (traverseS p work)) b) work through the outer structures, by lifting target accessors outwards liftUget g get (U gs) = get (gs!!g) liftGget s get (G ss) = get (ss!!s) liftSget p get (S ps) = get (ps!!p) liftUset g set (U gs) = U (here++(set this:there)) where (here,this:there) = splitAt g gs liftGset s set (G ss) = G (here++(set this:there)) where (here,this:there) = splitAt s ss liftSset p set (S ps) = S (here++(set this:there)) where (here,this:there) = splitAt p ps getPlanet get [g,s,p] = liftUget g (liftGget s (liftSget p get)) setPlanet set [g,s,p] = liftUset g (liftGset s (liftSset p set)) now, if 'get'/'set' work on a planet, then 'getPlanet get [g,s,p]'/ 'setPlanet set [g,s,p]' work on a specific planet in a universe. main = do print $ workOnPlanet [0,0,2] ("HERE: "++) u print $ getPlanet id [0,0,2] u print $ setPlanet (const "EARTH") [0,0,2] u while (b) may be closer to the 'reference into everything' you're used to, (a) is usually nicer and more efficient, because it nests larger chunks of work instead of nesting each and every small step. both styles are in common use in haskell, though get&set are often merged into one. there are more interesting aspects to this, eg, how exactly to model the data structures (lists are a useable default, but not always the best choice), or how to share substructures not affected by updates, or how to make traversal more flexible, so that we can change traversal directions on the fly, or how to extract the commonalities in the data structure interfaces, so that we only have to write that traverse or lifting code once, and perhaps generically over the different types addressed by different paths, etc. but since all of those will no doubt be addressed in other replies, i thought a simple start might be best;-) hth, claus