Thanks Daniel. But genbin 32 gives an empty list.. works till 31.
On Fri, Oct 15, 2010 at 9:05 AM, Daniel Gorín <[email protected]> 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 <[email protected]>: >>> On Fri, 15 Oct 2010 14:34:42 +0200, rgowka1 <[email protected]> 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 >>> [email protected] >>> http://www.haskell.org/mailman/listinfo/haskell-cafe >>> >> >> >> >> -- >> Eugene Kirpichov >> Senior Software Engineer, >> Grid Dynamics http://www.griddynamics.com/ >> _______________________________________________ >> Haskell-Cafe mailing list >> [email protected] >> http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
