# 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