Haskell List Comprehension and space leak

Question

I am trying to figure out how recursion combined with List Comprehension/Monadic operations cause space leaks.

I have a small test program:

module Main where
permute :: [a] -> Integer -> [[a]]
permute _ 0 = [[]]
permute xs' n = [x:xs | x <- xs', xs <- permute xs' (n-1)]
chars1 = ['0'..'9']
main = do
  putStrLn $ (permute chars1 10000)!!100000000 -- Leaks
  print $ [1..]!!100000000 -- Does not leak

Now, my understanding is that the function permute can be expanded as

xs' >>= \x -> (permute xs' (n-1) >>= \xs -> (x:xs))

So lots of (permute xs' n) will be stacked before a result can be retrieved. Am I understanding correctly? If so, what can I do to make sure the function does not leak?

Answer 1

This code is a little bit weird because permute doesn't actually.. well.. permute things but assuming that it's what you intended it actually performs in much the same way as your [0..] !! 10000 example, it's just that computing the 10000th selection is a lot more work in your code!

The important thing is that your code is lazy, we can easily compute the 1st element of permute [0..] 10 even though there are clearly infinitely many of them.

What you might be thinking of though is that when you actually run this it takes a really long time to produce any output even if you might hope that it would produce the 1st character... wait a bit.. produce the second character.. wait a bit.. and so on. This is not really a "leak" in the Haskell sense and cannot be avoided in this scenario. Youre list is essentially constructed with

map ('0':) (permute chars (n - 1)) ++ ... ++ map ('9':) (permute chars (n - 1))

The issue is that in order to know the first character, you need to figure out which "block" you'll be selecting from, which involves computing the length of the block, which involves evaluating permute chars (n - 1) fully. So what'll happen is you'll force each recursive call in turn until you have enough elements in the resulting list to evaluate the call to !!. This is not unexpected though. You can however significantly speed up this code with one fairly simple trick: reverse the x and xs in the list comprehension.

permute :: [a] -> Integer -> [[a]]
permute _ 0 = [[]]
permute xs' n = [x:xs | xs <- permute xs' (n-1), x <- xs']

Do note that the increased sharing could in theory lead to increased memory usage (something may not be GCed as soon in this version) but I'm unable to come up with a not-absurdly-contrived program which does this.