Generic tries (long)

[Jeffrey Yasskin]

On Sat, Jun 21, 2008 at 11:54 PM, Adrian Hey <ahey at iee.org> wrote:
> Hello apfelmus,
>
> apfelmus 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.
>>
>> You mean the case when
>>
>>  f Nothing = Nothing
>
> or, for some a ..
>
>  f (Just a) = Just a
>
> ..but of course there's no way you can tell from inside the alter
> function that the two a's are the same without an expensive equality
> test, and even then that's not enough because you need to pass the
> "no change" information back up the call chain (as a Nothing probably)
> which means that if there is a change even more heap will be burned
> by wrapping each intermediate result in a Just.

Thinking as a C++ programmer for a bit, I'd want to implement this as
a pointer comparison. If the argument to alter returns the same object
(not just an equal one), then the implementation can cheaply avoid
creating the new sub-tree. If it returns an equal one, you'd like to
skip the copy, but it's not worth the equality test. 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?

If alter were to cheat like this, we'd want to write its argument as:

f n at Nothing = n
f j@(Just a) = j

instead of risking creating a new object.

Trying this out, I figured out why it's called "reallyUnsafe":

Prelude GHC.Exts GHC.Prim> let q = Just 3
Prelude GHC.Exts GHC.Prim> let f j@(Just a) = j; r = f q
Prelude GHC.Exts GHC.Prim> I# (reallyUnsafePtrEquality# q r)
0
Prelude GHC.Exts GHC.Prim> r
Just 3
Prelude GHC.Exts GHC.Prim> I# (reallyUnsafePtrEquality# q r)
1
Prelude GHC.Exts GHC.Prim>

and even stranger:

Prelude GHC.Exts GHC.Prim> let q = Just 3
Prelude GHC.Exts GHC.Prim> let f j@(Just a) = j; r = f q
Prelude GHC.Exts GHC.Prim> I# (r `seq` reallyUnsafePtrEquality# q r)
0
Prelude GHC.Exts GHC.Prim> I# (r `seq` reallyUnsafePtrEquality# q r)
1


So it'd take some doing to get the implementation right, but getting
the fully-general API without wasting allocations might be worth it.

Jeffrey