Matthías Páll Gissurarson, @tritlo
Reykjavík Functional Programming
2020-07-31
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.
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)
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
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
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))
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
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!
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.
Any questions?