# CS计算机代考程序代写 Haskell Quiz #2 is Wed, March 18th

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