[Haskell-cafe] functional maps

Chad Scherrer chad.scherrer at gmail.com
Fri Dec 21 14:14:42 EST 2007


A while back I was playing with Data.Map was getting irritated about
lookups that fail having the type of values, but wrapped in an extra
monad. I decided to work around this by putting a default in the data
type itself, so we have a "functional map"

data FMap k a = FMap (k -> a) (Map k a)

This has been really convenient - it's a monad, and failed lookups
have the same type as successful ones.

lookup :: (Ord k) => k -> FMap k a -> a
lookup k (FMap f m)= Map.findWithDefault (f k) k m

This also makes it much nicer to build a function that tabulates a
list of pairs (nicer than I've found using Data.Map, anyway):

fromPairs :: (Ord k) => [(k,a)] -> FMap k [a]
fromPairs = foldl' (flip . uncurry $ insertWith (:)) $ return []

insertWith :: (Ord k) => (a -> b -> b) -> k -> a -> FMap k b -> FMap k b
insertWith f k x m = case lookup k m of
  v -> insert k (f x v) m

Ok, great, but fromPairs is blowing the stack. It does fine for a
while, but today I was trying to use it for a few million pairs. It
runs for a while, eats a couple gigs of ram, and then I get a stack
overflow.

Any advice for tracking this down? Thanks!

Chad


More information about the Haskell-Cafe mailing list