[Fwd: updateLookupWithKey confusion]

[Adrian Hey]

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 <ahey at iee.org>
> To: Jean-Philippe Bernardy <jeanphilippe.bernardy at gmail.com>
> 
> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
> 
>