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