Generic tries (long)

[Isaac Dupree]

>> 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.

this is where we need, hmm,
if in the class there was
size :: map a -> Int#
one would like something such as
size :: map a -> {-# UNPACK #-} Int
to work, since that unboxing doesn't change the semantics (results are 
implicitly lifted...).
But as it is
addSize :: map a -> UINT -> UINT
foldElemsUINT :: (a -> UINT -> UINT) -> map a -> UINT -> UINT
we also need something like John Meacham's ! and ~ stuff in class 
methods, to force strictness (because that changes the semantics).  It 
could get ugly, since GHC tries to preserve sharing by default, so we 
always need UNPACK:
addSize :: map a -> {-#UNPACK#-}!Int -> {-#UNPACK#-}Int

Reminds me a little of
http://hackage.haskell.org/trac/ghc/ticket/1349
because functions in data and in classes suffer the same "openness" 
problem that you can't know, given separate compilation, what functions 
are going to be used to implement that - so you can't optimize for them 
so well.

-Isaac