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

PowerPoint Presentation

Review: Writing functions

Haskell has a cleaner syntax than Racket.

triple x = x * 3

isEven x = x `mod` 2 == 0

getY m b x = m * x + b

Review: Currying

A function that is “curried” takes multiple arguments one at a time, always returning a new function in order to grab the next argument. Functions in both the Lambda Calculus and Haskell are curried.

For example:

addStuff x y = x + y

really means:

addStuff = x -> (y -> (x + y))

Review: Currying

RACKET:

(define (add-stuff-to-5 x y)

(+ x y 5))

(add-stuff 6)

HASKELL:

addStuffTo5 a b = a + b + 5

addStuffTo5 6

multStuff a b c d = a * b * c * d

multStuff 3 4

-> 6 + b + 5

c -> d -> 3 * 4 * c * d

Test yourself

getY m b x = m * x + b

getY 6 3

exchngCrncy rate n = rate * n

exchngCrncy 1.1

fahrToCels f = (f – 32) * (5/9)

fahrToCels

x -> 6 * x + 3

-> 1.1 * n

f -> (f – 32) * (5/9)

Review: Type Signatures

We see this underlying “curried” structure of all functions in the format of Haskell type signatures.

Review: Type Signatures

identity :: t -> t

identity x = x

increment :: Int -> Int

increment x = x + 1

plus :: Num a => a -> a -> a

plus x y = x + y

filter :: (a -> Bool) -> [a] -> [a]

filter

map :: (a -> b) -> [a] -> [b]

map

New: Type Signatures of Partially Applied Functions

getY :: Num a => a -> a -> a -> a

getY m b x = m * x + b

foo = getY 6 3

exchngCrncy :: Num a => a -> a -> a

exchngCrncy rate n = rate * n

bar = exchngCrncy 1.1

fahrToCels :: Num a => a -> a

fahrToCels f = (f – 32) * (5/9)

baz = fahrToCels

foo :: ???

foo:: Num a => a -> a

bar :: ???

bar :: Num a => a -> a

baz :: ???

baz :: Num a => a -> a

New: Conditional Branching

Three definitions of factorial in Haskell:

1. Using if/else

fact1 n = if n==0

then 1

else n*fact1(n-1)

2. Using guards

fact2 n

| n==0 = 1

| otherwise = n*fact2(n-1)

3. Using pattern matching

fact3 0 = 1

fact3 n = n * fact3 (n – 1)

Guards

As in Racket, if/else in Haskell is for when you have one condition and two possible outcomes. You use guards when you have two or more outcomes to choose between. Note: pipes must be indented!

myAbs1 x = if x < 0
then (-x)
else x
myAbs2 x
| x < 0 = (-x)
| otherwise = x
bloodSodium x
| x < 135 = “too low”
| x > 145 = “too high”

| otherwise = “good”

Participation Quiz, part one:

Practicing Guards

Racket

Haskell

Complex numbers: Numbers that are a combination of real and imaginary numbers, such as I (sq ty of -1).

11

Pattern Matching: An alternative to conditional branching

Pattern matching allows us to write functions that can decide between two or more possibilities for returned values, based on matching the value of the argument to the formal parameter:

Pattern Matching: An alternative to conditional branching

Pattern matching allows us to write functions that can decide between two or more possibilities for returned values, based on matching the value of the argument to the formal parameter:

> isItTwo 7

isItTwo :: Int -> Bool

isItTwo 2 = True

isItTwo x = False

Matching a pattern may fail, so it proceeds to the next available pattern to match or succeed.

Pattern Matching: An alternative to conditional branching

Pattern matching allows us to write functions that can decide between two or more possibilities for returned values, based on matching the value of the argument to the formal parameter:

> isItTwo 7

isItTwo :: Int -> Bool

isItTwo 2 = True

isItTwo x = False

Matching a pattern may fail, so it proceeds to the next available pattern to match or succeed.

Pattern Matching

You can also use an underscore to designate that it doesn’t matter what the value is. The underscore also never fails to match:

isItTwo :: Int -> Bool

isItTwo 2 = True

isItTwo _ = False

The underscore is called a “meh”

Order and Exhaustiveness Matter

isItTwo :: Int -> Bool

isItTwo _ = False

isItTwo 2 = True

What will happen if you call isItTwo 2?

The two will match with the meh and False will be returned.

isItTwo :: Int -> Bool

isItTwo 2 = True

isItTwo 3 = False

What will happen if you call isItTwo 4?

Error: Non-exhaustive patterns

Fibonacci three ways in Haskell

Racket:

Haskell:

Pattern matching and guards are two of the ways that Haskell’s syntax is close to mathematical syntax. For example, they resemble piecewise functions in math:

Lists in Haskell

Lists do double duty in Haskell:

As a way to refer to and process a collection of values

As an infinite series of values, usually generated by a function, which allows them to act as a stream data type (a sequence of data elements made available over time)

Infinite lists are only possible because of Haskell’s lazy evaluation strategy

We’ll look at infinite lists and laziness next week

Lists are recursive data types in Haskell, too

Racket

‘(a b c) or (list a b c)

Empty list: ‘()

Create the list that contains a: (cons a ‘())

Create the list that contains a and b: (cons a (cons b ‘()))

Create the list that contains a, b, and c: (cons a (cons b (cons c ‘())))

Haskell

[a,b,c]

Empty list: []

Create the list that contains a:

a : []

Create the list that contains a and b:

a : b : []

Create the list that contains a, b, and c:

a : b : c : []

Lists are recursive data types in Haskell, too

Racket

(list a b c)

car (list a b c)

> a

cdr (list a b c)

> (b (c ‘()))

Haskell

[a,b,c]

head [a, b, c]

> a

tail [a, b, c]

> [b [c [] ] ]

Pattern Matching on Lists

[a, b, c] = a : b : c : []

The fact that lists are recursive data types can be seen in the syntax of this function, which uses pattern matching on its list argument:

myLength :: Num a => [b] -> a

myLength [] = 0

myLength (x:xs) = 1 + myLength xs

Pattern Matching on Lists

What does this function accomplish?

myFunc :: Num a => [a] -> a

myFunc [] = 0

myFunc (x:xs) = x + myFunc xs

Summing the items in a list.

Pattern Matching on Lists

What does this function accomplish?

myFunc :: [Int] -> [Int] -> Bool

myFunc []_ = True

myFunc _[] = True

myFunc (x:xs) (y:ys)

| x == y = myFunc xs ys

myFunc (x:xs) (y:ys)

| x /= y = False

Returns true if the same elements are in the same order in two lists, and false otherwise.

Pattern Matching on Lists

Let’s do this one together:

How would we use pattern matching to write a function that drops the first 3 items in a list?

Participation Quiz, part two:

Pattern Matching

Here’s an implementation for the length of a list that looks like Racket, but isn’t idiomatic in Haskell. Rewrite the Haskell function to use pattern matching instead.

myLength :: Num p => [a] -> p

myLength [] = 0

myLength (x:xs) = 1 + myLength xs

Heads Up: Midterm

Wednesday, March 24th

Schedule:

Two weeks of Haskell

Spring Break

Midterm review day after we return from break

Midterm covers Functional Programming in…

Racket

Lambda Calculus

Haskell

/docProps/thumbnail.jpeg