Strict list evaluation in GHCi

Question

Consider the program:

l = [0..10]
l' = map (+1) [0..10]

Running it with GHCi, and typing :sprint l and :sprint l' will reveal both lists to be unevaluated. However, after running length l and length l' and then again using sprint:

l = [0,1,2,3,4,5,6,7,8,9,10]

and

l' = [_,_,_,_,_,_,_,_,_,_,_]

I've made similar experiments and tried binding variables to lists in GHCi with let, however only in the case of l (defined as above in a program top-level) is the list always completely evaluated.

These behaviours all point to an optimisation feature, however I was wondering if there is a more elaborate answer (strategy) 'under-the-hood'.

Well the elements are never evaluated, since we do not need them, and do not make any comparison, equality check with the elements. This has not much to do with a list, it will happen with all datastructures. — Willem Van Onsem
Side note: one potential source of confusion can be eliminated by making the lists monomorphic ([0 :: Integer ..10]). That way loading the definitions from a file should have the same effect as entering them at the GHCi prompt. — duplode

duplode duplode · Accepted Answer · 2020-04-13T15:21:20

The elements of the original [0..10] lists were evaluated in both cases. What was left unevaluated in the l' case were the results of applying (+1) to the list elements. In contrast, here is what happens if we map the function strictly:

GHCi> import Control.Monad
GHCi> l'' = (+1) <$!> [0 :: Integer ..10]
GHCi> :sprint l''
l'' = _
GHCi> length l''
11
GHCi> :sprint l''
l'' = [1,2,3,4,5,6,7,8,9,10,11]

(Note that I am specialising the integer literals, so that the absence of the monomorphism restriction in the GHCi prompt doesn't lead to different results from what you get upon loading the code from a file.)

It is worth noting that enumFromTo for Integer (which is what using the range boils down to), as implemented by base, evaluates the elements in order to know when to stop generating them. That's to say it is not length that forces the list elements, as we'd hope from looking at its definition:

length                  :: [a] -> Int
length xs               = lenAcc xs 0

lenAcc          :: [a] -> Int -> Int
lenAcc []     n = n
lenAcc (_:ys) n = lenAcc ys (n+1)

To get a better feeling for how length behaves here, we might try repeating your experiment with a list generated by using replicate (which, like length, doesn't look at the elements) on a not fully evaluated value:

GHCi> n = 2 * (7 :: Integer)  -- let-bindings are lazy.
GHCi> :sprint n
n = _
GHCi> l''' = replicate 3 n
GHCi> :sprint l'''
l''' = _
GHCi> length l'''
3
GHCi> :sprint l'''
l''' = [_,_,_]

Strict list evaluation in GHCi

1 Answers