Containers and strictness continued

[Edward Kmett]

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 talk21.com> 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 haskell.org
> http://www.haskell.org/mailman/listinfo/libraries