Laziness in Action

Matthías Páll Gissurarson, @tritlo

Reykjavík Functional Programming

2020-07-31

What is Laziness?

Comes from the evaluation order:

Strict evaluation:

(2 * (3 + 4))
= (2 * 7)
= 14 

Non-strict evaluation:

(2*3) + (2*4)
= 6 + 8
= 14 

In general: Strict evaluation proceeds from the inside out, evaluating all sub-expressions before evaluating the expression.

Examples

def ifThenElse(c: bool, t: int, e: int):
  if c:
    return t
  else:
    return e
def a():
  print "ok"
def b()
  quit()
    
print(ifThenElse(True, a(), b()))

vs.

ifThenElse :: Bool -> a -> a -> a
ifThenElse True  t _ = t
ifThenElse False _ e = e
a = unsafePerformIO (print "ok")
b = unsafePerformIO (die "Evaluated!")

main = print (ifThenElse True a b)

More Examples

doWhile :: (a -> Bool) -> IO a -> IO a
doWhile cond action = do result <- action
                         if cond result
                         then doWhile cond action
                         else return result
                         
mult :: IORef Int -> IO Int
mult ref = do modifyIORef ref (* 2)
              readIORef ref
              
main :: IO ()
main = do ref <- newIORef (1 :: Int)
          res <- doWhile (< 100) (mult ref)
          print res

Forces Purity

Since we don't evaluate until a value is needed, it becomes important to encapsulate side effects:

f = die "Evaluated!"
main = do k <- f
          print "Made it!"
          print k

vs

f = unsafePerformIO (die "Evaluated!")
main = do k <- return f
          print "Made it!"
          print k

Enables Sharing

Because we defer evaluation until something is needed, we can do common sub-expression elimination:

f n = unsafeDupablePerformIO $ print "f" >> return n
f2 n = unsafePerformIO $ print "f2" >> return n

main = do print (f 2 * f 2)
          print (f2 2 * f2 2)

here, f 2 will only be evaulated once (with -O3), despite being called twice, as it will be turned into:

main = let f' = (f 2) in print (f * f)
       print (f2 2 * f2 2)

However, unsafeDupablePerformIO will be inlined, which prevents sharing:

print ((unsafePerformIO $ print "f2" >> return 2) * (unsafePerformIO $ print "f2" >> return 2))

Partial Evaluation

In Haskell, we only evaluate as much as we need. E.g. we can write:

firstThreeOdds :: (Int, Int, Int)
firstThreeOdds = (x,y,z)
  where  Cons x (Cons y (Conz z xs)) = odds

And since the value of xs is never demanded, we only evaluate odds far enough to match the pattern. And luckily! Otherwise, working with infinite data would be cumbersome.

Note: pattern matches are strict! By e.g. writing

main = do (Cons x _) <- return odds
          print x

We evalute odds enough at that point to check the value, and invoking fail otherwise. We can recover laziness by writing

main = do ~(Cons x _) <- return odds
          print x

Theory of infinite data

With laziness, we can define infinite data:

data List a = Cons a (List a) | Empty

odds :: List Int
odds = let odds' n = Cons n (odds' (n+2)) in odds' 1
  
takeWhile :: (a -> Bool) -> List a -> List a
takeWhile _ Empty = Empty
takeWhile cond (Cons a cdr) = if cond a then (Cons a (takeWhile cond cdr)) else Empty

This is known as an inductive datatype, defined in terms of its constructors.

We can also define co-inductive datatypes (codata) defined in terms of their destructors ("views"):

data Stream a = Stream {head :: a, tail :: Stream a}
evens :: Stream Int
evens = let evens' n = Stream {head = n, tail = evens' (n+2) } in evens' 2

Laziness + codata allows us to define e.g. IO, since we lazily evaluate the views (e.g. memory), and not the entire world!

Caveats

The tradeoff for lazy evaluation is memory:

E.g. for

foldr (+) 1 [2,3,4,5]
= ((((1 + 2) + 3) + 4) + 5)

we'd rather store 15 than the unevaluated expression.

Luckily, haskell has a primitive (seq :: a -> b -> b) that allows us to force evaluation, e.g. seq a b will evaluate a and return b. We can use this to define $!:

($!) :: (a -> b) -> a -> b
($!) f x = seq x (f x)

Which evaluates x before applying f. We can then write:

foldl' f x xs = foldl (f $!)

Which would evaluate (1+2) to 3 before proceeding etc.

Thank You!

Any questions?