Re: [Fwd: updateLookupWithKey confusion]

Adrian Hey wrote:

Hello Folks,

Jean-Philippe suggests I put this question to the libraries list. Any thoughts?

Well thinking about this a bit more I propose that both updateLookupWithKey and insertLookupWithKey (and possibly several other functions) should be deprecated and replaced with a more general mechanism that allows users to "roll their own" as far as these complex hybrid operations are concerned, such as that AVL tree already provide in the form of the BAVL type: http://darcs.haskell.org/packages/collections/Data/Tree/AVL/Zipper.hs If you consider the problem of visiting a particular tree node there are 3 different things you might do if the search succeeds: 1- Modify the associated value 2- Delete the association 3- Leave the associated value unchanged, in which case it would be nice to leave the entire map/tree whatever unchanged (not duplicate all the nodes on the search path). If the search fails you might.. 1- Insert a new association 2- Insert nothing. Add to that the various possibilities for what value should be returned (Old value? New value? Both?) and with/without key options and lazy/strict options and the whole thing becomes a bit of a nightmare. Now it's true that the BAVL option or similar requires the tree to be traversed twice if it's modified (only once if it isn't), but the second traversal does not require any comparisons and the relevant nodes will probably still be in cache from the first traversal. So it should be very cheap (compared to the cost of constructing the new heap records). Regards -- Adrian Hey

-------- Original Message -------- Subject: updateLookupWithKey confusion Date: Mon, 26 Mar 2007 08:18:47 +0100 From: Adrian Hey To: Jean-Philippe Bernardy

Hello Jean-Philippe,

There seems to be some confusion over this between Haddock documentation and the two implementations in Data.Map and Data.Map.AVL.

Is the 'looked up' value supposed to be the value bound to the corresponding key in the map before or after the update? The behaviour isn't specified in the Haddock of either version.

In Data.Map implementation you could get the value present before or after the update (depending on whether or not the association is deleted). Surely that's wrong?

In Data.Map.AVL you consistently get the value present before the update occurs, but I would have thought it be more useful to get the value after the update occurs (if any).

Anyway, I think the behaviour needs specifiying and whichever implementation(s) is not consistent with that spec needs modifying. I'm working on Data.Map.AVL at the moment so I'll fix it if it's wrong (and make it more efficient too).

Also, why don't we have a plain updateLookup? (without key), like we do for other funcions.

Regards -- Adrian Hey

_______________________________________________ Libraries mailing list Libraries@haskell.org http://www.haskell.org/mailman/listinfo/libraries