Generic tries (long)

[Adrian Hey]

Adrian Hey wrote:
> I've never been very keen on alter myself (on efficiency grounds) and
> was wondering whether of not to include it. If the "altering" results
> in an unchanged map it would be nice to just return the unchanged
> map (rather than duplicate all nodes on the search path). There are
> other possible alternatives to alter that are more efficient in this
> respect.

There's something else that's always bugged me about alter. I'm sure
I can't be the only one who thinks requiring me to define a function
like this is a very weird thing to do...

f :: Maybe a -> Maybe a
f Nothing  = maybea    -- A constant, either Nothing or (Just somea)
f (Just a) = f' a

I've never felt comfortable with this. In any case I realised
that alter can be easily implemented using other class primitives

alter f k map = case f Nothing of
                 Just somea -> insertMaybe f' k somea map
                 Nothing    -> deleteMaybe f' k map
  where f' a = f (Just a)

but since I know what maybea and f' are, it seems to me it's a lot
easier to just use f' directly in either insertMaybe or deleteMaybe
as appropriate (depending on maybea).

The type of the proposed merge now seems similarly strange to me..

merge :: (k -> Maybe a -> Maybe b -> Maybe c) -> map a -> map b -> map c

This requres users to define a function argument that is presumably of
form..

f k Nothing  Nothing  = undefined
f k (Just a) Nothing  = fa  k a
f k (Just a) (Just b) = fab k a b
f k Nothing  (Just b) = fb  k b

Why not just pass fa,fab and fb directly, which will be more convenient
for both users and implementors I think..

merge :: (k -> a ->      Maybe c) ->
          (k -> a -> b -> Maybe c) ->
          (k ->      b -> Maybe c) ->
          map a -> map b -> map c

Though I actually think if this is to be included perhaps it should be
called mergeMaybeWithKey, and we also have..

mergeMaybe :: (a ->      Maybe c) ->
               (a -> b -> Maybe c) ->
               (     b -> Maybe c) ->
               map a -> map b -> map c

merge :: (a ->      c) ->
          (a -> b -> c) ->
          (     b -> c) ->
          map a -> map b -> map c

mergeWithKey :: (k -> a ->      c) ->
                 (k -> a -> b -> c) ->
                 (k ->      b -> c) ->
                 map a -> map b -> map c

Regards
--
Adrian Hey