[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