[Haskell-cafe] Keys and Maps [Was: Re: I just don't get it (data structures and OO)]

6 Jun 2007

      apfelmus wrote:
...
I mean, if the problem is indeed to store all known
planets in the universe, then it's indeed a database in nature and you
have to support fine grained operations like
delete :: Key -> Database -> Database
   insert :: Key -> Item -> Database -> Database
   ... and so on ...
(Note that some proposals like
changeGalaxies $ changePlanet 0 $ changeName $ const "first"
or functional references can be interpreted as keys for 'insert' or
'delete'. I mean that this expression already is the key to look up a
planet inside the universe, it's just that this key has a rather unusual
type. And that you can compose keys.)
Here's an elaboration of the last remark which gives a Haskell-98 way to
compose keys for "nested" finite maps (like Map k (Map k' a)). It's
inspired by functional references and similar to the type-class approach.

The problem we want to solve is to access/change/delete values of type
'a' in a nested map like say Data.Map k (Data.Map k' a). Here, k and k'
are known as "keys", but we will redefine the notion "key" shortly. The
basic observation is that we need a pair (k,k') to access a value of
type 'a', just like accessing a file via an absolute path requires a
sequence of directory names. Directories can be "composed" via the well
known slash '/' and that's what we're going to do as well:

    :: Key m m' -> Key m' a -> Key m a

Here, a value of type

   data Key m a = ... -- abstract for now

means that it's a key to access values of type 'a' in a finite map of
type 'm' that stores theses values. In other words, we are given operations

   lookup :: Key m a -> m -> Maybe a
   insert :: Key m a -> a -> m -> m
   delete :: Key m a -> m -> m
   ...

to change the finite map at a particular key. Of course, we already have
concrete keys k for Data.Map k a. We can turn those into abstract keys
via a given embedding

   at :: k -> Key (Data.Map k a) a

Now, how to implement Key? The observation is that all operations on
keys take them as their first argument which means that we can implement
them as record selectors! For maximum generality, we use the following

  data Key m a = Key {
                   lookup    :: m -> Maybe a
                 , singleton :: a -> m
                 , alter     :: (Maybe a -> Maybe a) -> m -> m
                 }

Here, 'alter' combines the functionality of insert, delete and adjust,
which can be implemented as follows:

  insert k x = update k $ const $ Just x
  delete k   = update k $ const $ Nothing
  adjust k f = update k $ fmap f

Key composition is readily implemented as

  k  k' = Key {
        lookup    = \m   -> lookup k m >>= lookup k'
      , singleton = \x   -> singleton k (singleton k' x)
      , alter     = \f m -> alter k (alter' f) m
      }
    where
    alter' f (Just m') = Just $ alter k' f m'
    alter' f Nothing   = f Nothing >>= singleton k'

Finally, we can implement keys for a concrete finite map implementation

  at :: k -> Key (Data.Map k a) a
  at k = Key {
        lookup    = Data.Map.lookup k
      , singleton = Data.Map.singleton k
      , alter     = flip Data.Map.alter k
      }

As an example, we have

  Just "Earth" == lookup (at "Milky Way"  at "Sun") universe

assuming that

  universe :: Data.Map String (Data.Map String String)

Regards,
apfelmus