Generic tries (long)

Adrian Hey ahey at
Mon Jun 23 14:57:59 EDT 2008

Hello Jeffrey,

Jeffrey Yasskin wrote:
>  Is there a reason
> I'm missing that it's a bad idea to use
> GHS.Prim.reallyUnsafePtrEquality# or a similar low-level function in
> the alter implementation?

I think, given the fuss about unboxed Ints, most people would recoil in
horror at this :-)

I guess what you could do would be to have the function argument of
alter and friends return a type (Maybe (Maybe a)) where..

Nothing       means delete it
Just Nothing  means leave it alone
Just (Just a) means use a as the new associated value.

..then to pass the change/nochange information back up the call chain
you could use an unboxed pair result containing an appropriate Bool
in addition to the (possibly modified) subtree.

But I can't help wondering if all the functions like this are really
the wrong abstraction. They might be what you want sometimes, but
often you'd want to combine them with a lookup (without searching
the map twice in quick succession using the same key).

Something like the proposed zipper based focus, OMap or whatever
seems much more general purpose, flexible and easy to use. It's
just a question of whether or not it can be implemented efficiently
enough to make alter and friends obsolete (at least as class methods),
or should it be an addition to an API that still retains alter
(deleteMaybe etc..).

Adrian Hey

More information about the Libraries mailing list