[Haskell-cafe] Re: All binary strings of a given length

[rgowka1]

Thanks Daniel.

But genbin 32 gives an empty list.. works till 31.

On Fri, Oct 15, 2010 at 9:05 AM, Daniel Gorín <dgorin at dc.uba.ar> wrote:
> I expect this one to run in constant space:
>
> import Data.Bits
>
> genbin :: Int -> [String]
> genbin n = map (showFixed n) [0..2^n-1::Int]
>    where showFixed n i = map (bool '1' '0' . testBit i) [n-1,n-2..0]
>          bool t f b = if b then t else f
>
> Daniel
>
> On Oct 15, 2010, at 9:43 AM, Eugene Kirpichov wrote:
>
>> Actually my ghci doesn't crash for genbin 25 (haven't tried further),
>> though it eats quite a bit of memory.
>> How are you going to use these bit strings? Do you need all of them at once?
>>
>> 2010/10/15 Aleksandar Dimitrov <aleks.dimitrov at googlemail.com>:
>>> On Fri, 15 Oct 2010 14:34:42 +0200, rgowka1 <rgowka1 at gmail.com> wrote:
>>>
>>>> Amazing, will never find this in any other languagw. But ghci crashes
>>>> for bigger input. Like genbin 20. How to scale this function?
>>>
>>> Well, "scaling" this isn't really possible, because of its complexity. It
>>> generates all permutations of a given string with two states for each
>>> position. In regular languages, this is the language {1,0}^n, n being the
>>> length of the string. This means that there are 2^n different strings in the
>>> language. For 20, that's already 1048576 different Strings! Strings are
>>> furthermore not really the best way to encode your output. Numbers (i.e.
>>> bytes) would be much better. You could generate them, and only translate
>>> into strings when needed.
>>>
>>> HTH,
>>> Aleks
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>>>
>>
>>
>>
>> --
>> Eugene Kirpichov
>> Senior Software Engineer,
>> Grid Dynamics http://www.griddynamics.com/
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>