[Haskell-cafe] FiniteMapFiniteMap

[Duncan Coutts]

On Thu, 2004-12-09 at 11:04 -0500, S. Alexander Jacobson wrote:
> Or is there a better way to (de-)serialize
> FiniteMaps?

There's a neat trick that we use in c2hs (at least the patched version
shipped with gtk2hs) to strictly read all the keys of the finite map but
read all the values lazily. This gives massive savings (from 10s of sec
to .1s of sec) since for this application the keys are small (an int or
two) and only a small number of items get looked up.

This uses ghc's Binary (de)serialisation module. The trick is to lazy
reading/writing is to store offsets so that items can be skipped over
and later seek back to them if the value was demanded. The actual
details are already implemented in the Binary module as lazyPut/lazyGet.

So for FiniteMap, what I do is:

instance (Binary key, Ord key, Binary elem) =>
         Binary (FiniteMap key elem) where

-- This would be the ordinary strict implementation
--    put_ bh fm = put_ bh (fmToList fm)
--    get bh = do list <- get bh
--                return (listToFM list)

    put_ bh fm = do let list = fmToList fm
                    put_ bh (length list)
                    mapM_ (\(key, val) -> do put_ bh key
                                             lazyPut bh val) list
    get bh = do len <- get bh
                let getMany :: Int -> IO [(key,elem)]
                    getMany 0 = return []
                    getMany n = do key <- get bh
                                   val <- lazyGet bh
                                   xs <- getMany (n-1)
                                   return ((key,val):xs)
                list <- getMany len
                return (listToFM list)

So as you can see, on deserialisation we build a perfectly ordinary
FiniteMap but all the values in the map are thunks that will on-demand
read and deserialise the value from disk.

Actually, this is a rather nice example of using laziness. In a strict
language to do this lazy reading trick you would have to change every
user of FiniteMap.

Of course all this relies on doing binary rather than textual
serialisation, otherwise byte offsets into the file make no sense and
you couldn't skip over stuff and come back to it later.

Duncan