generalized IntMap - IntegerMap or IntegralMap
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?
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 <lemming@henning-thielemann.de> 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
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 <lemming@henning-thielemann.de> 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
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 <david.feuer@gmail.com> 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 <lemming@henning-thielemann.de> 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
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.
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/
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@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@joachim-breitner.de http://www.joachim-breitner.de/
_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
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@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@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@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
participants (4)
-
David Feuer -
Henning Thielemann -
Joachim Breitner -
Oliver Charles