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!

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:

> 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.

> 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

Published by admin

Leave a Reply Cancel reply