CODEWITHSUNDEEP
haskelllazy-evaluationfoldfoldleft
jdfauw
jdfauw

Reputation: 657

Haskell fold left over infinite list not applying lazy evaluation

From my understanding, as Haskell uses lazy evaluation, which allows operations on for example infinite lists to be evaluated in a finite amount of time.

As a test, I defined the following function

X Boolean
Y Int

f(X,Y) = (Y == 3) OR X

Hence, fold left applied to the infinite list of integers [1..] with False as initial value and the function defined above, should return True, because when it will reach n=3 evaluating f(n==3,False) will return True, and hence this True will propagate through the function.

I implemented this function in Haskell code

myfunc :: Bool -> Int -> Bool
myfunc True _ = True
myfunc _ n
  | (n == 3)  = True
  | otherwise = False

and tried it out in the cli

foldl myfunc False [1..]

The command becomes unresponsive, suggesting it is doing an infinite computation. Why is Haskell not benefiting from the lazy evaluation here?

Upvotes: 1

Views: 191

Answers (1)

Will Ness
Will Ness

Reputation: 71065

Because foldl always must traverse its argument list in whole before starting reducing it into the final result; and foldl' traverses the argument list in whole while reducing it into the final result:

foldl f z [x1, x2, ..., xn]  ==           foldl f (f z x1) [x2, ..., xn]

foldl' f z [x1, x2, ..., xn]  ==  z `seq` foldl' f (f z x1) [x2, ..., xn]

-- thus,

foldl f z1 [x1, x2, ..., xn]  ==  f (...(f (f z1 x1) x2)...) xn

foldl' f z1 [x1, x2, ..., xn]  ==  z1 `seq` (let z2 = f z1 x1  in
                                    z2 `seq` (let z3 = f z2 x2  in
                                     z3 `seq` (... `seq` (f zn xn)...)))

You though wanted to be able to stop the traversal, which is done via right fold with a non-strict reducing function:

present y xs  =  foldr myfunc False xs 
  where
  myfunc x r  =  y == x || r

Because myfunc is non-strict in its second argument, foldr myfunc explores the list xs in the left-to-right order,

foldr myfunc False (x:xs)  =  myfunc x (foldr myfunc False xs)
                           =  y == x || foldr myfunc False xs

Upvotes: 5

Related Questions