Why does my function not work with an infinite list?

3
votes

I'm trying to learn haskell and implemented a function conseq that would return a list of consecutive elements of size n.

conseq :: Int -> [Int] -> [[Int]]
conseq n x 
      | n == length(x) = [x]
      | n > length(x) = [x]
      | otherwise = [take n x] ++ (conseq n (drop 1 x))

This works correctly.

> take 5 $ conseq 2 [1..10]  
[[1,2],[2,3],[3,4],[4,5],[5,6]]

However, if I pass [1..] instead of [1..10], the program gets stuck in an infinite loop.

As I understood it, haskell has lazy evaluation so I should still be able to get the same result right? Is it length? Shouldn't the first two conditions evaluate to false as soon as the length becomes greater than n?

What did I misunderstand?

2
haskelllazy-evaluation
What's length(x), where x == [1..]? - ForceBru
Is length not evaluated lazily? - Tessa Altman
Well, how do you evaluate it lazily? Execution can't proceed without knowing the length of this list, so it has to be computed immediately. I'm not completely sure about that though - ForceBru
@TessaAltman: everything is evaluated lazily, but when it is needed, it is evaluated, and then length got stuck in an infinite loop. - Willem Van Onsem
If length returned something like a Peano number and if the comparisons for Peano numbers were lazily implemented it might be possible to have n > length x avoid an infinite loop. But this just isn't the case using Int and built-in length... - Bakuriu

2 Answers

4
votes

One of the main reasons why using length is not a good idea is because when it has to be evaluated on an infinite list, it will get stuck in an infinite loop.

The good news is however, we don't need length. It would also make the time complexity worse. We can work with two enumerators, one is n-1 places ahead of the other. If this enumerator reaches the end of the list, then we know that the first enumerator still has n-1 elements, and thus we can stop yielding values:

conseq :: Int -> [a] -> [[a]]
conseq n ys = go (drop (n-1) ys) ys
    where go [] _ = []
          go (_:as) ba@(~(_:bs)) = take n ba : go as bs

This gives us thus:

Prelude> conseq 3 [1 ..]
[[1,2,3],[2,3,4],[3,4,5],[4,5,6],[5,6,7],[6,7,8],[7,8,9],[8,9,10],[9,10,11],[10,11,12],[11,12,13],[12,13,14],[13,14,15],[14,15,16],[15,16,17],[16,17,18],[17,18,19],[18,19,20],[19,20,21],[20,21,22],[21,22,23],[22,23,24],[23,24,25],[24,25,26],[25,26,27],…
Prelude> conseq 3 [1 .. 4]
[[1,2,3],[2,3,4]]
4
votes

The first thing your function does is calculate length(x), so it knows whether it should return [x], [x], or [take n x] ++ (conseq n (drop 1 x))

length counts the number of elements in the list - all the elements. If you ask for the length of an infinite list, it never finishes counting.