[Fwd: updateLookupWithKey confusion]

Adrian Hey ahey at iee.org
Sat Mar 31 17:18:19 EDT 2007

Jeffrey Yasskin wrote:
> If you don't intend to modify the map, lookup is probably enough,
> although with a slightly more general type for alterA involving "data
> Modification v = Delete | LeaveAlone | Replace v", we could subsume
> that too...

Well this is the potential difficulty. In general (assuming the search
succeeds) it will not be known whether or not to delete, replace or
leave alone until after the current associated value has been obtained.
So you need something like this. You could get away without the 
LeaveAlone constructor I guess (I.E. just use Maybe), but this won't
allow the "leave the entire tree alone" option (this is basically
what the current alter function does).

What I have in mind is something very simple..

-- An "Open" map (abstract data type)
data OMap k a

-- O(log n). Open a Map at a the supplied current key
openMap :: Ord k => k -> Map k a -> OMap k a

-- O(1). Read the value associated with the current key.
-- Returns Nothing if the search failed when the OMap was created
readOMap :: OMap k a -> Maybe a

-- O(log n). Delete the association at the current key
-- (O(1) if the search failed when the OMap was created)
deleteOMap :: OMap k a -> Map k a

--  O(log n). Set a new associated value for the current key.
writeOMap :: a -> OMap k a -> Map k a

-- O(1). Close OMap, leaving the Map unmodified (not strictly necessary)
closeOMap :: OMap k a -> Map k a

-- O(1). Get the current key (not strictly necessary)
readOMapKey :: OMap k a -> k

That should be all users need to implement whatever hybrid operations
they want. As to whether and how new values are calculated (and if
so how strictly etc..) is entirely up to them.

Adrian Hey

More information about the Libraries mailing list