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