CS计算机代考程序代写 Haskell compiler data structure Lambda Calculus scheme PowerPoint Presentation

PowerPoint Presentation

Haskell!

Intro to Haskell
Named after logician Haskell Curry (1900-1982)
A more modern functional language: created late 1980’s

Many similarities with Racket:
Programming with expressions, not statements
– No mutation! Everything is immutable.
Functions are values
– Can be passed as parameters to and returned from functions
Lists are the fundamental data structure

2

Intro to Haskell
Named after logician Haskell Curry (1900-1982)
A more modern functional language
Key distinctions from Racket:
Lazy Evaluation
An Extensive Type System
3

Scheme

Intro to Haskell
Named after logician Haskell Curry (1900-1982)
A more modern functional language
Key distinctions from Racket:
Lazy Evaluation
An Extensive Type System
Cleaner syntax
Notation even closer to mathematics
Infinite lists
Pattern matching
Purely functional

6

How do we write functions in Haskell?
With a more minimal syntax than Racket:
triple x = x * 3
[1] [2][3] [4]
[1] name of the function (note: camelCase)
[2] parameters, separated only by whitespace
[3] = binds the name to the definition and cannot be re-bound; pronounced “is”: “triple x is x times 3.”
[4] body of function (note: infix notation)

Actually, Haskell operator notation is infix or prefix
Infix notation tends to be the default preference:

5*(4+6)-2 — evaluates to 48
5*4^2-2 — evaluates to 78

… but you can also force prefix notation by enclosing operators
in parentheses:

(-) ((*) 5 ((+) 4 6)) 2

Racket
(define (identity x) x)

(define (add-one x)
(+ x 1))

(define (square x)
(* x x))

(define (add-stuff-to-five a b)
(+ a b 5))

(define (add-stuff x)
(lambda (y) (+ x y))

Haskell
identity x = x

addOne x = x + 1

square x = x * x

addStuffToFive a b = a + b + 5

addStuff x y = x + y
WHAT THE…???

Racket

Returning a lambda function is clearly possible in Racket, but must be explicitly coded.

Haskell: Every function is “curried” by default

Currying
Currying is the process of transforming a function that takes multiple arguments, into a function that takes just a single argument and returns another function which accepts further arguments, one by one.

All functions in Haskell take just one argument. But looking at function notation, this fact is not necessarily apparent. For example, take a simple division function:
div x y = x / y
div 11.0 2.0
5.5

This looks like a function definition that takes two arguments, x and y, at the same time.

But in fact, Haskell sees (div 11.0 2.0) as a two-part process!
(div 11) is, by itself, a meaningful evaluation for Haskell. It yields:
y -> 11 / y “A new procedure (lambda) that takes a y and returns
11 divided by y”
(div 11.0 2.0) is more properly ((div 11.0) 2.0)  5.5

The Lambda Calculus rears its head again…
In the LC, all definitions with multiple arguments take those arguments one at a time:
λfunc.λarg.(func arg)

This function takes one argument (func), then returns a new function that takes one argument (arg), then returns the application of the first argument to the second argument.

Haskell purely implements the lambda calculus.

As in the lambda calculus, all functions in Haskell take one argument and return one result. The way to think of this is that, in Haskell, when it seems we are passing multiple arguments to a function, we are actually applying a series of nested functions, each with one argument. In Haskell, this is called “currying.”

Haskell:
Which of the following functions are equivalent?
func x y z = x * y * z
func x y = z -> x * y * z
func x = y -> z -> x * y * z
func = x -> y -> z -> x * y * z

All four are equivalent.

addStuffToFive a b = a + b + 5

f = addStuffToFive 6

 -> 6 + b + 5

b.(6 + b + 5)

f 10

21

But why take only one argument and return a new function that expects a new argument, rather than accept all parameters up front??
This kind of higher-orderism is required by built-ins like map/filter/fold
It also enables code re-use

Racket:
(define (add-stuff-to x) (lambda (y) (+ x y))
(map (add-stuff-to 5) (list 1 2 3))  (list 6 7 8)

Haskell:
addStuff x y = x + y
map (addStuff 5) [1, 2, 3]  [6, 7, 8]

Remember our revenue program in Racket?

Even tinier in Haskell

Partial Application
When a function is purposefully supplied with fewer arguments than it expects, we say that it is “partially applied”:

add x y = x + y

> add 1

Again, because Haskell functions are curried by default, partial application automatically creates a new function that is ready to accept the remaining argument(s):

add x y = x + y > add 1
add = x -> y -> x + y y -> 1 + y

If you like, you can think of partial application as “preloading” a function with some of its arguments.

Hmm, but Haskell function notation lets me at least pretend that arguments are passed in all at once. So, can I just ignore this one-at-a-time business?
Nope. Haskell has a strict type system, which strongly recommends lambda calculus-style type signatures to be declared above every function.

What is a type signature?
Up until this slide, we’ve omitted the type signature. But in fact, a Haskell function is defined by writing its type signature on the first line, and its parameters and body on the remaining lines.

A type signature tells the compiler the expected types of the arguments to, and the type of the returned value of, a function.

max3 :: Int -> Int -> Int -> Int
max3 x y z
| x>=y && x>=z = x
| y>=x && y>=z = y
| otherwise = z

Sometimes you will also see “type signature” written as “type declaration.”

If the type signature is omitted, the Haskell compiler will infer it.
Functions are polymorphic: they can use variables of different types at different times
Omitting the type signature gives the function its broadest possible meaning
FOR EXAMPLE:
max3 x y z
| x>=y && x>=z = x
| y>=x && y>=z = y
| otherwise = z

> max3 6 4 1
6
> max3 “alpha” “beta” “gamma”
“gamma”
The type that Haskell infers for max3 is Ord a => a -> a -> a -> a

Providing type signatures is a “best practice”

Haskell’s type system clarifies thinking and expresses program structure
Writing type signatures serves as a form of code documentation
Type ambiguity is possible. But providing type signatures turns run-time errors into compile-time errors.

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

25

Recommended Reading:
“Learn You a Haskell for Great Good”
Please do invest time in this resource,
it has great explanations

Match the function to its type signature
not

length

concat

head

(<) __ :: [a] -> a

__ :: [[a]] -> [a]

__ :: Bool -> Bool

__ :: [a] -> Int

__ :: Ord a => a -> a -> Bool

Match the function to its type signature

head :: [a] -> a

concat :: [[a]] -> [a]

not :: Bool -> Bool

length :: [a] -> Int

(<) :: Ord a => a -> a -> Bool

Participation Quiz:
Match the Haskell function
with its type signature

Function Type Signature Description

“Cons (:) takes an element of type a and then returns a function that takes
a list of elements of type a, and then returns a new list of elements of type a.”

Heads Up: Midterm
One month away (Wednesday, March 24th)
Upcoming 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