5

I'm still a haskell newbie, so please excuse my bad code style.

I need all kind of combinations of letters in a box written into a file. In fact I need all this lines for doing a brute force attack on an old enigma puzzle. A line consists of a combination of 26 letters and 10 digits. It is given in the puzzle, that the first 6 characters were letters.

Now this is my code:

import Data.List (delete)

letters = ['A'..'Z']
allChars = letters ++ ['0'..'9']

boxContents :: [Char] -> [Char] -> [[Char]]
boxContents l lp = [a:b:c:d:e:f:delete f(delete e(delete d(delete c (delete b (delete a lp))))) | 
                 a <- l, 
                 b <- delete a l, 
                 c <- delete b (delete a l), 
                 d <- delete c (delete b (delete a l)),
                 e <- delete d (delete c (delete b (delete a l))),
                 f <- delete e (delete d (delete c (delete b (delete a l))))
                 ]

main :: IO()                    
main = writeFile "c:\\bc.txt" $ unlines $ boxContents letters allChars

It eats up my 16 GB ram and than consumes 100 GB pagefile until it dies. I'm sure I can write I simple program in plain old C that uses less than 64 kB RAM to produce this file. But that's not the point: The point is how to make this work in Haskell? Where's my mistake?

Hennes
  • 1,340
  • 1
  • 10
  • 26
  • 4
    Are you trying to generate permutations of length 7 of `allChars` where the first six are known to be `letters`? Use `permutations`, and read this: http://stackoverflow.com/a/24564307/461499 – Rob Audenaerde Apr 09 '15 at 09:50
  • 6
    Did you compile it with `-O2` There is no space explosion with `-O2` in ghc 7.8.4 – Sibi Apr 09 '15 at 10:21
  • 1
    @RobAu: The strings are a bit longer than 7 chars. A big bit. Sibi: You're my hero. That was the hint. Now it works. Thank you. – Hennes Apr 09 '15 at 10:33
  • 3
    Has anyone some explanation about why this requires so much space in GHCi without optimizations? What is retaining so much data in the code above? Why is it not being garbage collected? Using `show . length` instead of `unlines` makes it run in constant space. Even using `show . length . unlines` makes it constant space. Is the issue in `writeFile` which is not writing lazily as one would expect? – chi Apr 09 '15 at 10:44
  • 1
    @chi I would imagine without optimisations there's no strictness analysis. I couldn't pin it down any further than that, however. – MathematicalOrchid Apr 09 '15 at 11:21
  • 2
    It runs in constant space for me regardless of optimization level (as I would expect). Am I the only one? – Reid Barton Apr 09 '15 at 14:04
  • I'm thinking that the huge constant value from the expression `unlines $ boxContents letters allChars` might not be garbage collected if (the CAF for) `main` itself isn't, which might depend on how you compile/invoke it, say whole program vs. module vs. loading with GHCi... – Ørjan Johansen Apr 10 '15 at 00:37
  • Aha, I hadn't contemplated running the program from ghci or runghc. – Reid Barton Apr 15 '15 at 16:12

0 Answers0