Quiz #2 is Wed, March 18th
1
Today
Finish lazy evaluation
Special considerations:
Mutability and laziness
Tail call recursion and laziness
Higher Order Functions
map, filter, foldl/r
Lazy Evaluation: Review
Waiting to evaluate function arguments that are expressions only when needed (and possibly not at all), and then, only as much as necessary
What does “needed” mean? Or “necessary”?
When the program encounters a built-in operation, rather than a user-defined function
Only enough to successfully match a pattern but no more
Why be lazy? Advantages: Efficiency (avoidance of unnecessary computation), Infinite Lists, and Modularity (separation of control from data)
Can you have different outputs in a lazy vs. eager language?
Yes. Example: implementation of “add” in the LC
Can you have different outputs in a lazy vs. eager language?
Yes. Example: “unless”
Mutability Laziness
Almost all imperative languages evaluate eagerly, and even almost all functional languages evaluate eagerly, too.
Only a language that is a pure functional programming language should have lazy evaluation as its default strategy.
That is, only a language that guarantees immutability should be lazy-by-default.
Why?
Example
“One or both are true: X is less than or equal to 5, and Temp is less than or equal to 10. X is 5 and Temp is 15”
Example
“X is greater than 5 AND Temp is greater than 10. X is 5 and Temp is 15”
BUG!!
“An exclusively lazy language should be pure”
The compute function causes a “side effect” (mutation of x), and yet, because of temp’s laziness, compute may or may not be called and so the side effect may or may not happen.
It is not ideal to bake that kind of complexity into a language.
By offering the keyword “lazy” in addition to mutation, Scala hopes to force you to be explicit and therefore clearer about your lazy-yet-side-effecting intentions.
A lazy-by-default language needs to avoid mutability for the sake of clarity.
Recursion can be space inefficient
(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(*5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 1))))
(* 5 (* 4 (*3 2)))
(* 5 (* 4 6))
(* 5 24)
120
Optimize by rewriting with an “accumulator”
(fact 5 1)
(fact 4 5)
(fact 3 20)
(fact 2 60)
(fact 1 120)
120
Does it make sense to use tail call recursion in a language that evaluates lazily?
Seemingly “tail recursive” implementation of factorial in Haskell:
tailFact 0 acc = acc
tailFact n acc = tailFact (n-1) (n * acc)
How would tail-fact 4 1 evaluate, given lazy evaluation?
tailFact (4 – 1) (4 * 1)
tailFact 3 (4 * 1)
tailFact (3 – 1) (3 * (4 * 1))
tailFact 2 (3 * (4 * 1))
tailFact (2 – 1) (2 * (3 * (4 * 1)))
tailFact 1 (2 * (3 * (4 * 1)))
tailFact (1 – 0) (2 * (3 * (4 * 1)))
(2 * (3 * (4 * 1)))
(2 * (3 * 4))
(2 * 12)
24
You lose the call stack space savings
of tail recursion in a lazy language.
13
So… is stack overflow simply an unavoidable threat in Haskell?
No, because Haskell lets you force functions to use eager evaluation and tail call optimization
factorial :: (Integral a) => a -> a
factorial x = fac’ x 1 where
fac’ 0 acc = acc
fac’ n acc = fac’ (n-1) $! (n * acc)
Writing $! in front of an argument forces that argument to be evaluated before being passed into the function body.
Example: Not tail recursive
Another example, now using $!
Higher Order Functions in Haskell
We care about the “usual suspects”:
Map, Filter, Foldl/r
Built-in higher order functions
Same standbys as in Racket: map, filter, fold(l/r)
map (* 2) [1..10]
[2,4,6,8,10,12,14,16,18,20]
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map p (x:xs) = p x : map p xs
Using a list comprehension instead?
doubleMap n = [x*2 | x <- [1..n]]
Built-in higher order functions
Same standbys as in Racket: map, filter, fold(l/r)
filter (\x -> mod x 2 == 0) [1..10] — filter even [1..10]
[2,4,6,8,10]
PARTICIPATION QUIZ!
filter :: (a -> Bool) -> [a] -> [a]
Built-in higher order functions
Same standbys as in Racket: map, filter, fold(l/r)
filter (\x -> mod x 2 == 0) [1..10] — filter even [1..10]
[2,4,6,8,10]
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x :xs)
| p x = x : filter p xs
| otherwise = filter p xs
Using a list comprehension instead?
evenFilter n = [x | x <- [1..n], mod x 2 == 0]
/docProps/thumbnail.jpeg