Announcements
Midterm #1 next Monday.
You can write your personalized exam in class time or in any
50 minutes in the 24 hours before the end of the exam.
Open-book. You can use Google and ghci. (But won’t help 😉
All predefined functions you can use will be described (type
and their API).
A practice exam is on course web page (last years exam).
“A computer is like a violin. You can imagine a novice trying first a phonograph and then a violin. The latter, he says, sounds terrible. Computer programs are good, [some] say, for particular purposes, but they aren’t flexible. Neither is a violin, or a typewriter, until you learn how to use it.”
– Marvin Minsky, “Why Programming Is a Good Medium for Expressing Poorly-Understood and Sloppily-Formulated Ideas”, 1967
CPSC 312 — Lecture 7 1 / 13
©D. Poole 2021
Review
Haskell is a functional programming language Strongly typed, but with type inference
Bool
Num, Int, Integer, Fractional, Floating, Double Eq, Ord
Tuple, List, Function
Classes, type variables
List comprehension [f x | x<-list, cond x]
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(...⊕(an⊕v))) foldl ⊕ v [a1,a2,..an]=(((v⊕a1)⊕a2)⊕...)⊕an
CPSC 312 — Lecture 7 2 / 13
©D. Poole 2021
Clicker Question
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(...⊕(an⊕v))) Given
ml = foldr (\ x y -> y+1) 0
what is the result of
ml [10,11,12,13,14,15]
A [11,12,13,14,15,16]
B6
C 11
D [True,True,True,True,True,False] E It gives a type error
CPSC 312 — Lecture 7
3 / 13
©D. Poole 2021
Clicker Question
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(…⊕(an⊕v))) Given
bar = foldr (\ x y -> x+1) 0
what is the result of
bar [10,11,12,13,14,15]
A [11,12,13,14,15,16]
B6
C 11
D [True,True,True,True,True,False] E It gives a type error
CPSC 312 — Lecture 7
4 / 13
©D. Poole 2021
Clicker Question
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(…⊕(an⊕v))) Given
foo = foldr (\ x y -> (x+1):y) []
what is the result of
foo [10,11,12,13,14,15]
A [11,12,13,14,15,16] B6
C 11
D [16,15,14,13,12,11] E It gives a type error
CPSC 312 — Lecture 7
5 / 13
©D. Poole 2021
Clicker Question
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(…⊕(an⊕v)))
map f [a1,a2,..an] = [f a1,f a2,..,f an] Which of the following implement map
A map f lst = foldr (\x y -> f x:y) [] lst
B map f lst = foldr (\x y -> f x: map f y) [] lst C map f lst = foldr (\x y -> f x) [] lst
D map f lst = foldr (\x y -> x:f y) [] lst
E None: foldr cannot be used to implement map
CPSC 312 — Lecture 7 6 / 13
©D. Poole 2021
Clicker Question
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(…⊕(an⊕v))) foldl ⊕ v [a1,a2,..an]=(((v⊕a1)⊕a2)⊕…)⊕an
add1y x y = y+1
add1x x y = x+1
What returns the length of the list [7..9]?
A (foldr add1y 0 [7..9]) and (foldl
B (foldr add1y 0 [7..9]) and (foldl
C (foldr add1x 0 [7..9]) and (foldl
D (foldr add1x 0 [7..9]) and (foldl
E all four (foldr add1y 0 [7..9]) and (foldl add1y 0 [7..9]) and (foldr and (foldl add1x 0 [7..9])
add1y 0
add1x 0
add1y 0
add1x 0
add1x 0
[7..9]) [7..9]) [7..9]) [7..9])
[7..9])
©D. Poole 2021
CPSC 312 — Lecture 7 7 / 13
Clicker Question
foldr ⊕ v [a1,a2,..an]=a1⊕(a2⊕(…⊕(an⊕v))) foldl ⊕ v [a1,a2,..an]=(((v⊕a1)⊕a2)⊕…)⊕an
Which of the following gives a type error at compilation time
(i) foldr (:) [] [1,2,3,4,5]
(ii) foldl (:) [] [1,2,3,4,5]
A neither give an error
B (i) gives an error and (ii) doesn’t C (ii) gives an error and (i) doesn’t D they both give an error
©D. Poole 2021
CPSC 312 — Lecture 7 8 / 13
Call-by-name and Call-by-value
Recall: Definition
foo x = exp is an abbreviation for foo = \ x -> exp
Writing foo is same as \ x -> exp
foo x y = exp is an abbreviation for foo = \ x -> \y -> exp
Reduction:
(\ x -> f(x)) a reduces to f(a) substitute argument for formal parameter.
Example:
m x y = x*y
m (10-5) (m 10 5)
Call-by-value: evaluate arguments before reduction: m 5 50 Call-by-name: reduction of function first: (10-5)*(m 10 5)
CPSC 312 — Lecture 7 9 / 13
©D. Poole 2021
Call-by-name and Call-by-value
Call-by-value: evaluate arguments before reduction Call-by-name: reduction of function first
What does the following do?
inf = 1+inf
Does following halt?
inf = 1+inf
fst (x,y) = x
fst (3+2, inf)
sq x = x*x
sq (55+45)
If they both halt, they give same answer
CPSC 312 — Lecture 7
10 / 13
©D. Poole 2021
Lazy Evaluation
Lazy evaluation: evaluate argument only once, only if needed Evaluation Order:
Evaluation from outside in
Otherwise (if it knows both arguments need to be evaluated)
from left to right
It is possible to evaluate all arguments that need to be evaluated in parallel.
One could imagine a language that memorizes the results of all previous function calls. GHC does not do that. I just caches locally.
Lazy evaluation enables forms of programming that are not possible with call by value. E.g., definition of if-then-else
myif True then_exp else_exp = then_exp
myif False then_exp else_exp = else_exp
fac n = myif (n==0) 1 (n*fac (n-1))
CPSC 312 — Lecture 7 11 / 13
©D. Poole 2021
Lazy Computation Examples: finding primes (Lazy.hs)
Sieve of Eratosthenes
start with the list of all numbers ≥ 2,
when found a prime, cross off the multiples of that prime from the rest of the list
– – sieve (p:xs) is the list of all primes from p, given all of a multiples of primes less than p have been removed.
primes = sieve [2..]
where sieve (p:xs) =
p : sieve [x | x <- xs, x ‘mod‘ p /= 0]
take 100 primes
CPSC 312 — Lecture 7 12 / 13
©D. Poole 2021