How many times is (+ 1) computed here?

Question

On my functional programming exam, I had the following question:

How many times is (+ 1) function computed in the following code?

(map (+ 1) [1 .. 10]) !! 5

where the index function is defined like this:

(h:_) !! 0 = h
(_:t) !! x = t !! (x-1)

I would say 6 times, but the correct answer seems to be 1, and I cannot understand why. I could not find a good enough explanation of lazy evaluation in Haskell, so I would like to know what is the correct answer and why. Thank you in advance!

Answer 1

many times is (+ 1) function computed in the following code?

It is calculated only once. map does not force to calculate f xi on the elements in the result list. These calculations are postponed (just like everything else in Haskell), only when we need to calculate the value of a specific item, we do that.

map is specified in chapter 9 of the Haskell'10 report as:

-- Map and append  
map :: (a -> b) -> [a] -> [b]  
map f []     = []  
map f (x:xs) = f x : map f xs

There are no seq, bang patterns, etc. here to force evaluation of f x, so the map function will indeed "yield" an f x, but without evaluating f x, it is postponed until it is necessary (and it might happen that we are not interested in some of these values, and thus can save some CPU cycles).

We can take a look how Haskell will evaluate this:

   (!!) (map (+ 1) [1 .. 10]) 5
-> (!!) ((+1) 1 : map (+1) [2..10]) 5
-> (!!) (map (+1) [2..10]) 4
-> (!!) ((+1) 1 : map (+1) [3..10]) 4
-> (!!) (map (+1) [3..10]) 3
-> (!!) ((+1) 1 : map (+1) [4..10]) 3
-> (!!) (map (+1) [4..10]) 2
-> (!!) ((+1) 1 : map (+1) [5..10]) 2
-> (!!) (map (+1) [5..10]) 1
-> (!!) ((+1) 1 : map (+1) [6..10]) 1
-> (!!) (map (+1) [6..10]) 0
-> (!!) ((+1) 6 : map (+1) [7..10]) 0
-> (+1) 6
-> 7

This is because map f [x1, x2, ..., xn] eventually maps to a list [f x1, f x2, ..., f xn], but it does not compute f xi of the elements, that computation is postponed until we actually would need the value in that list, and do something with it (like priting it).

This can result in a significant performance boost, given f is an expensive function, and we only need the value of a small amount of elements in the list.

Answer 2

Let's test it by doing something horrible. You'll need to import the Debug.Trace module for this.

ghci> (map (\x -> trace "Performing..." (x + 1)) [1..10]) !! 5

Now, we'll get that totally safe IO action to happen every time the lambda expression is called. When we run this in GHCi, we get

Performing
7

So only once.

As a sanity check, we could remove the !! 5 bit.

ghci> map (\x -> trace "Performing..." (x + 1)) [1..10]
[Performing
2,Performing
3,Performing
4,Performing
5,Performing
6,Performing
7,Performing
8,Performing
9,Performing
10,Performing
11]

So it's definitely happening 10 times when we ask for the whole list.