infinite lists, lazy evaluation and length

1
votes

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?)

3
haskelllazy-evaluationinfinite
The way to answer your own question of course is to track down the implementation of length (see the haskell tag info section for resources), or even better try to define it yourself and convince yourself that it can only possibly behave one way. - jberryman
And if you're feeling adventurous, try re-implementing splitAt and length in terms of Peano numbers instead of Int and see if you can make your chunks well-behaved on infinite lists - jberryman
You might like to look at genericLength and the lazy Natural type -- just changing Int to Natural in the type of chunks and changing length to genericLength will make your examples work. - Daniel Wagner

3 Answers

5
votes

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).

5
votes

Another trick you can do (which I've seen in Data.Text, but am surprised is not in Prelude for lists in general) is to make length short-circuit as soon as possible by returning an Ordering rather than a Bool.

compareLength :: [a] -> Int -> Ordering
compareLength [] n = compare 0 n
compareLength _ 0 = GT
compareLength (x : xs) n = compareLength xs (n - 1)

Then you can use it in chunks.

chunks :: Int -> [a] -> [[a]]
chunks n xs = case compareLength xs n of
                   LT -> [xs]
                   _  -> let (ch, rest) = splitAt n xs in ch:chunks n rest

And this works fine.

*Main> take 4 $ chunks 3 [1..]
[[1,2,3],[4,5,6],[7,8,9],[10,11,12]]

For this particular case, other implementations might be more idiomatic, but hopefully this is a nice trick to know.

3
votes

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

Yes, absolutely.

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

Yes, absolutely.

so there is some alternative?

Yes: solve the problem without referencing length. There are no general methods of problem solving so you need to work out each specific case.

how can I improve my example to work with infinite lists

You are a railroad worker. A huge train if cars begins where you are standing and stretches over the horizon. You have no idea where it ends, if ever. Your job is to separate it into small trains of three cars each. How do you proceed?