Generic tries (long)

[Adrian Hey]

Hello Iavor,

Iavor Diatchki wrote:
> thanks for doing this---I think that the functions in the API look
> good.  Of course, one can always think of more :-)  One that I often
> find useful when working with Data.Map is a function that removes a
> key from a map and also returns the associated value---a kind of
> destructive lookup.

That would be good. I guess you could implement that using the OMap
idea I just posted, or you could have a specialised lookupDelete
method.

> I think that the library would be better if you exposed a
> non-overloaded API for the map(s?) that you plan to implement.  This
> is useful because (i) most of the type I anticipiate using a single
> type of map, and concrete types lead to more accurate types in type
> inference, (ii) it makes the API Haskell'98 and hence likely to work
> on most Haskell implementations out there.   If you really think that
> the overloading is useful, then you could provide separate modules
> that provide the class+instances in terms of the non-overloaded API
> and add a cabal flag to turn these on/off.

I agree, all the hand written instances I've written so far do expose
the non-overloaded function names. The instance declarations are just
simple renamings. However, the polymorphic versions still have
appropriate class constraints so probably still won't work with any
Haskell that doesn't understand the class.

Things may not be so simple with automated deriving because of the
difficulty of adding to module export lists. But I guess with bit
of that cpp hackery thrown in this is not too much of a problem :-)

> Also, as others mentioned, using Int# in an API is not great because
> this is a GHC internal type.  If you found situatuins where GHC is not
> unboxing something please send a mail to the GHC team---they are
> usually very good at fixing these sorts of things.  Adrian mentioned
> that you use CPP to control the use of Int# but this does not help if
> the Int# leaks through the API:  (i) I could still have programs that
> work in Hugs and fail to compile in GHC (and vice versa), (ii) if I
> want to use your map library, I would have to compile all my programs
> with the CPP extensions, which is not nice.

Well I may be wrong, but AFAIK as we're talking about a class method
here if boxed is what you specify, boxed is what you will get. It
*might* be converted to unboxed if you use a SPECIALISE pragma, but
this kind of optimisation depends on strictness analysis. It's very
easy to end up writing something that is non-strict (or is strict but
ghc can't see it) and lose the unboxing.

I haven't been keeping up with H', but I would hope that support for
unboxed (or should I say unpointed?) types would be part of that.

Regards
--
Adrian Hey