Quiz #2 is Wed, March 18th
CS 345, Lecture 20
New rule for Office Hours
Cameras must be turned on during office hours.
Please come prepared to be seen and heard!
Last time
We finished lazy evaluation
Special considerations:
Mutability and laziness
Tail call recursion and laziness
Last Time: Map and Filter
Map
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
Filter
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
These work the same as map and filter in Racket. But note:
The function argument can be partially applied
filter (< 3) [1,2,3]
map (* 2) [1,2,3]
You can also use a list comprehension to map and filter
[x | x <- [1,2,3], x < 3]
[x*2 | x <- [1,2,3]]
Built-in higher order functions
Same standbys as in Racket: map, filter, fold(l/r)
Recall that fold takes a function and “folds” it in between the elements of a list:
> foldl (+) 0 [1..3]
1 2 3
+ 1 + 2 + 3
0 + 1 + 2 + 3
6
foldl vs. foldr
> foldl (-) 0 [1, 2, 3]
-6
> foldr (-) 0 [1, 2, 3]
2
0
1
f
f
2
f
3
-1
-3
-6
2
f
f
-1
1
f
2
3
0
3
Caution: Haskell’s foldl is different from Racket’s foldl!
6
Review: Racket’s foldl
foldl means a left-to-right fold in this sense:
(foldl – 0 (list 1 2 3 4 5)
(- 5 (- 4 (- 3 (- 2 (- 1 0)))))
= 3
The evaluation order:
(- 1 0) first,
(- 2 (- 1 0)) next, etc…
…reads the input list (list 1 2 3 4 5) from left to right.
Haskell’s foldl: different from Racket!
> foldl (-) 0 [1..5]
> -15
(0 – 1)
((0 – 1) – 2)
(((0 – 1) – 2) – 3)
((((0 – 1) – 2) – 3) – 4)
(((((0 – 1) – 2) – 3) – 4) – 5)
Implementing Haskell’s foldl
> foldl (-) 0 [1, 2, 3]
-6
0
1
f
f
2
f
3
myfoldl f base [] = base
myfoldl f base (x:xs) = myfoldl f (f base x) xs
9
foldr
> foldr (-) 0 [1..3]
> 2
(1 – (2 – ( 3 – 0)))
(1 – (
(1 – (2 – (
(1 – (2 – ( 3 – 0)))
(Same as Racket’s foldr: phew!)
Let’s implement myfoldr
> foldr (-) 0 [1, 2, 3]
2
myfoldr f base [] = base
myfoldr f base (x:xs) = f x (myfoldr f base xs)
2
f
f
1
f
3
0
11
Why is foldl different in Racket vs. Haskell??
Honestly, I don’t know, and I also haven’t found any consensus about it on the web or answers in books.
I have, however, found false information:
Why is foldl different in Racket vs. Haskell??
Consider the difference between these implementations: both are tail recursive, so that can’t be the reason one was chosen over the other.
Perhaps it all comes down to this!
(foldl cons ‘() (list 4 3 2 1))
‘(1 2 3 4)
The way foldl is currently implemented in Racket, you have an elegant and efficient way to reverse a list.
Rest of Today: Haskell Review
List comprehensions
Function composition
Partial Application
Higher Order Functions
List Comprehensions
What does func accomplish?
func :: Int -> [(Int, Int, Int)]
func n = [ (x, y, z) | x <- [1 .. n] , y <- [1 .. n] , z <- [1 .. n], x ^ 2 + y ^ 2 == z ^ 2 ]
Returns all the Pythagorean triples up to some ceiling n.
List Comprehension Function Example: Factors
Factors are the numbers that evenly divide a given number. For example, the factors of 6 are 1, 2, 3, and 6.
How can we use list comprehensions to write a function that returns all the factors of a number?
factors n = …
factors 6
[1,2,3,6]
factors :: Integral a => a -> [a]
factors n = [x | x <- [1..n], mod n x == 0]
List Comprehension Function Examples: Primes
What are prime numbers?
How can we use our factors function to write an isPrime function?
isPrime x = take 2 (factors x) == [1,x]
How can we use our isPrime function as the predicate in a list comprehension, to find all the prime values up to some limit?
primes lim = …
primes 12
[2,3,5,7,11]
primes lim = [x | x <- [1..lim], isPrime x]
Review: Function Composition
(p (f (g x)))
In Haskell, there’s a clean syntax for composing functions, using this “dot” operator:
(p.f.g) x = (p (f (g x)))
(even.negate.sum) [1,2,3,4]
true
1. sum [1,2,3,4] -> 10
2. negate 10 -> -10
3. even -10 -> true
Review: Function Composition
f :: Integral a => [a] -> Bool
f = even.negate.sum
f [1,2,3,4]
true
Function Composition for Readability
map (\x -> negate (abs x)) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]
map (negate . abs) [5,-3,-6,7,-3,2,-19,24]
[-5,-3,-6,-7,-3,-2,-19,-24]
Function Composition for Readability
map (\xs -> negate (sum (tail xs))) [[1..5],[3..6],[1..7]]
[-14,-15,-27]
map (negate . sum . tail) [[1..5],[3..6],[1..7]]
[-14,-15,-27]
Function Composition Example: Revenue
Function Composition Example: Word Count
Function Composition: Practice
Give the sum of the negation of only the even items of a list
[1,2,3,4]
-2 + -4 = -6
Given a list of pairs of Ints, return the product of the max of each pair
[(3,4),(1,3),(2,3)]
36
Define your own “maxOfTuple”
f :: Integral c => [c] -> c
f = sum.map negate.filter even
f [1,2,3,4]
-6
maxOfTup :: (Int, Int) -> Int
maxOfTup (x,y) = if x > y
then x
else y
f :: [(Int, Int)] -> Int
f = product.map maxOfTup
f [(3,4),(1,3),(2,3)]
36
Participation Quiz
What’s going on here? Explain why this works!
This is a challenge! Discuss it with your peers.
Studying for the Midterm
Modules:
Slides
Recordings
Do not worry about recommended reading
Your labs
In the next 24 hours, I will create a Module in Canvas containing these study materials:
Exhaustive list of topics
Practice Canvas test
Monday after return from Spring Break will be exclusively devoted to content review:
I will not prepare a lecture. It will be in the format of office hours, i.e. directed by your questions
/docProps/thumbnail.jpeg