Search code examples
haskelllazy-evaluationinfinite

infinite lists, lazy evaluation and length

Haskell noob here: I'm still trying to understand the mechanics of the language, so if my question is plain stupid, forgive me and point me to some link which I can learn from (I've searched awhile in similar topics here on stackoverflow, but still I can't get this).

I came out with this function:

chunks :: Int -> [a] -> [[a]]
chunks n xs
    | length xs <= n = [xs]
    | otherwise = let (ch, rest) = splitAt n xs in ch:chunks n rest

so that

ghci> chunks 4 "abracadabra"
["abra","cada","bra"]
ghci> 
ghci> chunks 3 [1..6]
[[1,2,3],[4,5,6]]

I was pretty satisfied with that, then I thought "there's lazy evaluation! I can use this even on an infinite sequence!". So i tried take 4 $ chunks 3 [1..]. I was hoping that the lazy haskell magic would have produced [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]], instead it seems like this time lazyness can't help me: it can't reach the end of the computation (is it walking all the way long to the end of [1..]?)

I think the problem is in the "length xs" part: ghci seems to get stuck also on a simple length [1..]. So I'm asking: is length actually iterating the whole list to give a response? If so, I guess length is to be avoided every time I try to implement something working well with the lazy evaluation, so there is some alternative? (for instance, how can I improve my example to work with infinite lists?)

Solution

  • is length actually iterating the whole list to give a response?

    Yes.

    I guess length is to be avoided every time I try to implement something working well with the lazy evaluation

    Not just that, it also gives you bad runtimes when laziness isn't a factor (being O(n) in cases where an O(1) check often suffices1), so you should avoid it most of the time in general.

    how can I improve my example to work with infinite lists?

    You don't need to check whether the length of the list is less than n, you just need to check whether it's zero. And that you can do with a simple pattern match.

    1 For example something like f xs | length xs >= 2 = ..., which is O(n), can be replaced with f (x1 : x2 : xs) = ..., which is O(1).