Generic tries (long)

[Adrian Hey]

Hello apfelmus,

apfelmus wrote:
> The OMap type is like a zipper, the Int# encodes the path. I don't know 
> whether the Int# (which should be a !Int with an UNPACK pragma) really 
> gains anything compared to a list, only benchmarks can tell. Fretting 
> about it seems like an irrelevant micro-optimization to me.

Actually MHO is that using proper language constructs (where available)
is always preferable to pragma or compliler flag hackery :-)

As for this kind of thing being irrelevant micro-optimization, this is
not the case. If you consider what a typical Haskell prog spends it's
time doing..
  1 - Traversing heap data structures
  2 - Building new heap records
  3 - Collecting garbage

Excessive heap allocation rate has a big impact on time spent on both 2
and 3, and hence on overall performance. A fact that has been confirmed
in just about every benchmark I've ever run. Here's the results of one
I posted recently
  http://www.haskell.org/pipermail/haskell-cafe/2008-February/039882.html

So if performance is a concern, MHO is that heap allocation should be
avoided like the proverbial plague. In a world of immutable data
structures it's always likely to be on the high side anyway, but
anything that can be done to reduce it will boost performance.

I do think a general purpose zipper would be a great thing to have,
especially for ordered maps. But for the particular problem that sparked
this discussion I suspect (though I don't know) that it might be
expensive overkill. It needs thinking about. (There's at least one
case I know of where there is a much cheaper solution.)

> In any case, focus  can easily be implemented in terms of  OMap :

Yes, of course. The point I was trying to make about OMap was that if
we're going to have full zipper available, one where you could
actually "walk the map", inspecting, modifying, inserting and deleting
as you go (call it ZMap say), then the OMap distinction with
(corresponding impoverished API) is useful. Just making the point that
the OMap or something like it is all that's needed to solve this
particular problem (if it can be implemented cheaply).

Regards
--
Adrian Hey