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

Thanks Daniel. But genbin 32 gives an empty list.. works till 31. On Fri, Oct 15, 2010 at 9:05 AM, Daniel Gorín 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 :

...

On Fri, 15 Oct 2010 14:34:42 +0200, rgowka1 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@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe