Does indexing a mapped/filtered infinite list apply the map/filter function to all the elements before the index?

user_15055749 0
Viewed 128

If I define an infinite list and call map over it with a function, I can take some number of elements from the beginning and Haskell will generate and apply the function only to these elements due to lazy evaluation

-- This will generate and process 10 elements

doubledNumbers = map (*2) [0..]
take 10 doubledNumbers

If I index this infinite mapping instead

doubledNumbers !! 9

will Haskell generate the list up to that point, apply the mapping function to all elements and give the element at index 9 back; or will it generate the list, apply the mapping function to the element at index 9, and give that back. In other words, which of the following (if any) would happen when I call doubledNumbers !! 9

  1. The list [0,1,2,3,4,5,6,7,8,9] is generated, then the list [0,2,4,6,8,10,12,14,16,18], then 18 is taken from that list
  2. The list [0,1,2,3,4,5,6,7,8,9] is generated, than 9 is taken from that list and given to (*2) , than (*2) returns 18
list haskell
3 Answers

The second interpretation is the correct one (well, morally at least: see below for a better explanation):

  1. The list [0,1,2,3,4,5,6,7,8,9] is generated, than 9 is taken from that list and given to (*2) , than (*2) returns 18

You can observe that the function ((*2) in your case) is not applied to other elements with the following experiment. First, define a function that will crash on every number except 9:

f 9 = 100 ; f _ = error "urk!"

Then try your code in GHCi, adapted to the new function

> doubledNumbers = map f [0..]
> doubledNumbers !! 9
100

If GHCi applied f to any other number you would observe the crash. This is a way to distinguish, through an experiment, lazy evaluation from eager evaluation.

More pedantically, entering in GHCi the code

> doubledNumbers = map (*2) [0..]
> doubledNumbers !! 9

will first generate a list similar to

(*2) 0 : (*2) 1 : .... : (*2) 9 : map (*2) [10..]

where the expressions are not yet evaluated. After that, GHCi will extract the 9th, causing it to be evaluated and printed.

user_32349590

Neither interpretation is correct. In fact, the list that's generated can be thought to look something like this:

[_,_,_,_,_,_,_,_,_,_...

In other words, the spine, or shape, of the list is forced up through the 9th element (and no further), but the actual values in the list aren't. Then, when you ask for the 9th element of the mapped list, GHC calls the function on that element without evaluating it unless necessary. You can observe this with the following experiment:

errorList = repeat (error "fail!")

trueList = map (const True) errorList

val = trueList !! 9

If the list were actually produced in the first place, then val would fail with fail! as soon as we try to print it. However, val properly is True.

user_148023840

Using the tracing facility:

It is often possible to answer this type of question using a little but handy tracing facility included in the Haskell runtime library.

So there is a trace function, such that evaluating the expression trace debugMsg expr will return the value of expr and, as a side effect, print the value of debugMsg to the standard error channel.

Yes, side effects are normally not available in Haskell, but the trace function enjoys a special privilege :-)

So you can replace your (*2) function with the equivalent one:

import qualified  Debug.Trace  as  DT

doubler :: Int -> Int
doubler x = let  debugMsg = "Doubling " ++ (show x) ++ " ... "
            in   DT.trace  debugMsg  (2*x)

And then you can test the various hypothesis under the ghci interpreter:

$ ghci
 GHCi, version 8.8.4: https://www.haskell.org/ghc/  :? for help
 λ> 
 λ> :load q65861408.hs
 [1 of 1] Compiling Main             ( q65861408.hs, interpreted )
 Ok, one module loaded.
 λ> 
 λ> :type doubler
 doubler :: Int -> Int
 λ> 
 λ> doubler 5
 Doubling 5 ... 
 10
 λ> 
 λ> doubledNumbers = map doubler [0..]
 λ> 
 λ> doubledNumbers !! 9
 Doubling 9 ... 
 18
 λ>

And so it appears that, as mentioned in the other answers, the doubling function is only invoked for the input value 9.

This is because of the language laziness: the user did not ask to see the other doubled values, hence there is no need to compute them in the first place.

user_112824040
Related