headers
Obscaenvs | 8 Aug 2012 22:48
Picon
Gravatar

Lazy evaluation and list comprehensions

Hi fellow Haskellers! Trying literary style here, lets just hope it
plays well with your email clients.

Suppose we define a list - somewhat arbitrarily - as

 > xs = [1..42] :: [Int]

Next, we let x and ys be

 > x  = 17 -- also somewhat arbitrarily
 > ys = [ y | y <- xs, y >= x ]

My question: in which WHNF state is ys? y and x are evaluated in
applying >= to them - at least in this particular instance of Ord
(Int). Are these evaluated values then copied to the new list ys, or
are they just stored as thunks? I would guess that they are just
thunked, and that the state of ys is [*thunk*,*thunk*,...,*thunk*]
since it cannot be known beforehand to what extent the predicate
reduces its arguments (in this case >= ), but I don't know for sure.

I thought I had sufficient knowledge about thunks, WHNF, NF and lazy
evaluation, but this one does me in. I guess it is because I haven't
trawled through Okasaki's book yet :)
Permalink | Reply |
headers
Felipe Almeida Lessa | 8 Aug 2012 23:14
Picon
Gravatar

Re: Lazy evaluation and list comprehensions

Just use GHCi's :print command =).

Prelude> let xs = [1..42] :: [Int]; x = 17; ys = [ y | y <- xs, y >= x ]
Prelude> :print xs
xs = (_t1::[Int])
Prelude> :print ys
ys = (_t2::[Int])

Initially nothing is evaluated (as expected).

Let's try forcing ys to WHNF:

Prelude> ys `seq` ()  -- forcing to WHNF
()
Prelude> :print xs
xs = 1 : 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : 10 : 11 : 12 : 13 : 14 :
     15 : 16 : 17 : (_t3::[Int])
Prelude> :print ys
ys = 17 : (_t4::[Int])

So xs had to be forced until the first element of ys appeared (since
WHNF decides between [] and _:_).  We didn't explicitly evaluate ys's
first element but as it needed to be evaluated before it already
appears evaluated now.

Same thing if you continue forcing ys:

Prelude> tail ys `seq` ()  -- forcing tail to WHNF
()
Prelude> :print xs
(Continue reading)

Permalink | Reply |

Gmane