Why doesn't my Haskell function support infinite lists?

Question

I don't understand why my implementation of this function for a tutorial exercise fails to be lazy. It fails when running take 4 (chunks 3 [0..]). Please advise me what to change.

I'm not doing anything that I think would cause an infinite list to be evaluated:

• no length function
• no pattern matching on the list that requires computation
• no tail function
• no right side calculations

--   chunks 2 [1,2,3,4] ==> [[1,2],[2,3],[3,4]]
--   take 4 (chunks 3 [0..]) ==> [[0,1,2],[1,2,3],[2,3,4],[3,4,5]]

chunks :: Int -> [a] -> [[a]]
chunks len input = chunks' len input []

chunks' :: Int -> [a] -> [[a]] -> [[a]]
chunks' _ [] output = output
chunks' len input@(input1:inputTail) output
    | lengthAtLeast len input = chunks' len inputTail (output++[take len input])
    | otherwise               = output
    where 
        lengthAtLeast len list = length (take len list) >= len

Answer 1

This is an issue:

chunks' len input@(input1:inputTail) output
    | lengthAtLeast len input = chunks' len inputTail (output++[take len input])

Note that the condition lengthAtLeast ... will be always true for infinite lists. Hence, we always fall in this case -- which recurses without producing any part of the output. The output would be returned only when we fall in the other cases, but that never happens.

Instead, make sure the result is produced before we recurse:

chunks' len input@(input1:inputTail) output
    | lengthAtLeast len input = take len input : chunks' len inputTail output

Of course, after this change output will always be the empty list, and we can remove the argument, further simplifying the code.

The thumb rule is: when dealing with infinite lists, tail recursion will lead to infinite loops. You want to generate at least part of the result before recursing. In general, tail recursion is the wrong approach when your output is a large data structure like a list, which should instead be generated gradually so that we can benefit form laziness.