Library proposal: add a Location interface for element-wise operations on Data.Map (#4887)

[Ross Paterson]

On Sat, Jan 08, 2011 at 01:07:48AM +0100, Bas van Dijk wrote:
> (The following is just some brainstorming)
> 
> Why not store the value in the Location as in:
> 
> data Location k a
>     = Empty !k !(Path k a)
>     | Full {-# UNPACK #-} !Size !k a !(Path k a) !(Map k a) !(Map k a)
>
> [...]
> We do need a function to retrieve the value:
> 
> value :: Location k a -> Maybe a
> value (Empty _ _) = Nothing
> value (Full _ _ v _ _ _) = Just v

That would work well for search, but then index, minLocation and maxLocation
would return Locations that value was always mapped to Just something.
Extra invariants like that feel wrong to me.