[Haskell-cafe] FiniteMapFiniteMap

[S. Alexander Jacobson]

Hmm cool. Binary does not appear in the GHC
docs...  Is it new?

-Alex-

On Thu, 9 Dec 2004, Duncan Coutts wrote:

> 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
>

______________________________________________________________
S. Alexander Jacobson tel:917-770-6565 http://alexjacobson.com