generalized IntMap - IntegerMap or IntegralMap - Libraries

generalized IntMap - IntegerMap or IntegralMap

Henning Thielemann

22 Jan 2018 22 Jan '18

8:44 a.m.

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?

Show replies by date

David Feuer

22 Jan 22 Jan

9:05 a.m.

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 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 Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

Henning Thielemann

9:14 a.m.

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

David Feuer

9:19 a.m.

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 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

David Feuer

9:20 a.m.

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 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 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

Henning Thielemann

9:23 a.m.

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.

Joachim Breitner

3:53 p.m.

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/

David Feuer

3:58 p.m.

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

Oliver Charles

6:38 p.m.

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

2721

Age (days ago)

2721

Last active (days ago)

List overview

Download

8 comments

4 participants

participants (4)

David Feuer
Henning Thielemann
Joachim Breitner
Oliver Charles

generalized IntMap - IntegerMap or IntegralMap

tags

participants (4)