generalized IntMap - IntegerMap or IntegralMap

[Jonathan S]

> 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-multiplication/part-4
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 <david.feuer at gmail.com> wrote:
> ---------- Forwarded message ----------
> From: "David Feuer" <david.feuer at gmail.com>
> Date: Jan 22, 2018 1:42 PM
> Subject: Re: generalized IntMap - IntegerMap or IntegralMap
> To: "Oliver Charles" <ollie at ocharles.org.uk>
> 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" <ollie at ocharles.org.uk> 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" <david.feuer at gmail.com> 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" <mail at joachim-breitner.de>
>>> 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 at joachim-breitner.de
>>>>   http://www.joachim-breitner.de/
>>>>
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> Libraries at haskell.org
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> Libraries at haskell.org
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>