[Haskell-cafe] Re: I just don't get it (data structures and OO)
Phlex
Phlex at telenet.be
Sun Jun 3 05:21:46 EDT 2007
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
More information about the Haskell-Cafe
mailing list