haskellevaluationstrictness

Strict list evaluation in GHCi


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'.


Solution

  • 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''' = [_,_,_]