CS计算机代考程序代写 Haskell PowerPoint Presentation

PowerPoint Presentation

Let us pray.

Today:
Pattern matching on lists (review)
List comprehensions
Composed functions

Useful list features in Haskell
Make a list with a range:
[1..10] is same as [1,2,3,4,5,6,7,8,9,10]
But, do [10,9..1] for [10,9,8,7,6,5,4,3,2,1]

If a pattern can be achieved by adding or subtracting a number, you can specify a step:
[2,4..10] is same as [2,4,6,8,10]
[1,3..11] is same as [1,3,5,7,9,11]

Useful built-in functions on lists:
sum[1,2,3] -> 6
product[2,3,4] -> 24
elem 4 [1..10] -> True
take 3 [1..10] -> [1,2,3]
drop 3 [1..10] -> [4,5,6,7,8,9,10]

Pattern Matching on Lists
[a, b, c] = a : b : c : []

(x:xs)

Pattern Matching on Lists
[a, b, c] = a : b : c : []

(x:xs)

myLength :: Num a => [b] -> a
myLength [] = 0
myLength (x:xs) = 1 + myLength xs

Head of the list
consed onto

the tail of the list

Implementing zip: myZip
zip is a built-in function that will create tuples from two lists, such that the indices of the elements are the same:

> zip [1,4,9,16,25] [1,8,27,64,125]
[(1,1), (4,8), (9,27), (16,64), (25,125)]

Let’s implement our own zip, called myZip.

Implementing zip: myZip
So long as both lists are not empty, we should cons a tuple of the heads of the two lists:

myZip (x:xs) (y:ys) = (x,y) : myZip xs ys

The base case will be reached when we reach the end of either of the input lists, upon which we’ll return an empty list:

myZip [] _ = []
myZip _ [] = []

Solution

Pattern Matching on Lists: uncouple
How would we write a function that takes a list of pairs of the same type, and creates a list of uncoupled items?

uncouple :: [(a,a)] -> [a]

uncouple [(1,2),(3,4),(5,6)]
[1,2,3,4,5,6]

Pattern Matching on Lists: uncouple
Base case:

uncouple [] = []

Recursive case:

uncouple (????) = a : b : uncouple c

The challenge here is to think of how to express the “head of the list” and the “tail of the list” as a pattern, especially given that we have a list of tuples.

Pattern Matching on Lists: uncouple
Solution:

Pattern Matching on Lists: myElem
elem is a built-in function that returns “true” if the argument can be found in the list:

elem 3 [1,2,3,4,4,6]
True

elem “hi” [“abc”, “boo”, “bar”, “hi” “fizz”]
True

How would you implement myElem using pattern matching?

Pattern Matching on Lists: myElem

myElem :: Eq t => t -> [t] -> Bool
myElem _ [] = False
myElem x (y:ys)
| x == y = True
| otherwise = myElem x ys

List Comprehensions

List Comprehensions
List comprehensions are a means of generating a new list from a list or lists. The output of a list comprehension is always a new list.
They come directly from the concept of set comprehensions in math, including similar syntax. Another way Haskell is “mathy”!
A simple list comprehension:

[x^2 | x <- [1..10]] 1 2 3 Output function: function that applies to the members of the list we indicate. Another way to map! The pipe separates input list from output function The input set: a “generator” list and a variable that represents the elements that will be drawn from that list This list comprehension produces a new list that includes the square of every number from 1 to 10: [1,4,9,16,25,36,49,64,81,100] List comprehensions, continued List comprehensions can contain predicates, which make list comprehensions act like filters, because the predicate limits the elements drawn from the generator list: [x^2 | x <- [1..10], mod x 2 == 0] Here we’ve specified that the only elements to take from the generator list as x are those that are even. [4, 16, 36, 64, 100] You can have multiple predicates, separated by commas. List comprehensions, continued To be clear, the output function could simply be the identity function: [x | x <- [1..10], mod x 2 == 0] [2,4,6,8,10] List comprehensions, continued List comprehensions can use multiple generator lists: [x^y | x <- [1..10], y <- [2,3]] [1,1,4,8,9,27,16,25,125] What’s going on here? [12, 13, 22, 23, 32, 33, 42, 43 etc.] You can still add predicates with multiple generators: [x^y | x <- [1..10], y <- [2,3], mod x 2 == 0] [4,8,16,64,36,216,64,512,100,1000] [x * 2 | x <- [1..10]] [2,4,6,8,10,12,14,16,18,20] [x | x <- [10..], x*x < 200] [10,11,12,13,14] [x | x <- [1..200], mod x 53 == 0] [53,106,159] List comprehensions closely follow set builder notation from math 19 Using List Comprehensions in Functions You can define functions that take a list or several lists as arguments and return the result of a list comprehension: > evens :: [Int] -> [Int]
> evens ls = [x | x <- ls, mod x 2 == 0] > evens [1..10]

[2,4,6,8,10]

Participation Quiz:
List Comprehensions

List Comprehensions, Reviewed
[x^y + a | x <- [1..3], a <- [3,4], y <- [2,3]]   What order? One possibility: 12 + 3, 12 + 4, 13 + 3, 13 + 4, 22 + 3, 22 + 4, 23 + 3, 23 + 4 (etc) Another possibility: 12 + 3, 13 + 3, 12 + 4, 13 + 4, 22 + 3, 23 + 3, 22 + 4, 23 + 4 (etc) List Comprehensions, Reviewed [x^y + a | x <- [1..3], a <- [3,4], y <- [2,3]]   What order? Answer: 12 + 3, 13 + 3, 12 + 4, 13 + 4, 22 + 3, 23 + 3, 22 + 4, 23 + 4 (etc) Keep the innermost values constant and vary the outer values. Answers Function Composition A “composed” function passes the result of applying one function as an argument to another function. f ° g (f (g x)) h(x) = (f (g x)) Function Composition You can compose functions in Racket, too: (define (find3MostFreqWds ls) (take (sortListDescFreq (frequencyLs (sortListAlphab (mapToLowercase ls)))) 3)) 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

Function Composition
f = even.negate.sum
f [1,2,3,4]
true

What is the type of f?
Well, what type does sum take, what type does even take, and what does even return?
f :: Integral a => [a] -> Bool
Num p => [p] -> p
sum [] = 0
sum (x:xs) = x + sum xs

Sum takes Nums, while Even takes only whole numbers (Integrals), a subcategory of Nums. Integral includes only integral (whole) numbers. In this typeclass are Int and Integer. “Integer” is an arbitrary precision type: it will hold any number no matter how big, up to the limit of your machine’s memory. “Int” is the more common 32 or 64 bit integer. 

27

What would happen?
(sum.map even.filter (<100)) [1..200] Type error: sum expects a list of Nums, not Booleans. (sum.map (+ 1).filter (<100)) [1..200] 5049 /docProps/thumbnail.jpeg