Generic tries (long)

[Adrian Hey]

Hello apfelmus,

apfelmus wrote:
> in  alter f .. ? Hm, maybe some zipper-like extension of  lookup  can do 
> the trick
> 
>   focus :: k -> map a -> (Maybe a, Maybe a -> map a)
> 
>   lookup k    = fst . focus k
>   delete k m  = case focus k m of
>       (Nothing, _) -> m
>       (_      , g) -> g Nothing
>   alter f k m = case focus k m of
>       (Nothing, g) -> case f Nothing of
>            Nothing -> m
>            x       -> g x
>       (x      , g) -> g x

I think I prefer this API now, largely because it doesn't require the
definition of a new type (per GMap instance presumbly). Only thing
I have against it is that it creates another of those weird dual purpose
functions that take (Maybe something) as an argument (don't like them
much :-).

So possibly instead we could have..

focus :: k -> map a ->
          (Maybe (a      -- associated value (if any)
                 ,map a  -- k deleted map (unevaluated thunk)
                 )
          ,a -> map a    -- Insertion/Substitution
          )

Again, I don't think this could replace alter and friends as a typical
zipper implementation will burn as much heap as you're trying to save
(twice as much if you go ahead and delete or substitute). But it would
avoid an expensive second search in cases where you want the operation
combined with a lookup.

Instances that can do this cheaper than full zipper (unboxed Int path
say) could define their alter,deleteMaybe etc using it if they wanted.
(though AFAICS alter can be defined in terms of insertMaybe/deleteMaybe
anyway with no efficiency loss).

Regards
--
Adrian Hey