generalized IntMap - IntegerMap or IntegralMap

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

generalized IntMap - IntegerMap or IntegralMap

Henning Thielemann

I want to use Word32 or Word64 bit patterns as indices for a Map. I have
checked that IntMap is more efficient than Map in my application. However,
the Haskell 98 report warrants only 30 bits for Int including the sign
bit. Is there a generalization of IntMap for Map Integer or (Integral k,
Bits k) => Map k or would there be general interest in such a data
structure?
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

David Feuer
There has been some discussion in the past, but it hasn't gone far. A
few points:

1. Integer is a bit tough to deal with. It might make sense to use
some sort of trie for Integer keys.

2. I would very much like to add Data.Int64{Map,Set} and perhaps also
Data.Int32{Map,Set} to containers. Unfortunately, I don't have the
time to consider such a thing at the moment. Jonathan S. has been
working (on and off) on a wholesale replacement for IntMap. Perhaps he
has ideas for this extension as well. IntMap itself could become a
wrapper around one of those two, or could perhaps be implemented
separately (although I doubt it's worth the trouble).

3. I don't think any existing classes really get the point across. To
fit in an IntMap, a type must *actually* satisfy the law that   toEnum
. fromEnum = id. Furthermore, some operations will only make sense if
toEnum is strictly order-preserving. One option would be to add an ad
hoc class for just this purpose:

class SmallKey k where
  -- Laws:
  -- fromInt . toInt = id
  -- If k has an Ord instance, then toInt is strictly order-preserving.
  toInt :: k -> Int
  fromInt :: Int -> k

Of course, if (2) should happen, then we'll need SmallKey32 and
SmallKey64 classes.

On Mon, Jan 22, 2018 at 3:44 AM, Henning Thielemann
<[hidden email]> wrote:

>
> I want to use Word32 or Word64 bit patterns as indices for a Map. I have
> checked that IntMap is more efficient than Map in my application. However,
> the Haskell 98 report warrants only 30 bits for Int including the sign bit.
> Is there a generalization of IntMap for Map Integer or (Integral k, Bits k)
> => Map k or would there be general interest in such a data structure?
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

Henning Thielemann

On Mon, 22 Jan 2018, David Feuer wrote:

> 3. I don't think any existing classes really get the point across.

I would be happy with a custom class that has Word32 and Word64 as member,
and optimally a way to compose these words, e.g.
    type Word96 = Stack Word32 Word64
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

David Feuer
Word64 is an entirely different story, because it's not
order-isomorphic to Int64. That means lots of operations will actually
have to be implemented differently for it. Anyway, you should probably
check out the generic-trie package for ways to compose things.

On Mon, Jan 22, 2018 at 4:14 AM, Henning Thielemann
<[hidden email]> wrote:
>
> On Mon, 22 Jan 2018, David Feuer wrote:
>
>> 3. I don't think any existing classes really get the point across.
>
>
> I would be happy with a custom class that has Word32 and Word64 as member,
> and optimally a way to compose these words, e.g.
>    type Word96 = Stack Word32 Word64
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

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

On Mon, Jan 22, 2018 at 4:19 AM, David Feuer <[hidden email]> wrote:

> Word64 is an entirely different story, because it's not
> order-isomorphic to Int64. That means lots of operations will actually
> have to be implemented differently for it. Anyway, you should probably
> check out the generic-trie package for ways to compose things.
>
> On Mon, Jan 22, 2018 at 4:14 AM, Henning Thielemann
> <[hidden email]> wrote:
>>
>> On Mon, 22 Jan 2018, David Feuer wrote:
>>
>>> 3. I don't think any existing classes really get the point across.
>>
>>
>> I would be happy with a custom class that has Word32 and Word64 as member,
>> and optimally a way to compose these words, e.g.
>>    type Word96 = Stack Word32 Word64
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

Henning Thielemann
In reply to this post by David Feuer

On Mon, 22 Jan 2018, David Feuer wrote:

> Word64 is an entirely different story, because it's not
> order-isomorphic to Int64. That means lots of operations will actually
> have to be implemented differently for it. Anyway, you should probably
> check out the generic-trie package for ways to compose things.

Thank you for the pointer! I see, TrieKey has a pair instance.
Unfortunately it misses Word32.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

Joachim Breitner-2
In reply to this post by David Feuer
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
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

David Feuer
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" <[hidden email]> 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
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: generalized IntMap - IntegerMap or IntegralMap

Oliver Charles-3
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" <[hidden email]> 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" <[hidden email]> 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
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Fwd: Re: generalized IntMap - IntegerMap or IntegralMap

David Feuer
---------- Forwarded message ----------
From: "David Feuer" <[hidden email]>
Date: Jan 22, 2018 1:42 PM
Subject: Re: generalized IntMap - IntegerMap or IntegralMap
To: "Oliver Charles" <[hidden email]>
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" <[hidden email]> 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" <[hidden email]> 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" <[hidden email]> 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
  [hidden email]
  http://www.joachim-breitner.de/

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Re: 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 <[hidden email]> wrote:

> ---------- Forwarded message ----------
> From: "David Feuer" <[hidden email]>
> Date: Jan 22, 2018 1:42 PM
> Subject: Re: generalized IntMap - IntegerMap or IntegralMap
> To: "Oliver Charles" <[hidden email]>
> 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" <[hidden email]> 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" <[hidden email]> 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" <[hidden email]>
>>> 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
>>>>   [hidden email]
>>>>   http://www.joachim-breitner.de/
>>>>
>>>> _______________________________________________
>>>> Libraries mailing list
>>>> [hidden email]
>>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>>
>>>
>>> _______________________________________________
>>> Libraries mailing list
>>> [hidden email]
>>> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>>>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries