CODEWITHSUNDEEP
haskelllazy-evaluationhigher-order-functions
clinton3141
clinton3141

Reputation: 4841

Is `map` in Haskell lazy?

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?

Upvotes: 2

Views: 586

Answers (1)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476534

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.

Upvotes: 8

Related Questions