[Haskell-cafe] Spine-lazy "multiqueue"

Jamie Brandon jamiiecb at googlemail.com
Wed Oct 22 16:08:45 EDT 2008


>  Ideas for how to make such tries
> composable would encourage me to release a hackage module :-)

Have a look at code.haskell.org/gmap/api - a library for composable
maps. It currently requires huge instances in the name of efficiency
but I hope to improve that over the next couple of months. The basic
idea is pretty simple:

class Map mp k | mp -> k where
  lookup :: k -> mp a -> Maybe a
  etc

data EitherMap mpL mpR kL kR = EitherMap mpL mpR

instance (Map mpL kL, Map mpR kR) => Map (EitherMap mpL mpR kL kR) where
  lookup (Left l) (EitherMap mpL mpR) = lookup l mpL
  lookup (Right r) (EitherMap mpL mpR) = lookup r mpR

The types can get a bit hairy at the moment but using associated types
instead of fundeps will probably improve that.

For lazy spined maps, lookup 'skew binary random access lists' (in
Okaski's book, if you have a copy). You'll get roughly the same
perfomance as a trie over bits but with the advantage that you can
take the tail in constant time. That way, if your keys are time values
(I'm guessing this is related to your frp ideas) you get the same
garbage collection properties as a simple list of [(Time,a)] but you
can still look ahead efficiently.

If you have problems with sparse time values you could compose the
random access list with something else:

data TimeMap mp a = TM (RandList (mp a))

instance (Map mp Integer) => Map (TimeMap mp) Integer where
  lookup k (TM randList) = lookup k (lookup (div k chunkSize) randList)
  etc


More information about the Haskell-Cafe mailing list