Containers and strictness continued

Edward Kmett ekmett at
Fri Jul 9 13:36:06 EDT 2010

Sadly, no. I wind up utilizing those operations, but you still need two passes. Inserting into a trie where the first level child node already exists has no way to report if you had to create the node n levels down. The lookup returns Just (some trie) but then you still have to walk it!

So you wind up having to lookup and then insert or you wind up not memoizing the size of the trie. Both are highly suboptimal solutions.

Sent from my iPhone

On Jul 9, 2010, at 1:22 PM, "Claus Reinke" <claus.reinke at> wrote:

>> 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
> _______________________________________________
> Libraries mailing list
> Libraries at

More information about the Libraries mailing list