Re: Re: generalized IntMap - IntegerMap or IntegralMap

Jonathan S. has been working (on and off) on a wholesale replacement for IntMap.

For context, this is me.

what is the plan here? I am currently in the process of formally verifying IntSet (and later IntMap), so I am curious about what is going to change here.

The algorithm is related in that the shape of the tree for a given set of keys is the same as the shape of a Patricia tree. However, the way everything is encoded and where keys and values are stored is completely different. The best description of the algorithm currently is at https://github.com/gereeter/bounded-intmap/blob/master/README.md .The description is in terms of a WordMap, since the logic is easier to follow with unsigned integers and it was something I personally wanted. https://www.schoolofhaskell.com/user/edwardk/revisiting-matrix-multiplicatio... is also a useful resource, which describes an unoptimized version of the structure.

I wish I knew. There are some loose ends that need to be tied up and unfortunately I have no sense of whether that's happening.

On the implementation from, working on and off is quite accurate. I'm working on it whenever I have the time, energy, and interest, which unfortunately hasn't been that often. That said, the implementation is almost done. If my benchmarks are correct (and I'm not entirely sure they are, but they are somewhat believeable), the new implementation is basically universally faster, and the only function left unimplemented is mergeA (I think). Most of the remaining work is in documentation, and I guess that could theoretically done at least partially in a second pass and PR if it is easier and people want the changes merged.

Er... what am I thinking? Of course it's order-isomorphic. The isomorphism just isn't a coercion, so it's not free.

I'm completely confident that at least my IntMap implementation works unmodified for both signed and unsigned integers, even though they don't have a free order isomorphism. I originally implemented IntMap (in the standalone bounded-intmap repository) by just casting to Word and fiddling with the order afterwards, and similarly you could pass everything in and out with the order isomorphism, but it turns out to be unnecessary - the difference in order can only switch the two children of the topmost node, and since comparison is used when determining which branch to take, the navigation procedure is also flipped consistently at the topmost node when using signed integers. You could take the implementation in haskell/containers#60 and make it generic on the key type (requiring Ord and Bits), and I'm completely confident that it work correctly in all (2's complement) cases, regardless of the signedness or the bitwidth.

Would backpack be at all useful here? Seems you want to parameterise the map by choice of numeric type.

The only use I see for Backpack here is in unboxing the integer type. IntMap gets a fairly large portion of its efficiency from having unboxed keys (see, e.g., https://www.twanvl.nl/blog/haskell/benchmarking-unpacked-containers), and GHC currently can't unbox generic parameters. If I understand the Backpack work correctly, each instantiation of IntegerMap would be distinct, so GHC would have no problem unboxing the keys. On Mon, Jan 22, 2018 at 12:42 PM, David Feuer wrote:

---------- Forwarded message ---------- From: "David Feuer" Date: Jan 22, 2018 1:42 PM Subject: Re: generalized IntMap - IntegerMap or IntegralMap To: "Oliver Charles" Cc:

That would help, in theory. But backpack is a bleeding-edge experimental GHC feature, and containers has a long history of striving for relative portability. So for now we need to stick to CPP and whatever other widely-available preprocessors we want.

On Jan 22, 2018 1:38 PM, "Oliver Charles" wrote:

...

Would backpack be at all useful here? Seems you want to parameterise the map by choice of numeric type.

On 22 Jan 2018 3:59 pm, "David Feuer" wrote:

...

I wish I knew. There are some loose ends that need to be tied up and unfortunately I have no sense of whether that's happening.

On Jan 22, 2018 10:54 AM, "Joachim Breitner" wrote:

...

Hi,

Am Montag, den 22.01.2018, 04:05 -0500 schrieb David Feuer:

...

Jonathan S. has been working (on and off) on a wholesale replacement for IntMap.

what is the plan here? I am currently in the process of formally verifying IntSet (and later IntMap), so I am curious about what is going to change here.

Cheers, Joachim

-- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries