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.dimit...@googlemail.com>: >> On Fri, 15 Oct 2010 14:34:42 +0200, rgowka1 <rgow...@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@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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe