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. Regards -- Adrian Hey