Re: [Haskell-cafe] Best bit LIST data structure

2011-10-11 Thread Ryan Ingram
On Sun, Oct 9, 2011 at 6:18 AM, Ryan Newton rrnew...@gmail.com wrote: Yep, it is simple. But I prefer to only use well-tested data structure libraries where I can! Here's an example simple implementation (partial -- missing some common functions): module Data.BitList ( BitList ,

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-10 Thread Ryan Newton
On Sun, Oct 9, 2011 at 12:11 PM, Roman Beslik ber...@ukr.net wrote: Yes, if you do not use high-level concepts and optimize everything by hand, it requires a lot of testing. :) There are probably more constructive, jibe-free ways to frame this suggestion... Regarding testing: my preference

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread Roman Beslik
I am not aware of such a library, but IMHO this code will be very simple. data Bits b = BitList b = BitList Int {- number of used bits in the next component -} b [b] Write an isomorphism between @BitList b@ and @ListStep (BitList b)@ where data ListStep e rc = Nil | Cons e rc On 07.10.11

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread Ryan Newton
Yep, it is simple. But I prefer to only use well-tested data structure libraries where I can! Here's an example simple implementation (partial -- missing some common functions): module Data.BitList ( BitList , cons, head, tail, empty , pack, unpack, length, drop ) where import

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread Joachim Breitner
Hi, Am Freitag, den 07.10.2011, 10:52 -0400 schrieb Ryan Newton: What about just using the Data.Bits instance of Integer? Well, presently, the setBit instance for very large integers creates a whole new integer, shifts, and xors:

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread Daniel Fischer
On Sunday 09 October 2011, 15:54:14, Joachim Breitner wrote: Hi, Am Freitag, den 07.10.2011, 10:52 -0400 schrieb Ryan Newton: What about just using the Data.Bits instance of Integer? Well, presently, the setBit instance for very large integers creates a whole new integer, shifts, and

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread Thomas Schilling
On 9 October 2011 14:54, Joachim Breitner m...@joachim-breitner.de wrote: Hi, Am Freitag, den 07.10.2011, 10:52 -0400 schrieb Ryan Newton: What about just using the Data.Bits instance of Integer?  Well, presently, the setBit instance for very large integers creates a whole new integer,

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread Roman Beslik
Yes, if you do not use high-level concepts and optimize everything by hand, it requires a lot of testing. :) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread KC
Must it be a list? What about a Bloom Filter? On Sun, Oct 9, 2011 at 9:11 AM, Roman Beslik ber...@ukr.net wrote: Yes, if you do not use high-level concepts and optimize everything by hand, it requires a lot of testing. :) ___ Haskell-Cafe mailing

Re: [Haskell-cafe] Best bit LIST data structure

2011-10-09 Thread Yves Parès
data *(Bits b) =* BitList b Is deprecated and soon to be removed from the language. I fail to understand. Why not just: data BitList b = Nil | BitList Int b (BitList b) ?? 2011/10/9 Roman Beslik ber...@ukr.net I am not aware of such a library, but IMHO this code will be very simple. data

[Haskell-cafe] Best bit LIST data structure

2011-10-07 Thread Ryan Newton
Hi Cafe, We are lucky to have a plethora of data structures out there. But it does make choosing one off hackage difficult at times. In this case I'm *not* looking for a O(1) access bit vector (Data.Vector.Unboxed seems to be the choice there), but an efficient representation for a list of bits