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