Is `map` in Haskell lazy?

user_123681 0
Viewed 269

I've been working through Graham Hutton's Programming in Haskell. It states that

the function map applies a function to all elements of a list

OK, makes sense. Certainly matches what I know about map from other languages.

One of the exercises is to implement all :: (a -> Bool) -> [a] -> Bool.

There are times where a naive implementation may loop infinitely if not done lazily. For example all (<10) [1..]. So my first implementation was:

all p []       = True
all p (x:xs)   | not (p x) = False
               | otherwise = all' p xs

But then I thought about trying with function composition of map and and to see what a non terminating programme in Haskell would do:

all' :: (a -> Bool) -> [a] -> Bool
all' p = and . map p

To my surprise, all' (<10) [1..] quickly returned False. I actually expected map to attempt to create an infinite list before and was applied - something like and [p x | x <- xs, p x].

This terminating behaviour would imply that map is in fact creating something similar to a stream which and is processing. Is map in fact lazy (and hence the description wrong) or have I misunderstood something else in my second implementation?

higher-order-functions lazy-evaluation haskell
1 Answers

Is map in fact lazy (and hence the description wrong) or have I misunderstood something else in my second implementation?

map is lazy. It will not eagerly apply the function to each item. In fact all expressions are lazy in the sense that map f x remains map f xs unless the value is needed.

If we evaluate map f xs, and we need for example the third element, it will not determine f x1 if we are not interested in the value of the first element.

List comprehension is lazy as well. Indeed, if we work with:

and [p x | x <- xs]

it will terminate from the moment one of the items x in xs has False as p x. If you however add a filter p x, it will only emit Trues, indeed:

[p x | x <- xs, p x]

will only yield True, since we already filter on the fact that p x should be True, and the and on a infinite list of Trues will never terminate, since and will keep looking for a False value.

user_675790
Related