You may also want to look at adding monadic inserts/adjusts/etc in the sense that there is currently no way to insertWith and extract any information in one pass.
This means a lot of otherwise trivial operations on tries built out of Map/IntMap take twice as long as would be otherwise necessary.
Would Data.IntMap.{mapAccumWithKey,insertLookupWithKey} help?
im fromList [(0,0),(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81),(10,100)]
let upd k f acc key val = if k==key then (Just val,f val) else (acc,val)
mapAccumWithKey (upd 3 $ const 0) Nothing im (Just 9,fromList [(0,0),(1,1),(2,4),(3,0),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81),(10,100)])
insertLookupWithKey (const $ (+)) 4 4 im (Just 16,fromList [(0,0),(1,1),(2,4),(3,9),(4,20),(5,25),(6,36),(7,49),(8,64),(9,81),(10,100)])
insertLookupWithKey (const $ (+)) 42 4 im (Nothing,fromList [(0,0),(1,1),(2,4),(3,9),(4,16),(5,25),(6,36),(7,49),(8,64),(9,81),(10,100),(42,4)])
Admittedly, I only remember them because I found them rather non-obvious when I needed them.. Also, mapAccumWithKey traverses the whole tree rather than the path to the entry. Claus