程序代写代做 flex Java Haskell data structure C 1 Haskell

1 Haskell
CS 381 • Haskell
1
λ

Change vs. Description
private void quicksort(int low, int high) {
int i = low, j = high;
int pivot = numbers[low + (high-low)/2];
while (i <= j) { while (numbers[i] < pivot) { i++; } while (numbers[j] > pivot) {
j–; }
if (i <= j) { exchange(i, j); i++; j--; } } if (low < j) quicksort(low, j); if (i < high) Quicksort in Java invented the “=” sign in 1557 } quicksort(i, high); Same symbol – completely different meaning! qsort :: Ord a ⇒ [a] → [a] qsort [] = [] Robert Recorde Quicksort in Haskell private void exchange(int i, int j) { int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } qsort (x:xs) = qsort [y | y←xs, y<=x] ++ [x] ++ qsort [y | y←xs, y>x]
CS 381 • Haskell
2

The Meaning of “=” i=i+1
Java, C, … (… and maybe on Fox News)
S ↦ S – {(i, S(i))} ∪ {(i, S(i)+1)} inew = iold + 1
Haskell
Math, Logic, Philosophy, …
… and the rest of the rational world
undefined
In Haskell:
No state, No assignment!
CS 381 • Haskell
3
(There are monads …)

Computation in Haskell
S →T
Function that maps values of type S to values of type T
Description of Computation: Equations of how to construct output from input
[Int] : list of Int
[a]
: list of anything
reverse :: [a] → [a]
Concatenate 2 lists
Example: reversing a list
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
list of single element x
CS 381 • Haskell
4
Empty list
Nonempty list with first element and x rest list xs

CS 381 • Haskell
5
Zoom Poll
About Recursion

Substituting Equals for Equals
reverse :: [a] → [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
xs x
(1:[2,3,4])
xs x
(2:[3,4])
Pattern Matching:
(1) Conditional (2) Bindings
(:) :: a →[a]→[a] (++) :: [a] → [a] → [a]
reverse [1,2,3,4] =
reverse [2,3,4] ++ [1] =
reverse [3,4] ++ [2] ++ [1] =
reverse [4] ++ [3] ++ [2] ++ [1] =
reverse [] ++ [4] ++ [3] ++ [2] ++ [1] =
[] ++ [4] ++ [3] ++ [2] ++ [1] =
[4,3,2,1]
CS 381 • Haskell
6

CS 381 • Haskell
7
Learning Haskell: Baby Steps
• • • • • • • •
Values and Basic Types
Expressions (applying functions to values and expressions) Function Definitions (Type Signatures, Parameters, Equations) Pattern Guards
Recursion
Lists and Pattern Matching
Higher-Order Functions
Data Types (Constructors, Pattern Matching)

• • • • • • • •
Learning Haskell
Values and Basic Types
Expressions (applying functions to values and expressions) Function Definitions (Type Signatures, Parameters, Equations) Pattern Guards
Recursion
Lists and Pattern Matching
Higher-Order Functions
Data Types (Constructors, Pattern Matching)
CS 381 • Haskell
8

Exercises
Write an expression that computes the larger value of 5 and 6 (don’t use the function max)
Write an expression that tests whether 2*3 is equal to 3+3
if 5>6 then 5 else 6
if 2*3==3+3 then True else False
2*3==3+3
CS 381 • Haskell
9

Exercises
Define a function that tests whether a number is positive using pattern guards
positive :: Int → Bool
positive x = if x>=0 then True else False
positive :: Int → Bool positive x | x>=0 = True
| otherwise = False
positive :: Int → Bool positive x = x>=0
CS 381 • Haskell
11

Exercises
Define a function for computing Fibonacci numbers
Define a function that tests whether a number is even
fib :: Int → Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
fib :: Int → Int even 0 = True
even 1 = False
even n = even (n-2)
CS 381 • Haskell
13

Exercises
Define the function length :: [a] → Int
Evaluate the expressions that don’t contain an error
(:) :: a →[a]→[a] (++) :: [a] → [a] → [a]
head :: [a] → a head (x:_) = x
tail :: [a] → [a] tail (_:xs) = xs
sum :: [Int] → Int
sum [] = 0
sum (x:xs) = x + sum xs
length :: [a] → Int
length [] = 0
length (_:xs) = 1 + length xs
xs = [1,2,3]
=9
✗
= [1,2,3,3] = [6,3]
✗
= [5,1,2,3]
✗
✗
= [[2,3],[5]] = [[1,2,3]]
CS 381 • Haskell
15
sum xs + length xs
xs ++ length xs
xs ++ [length xs]
[sum xs, length xs]
[xs, length xs]
5:xs
xs:5
[tail xs,5]
[tail xs,[5]]
tail [xs,xs]

CS 381 • Haskell
16
Zoom Poll
Haskell list functions

From Iteration to Recursion
f
fac
result = 1
while argument > 1 do { result = result * argument argument = argument – 1
}
result = Start
while Condition[argument] do {
result = Update[result,argument]
argument = Simplify[argument] }
f argument | Condition[argument] = Update[f(Simplify[argument]),argument] | otherwise = Start
fac argument | argument > 1 = fac(argument – 1) * argument | otherwise = 1
CS381•Haskell
fac 1 = 1 facn=n*fac(n-1) 17

From Iteration to Recursion
f
length result = 0
while not (null (list)) do { result = result + 1
list = list.next
}
result = Start
while Condition[argument] do {
result = Update[result,argument]
argument = Simplify[argument] }
f argument | Condition[argument] = Update[f(Simplify[argument]),argument] | otherwise = Start
length list | not (null list) = length (tail list) + 1 | otherwise = 0
CS381•Haskell
length [] = 0 length(_:xs)=1+lengthxs 18

3 Ways to Define Functions
Recursion
sum :: [Int] → Int
sum xs = if null xs then 0
else head xs + sum (tail xs)
(1) Case analysis
head :: [a] → a head (x:_) = x
tail :: [a] → [a] tail (_:xs) = xs
Pattern Matching
Higher-Order
Functions
sum :: [Int] → Int
sum [] = 0
sum (x:xs) = x + sum xs
(2) Data decomposition
CS 381 • Haskell
19
sum :: [Int] → Int  
sum = foldr (+) 0 variables & recursion not needed!

Higher-Order Functions
map f [x1, …, xk] = [f x1, …, f xk]
HOFs ≡ Control
Structures
map :: (a → b) → [a] → [b] map f [] = []
map f (x:xs) = f x:map f xs
Loop for processing elements independently
fold f u [x1, …, xk] = x1 `f` … `f` xk `f` u
Loop for aggregating elements
fold :: (a → b → b) → b → [a] → b fold f u [] = u
fold f u (x:xs) = x `f` (fold f u xs)
sum = fold (+) 0
fac n = fold (*) 1 [2 .. n]
CS 381 • Haskell
21

Higher-Order Functions
Function composition
(f . g) x = f (g x)
(.) :: (b → c) → (a → b) → a → c
f . g = \x → f (g x)
plus2 = succ . succ
odd = not . even
snd = head . tail
drop2 = tail . tail
succ :: Int → Int even :: Int → Bool not :: Bool → Bool head :: [a] → a tail :: [a] → [a]
CS 381 • Haskell
22

Exercises
Is the function th well defined?
If so, what does it do and what is its type?
th :: ?
th = tail . head
(.) :: (b → c) → (a → b) → a → c
th :: [[a]] → [a]
head :: [a] → a head (x:_) = x
What does the expression map f . map g compute? How can it be rewritten?
tail :: [a] → [a] tail (_:xs) = xs
map f . map g = map (f . g)
CS 381 • Haskell
23

Implement revmap using pattern matching
map :: (a → b) → [a] → [b] map f [] = []
map f (x:xs) = f x:map f xs
reverse :: [a] → [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
Exercises
revmap :: (a → b) → [a] → [b]
revmap f [] = []
revmap f (x:xs) = revmap f xs ++ [f x]
Implement revmap using function composition
(.) :: (b → c) → (a → b) → a → c
revmap :: (a → b) → [a] → [b] revmap f = reverse . map f
CS 381 • Haskell
24
revmap f = map f . reverse

Find expressions to …
… increment elements in xs by 1
… increment elements in ys by 1 … find the last element in xs
Define the function
last :: [a] → a
Exercises
xs = [1,2,3]
ys = [xs,[7]]
map succ xs = [2,3,4]
map (map succ) ys = [[2,3,4],[8]]
head (reverse xs) = 3
✗
= [6,7] = [7]
= [3,7] =7
Evaluate all the expressions that don’t contain an error
map sum xs
map sum ys
last ys
map last ys
last (last ys)
last :: [a] → a
last [x] = x
last (_:xs) = last xs
CS 381 • Haskell
25

data Nat = Zero
| Succ Nat
Data Constructors
≈ C++/Java object constructor, but: (1) Inspection by pattern matching!
(2) Immutable!
Data types value are read-only
Zero
Succ Nat two = Succ (Succ Zero) X
Succ
Empty
Cons I3n1t List
Zero
data List = Empty
| Cons Int List
Cons 7
Empty
CS 381 • Haskell
27
xs = Cons 31 (Cons 7 Empty)

More on Data Constructors
data Nat = Zero
| Succ Nat
data List = Empty
| Cons Int List
data List = Empty
| Cons Nat List
one = Succ Zero
two = Succ one
ys = Cons one (Cons two Empty)
two = Succ (Succ Zero)
Succ
xs = Cons 1 (Cons 2 Empty) Cons 1
Succ
Zero
Cons 2
Empty
two
ys Cons
Succ
one Succ
Cons
Zero
Empty
CS 381 • Haskell
28

Avoiding Sharing
data List = Empty
| Cons Nat List
one = Succ Zero
two = Succ one
ys = Cons one (Cons two Empty)
two
ys Cons
Succ
one Succ
Cons
Zero
Empty
one Succ
Zero
one = Succ Zero
two = Succ (Succ Zero)
ys = Cons one (Cons two Empty)
two
Succ
Succ
Zero
ys Cons
Cons
Empty
CS 381 • Haskell
29

Cyclic Data Structures
data List = Empty
| Cons Int List
Intensional description of an infinite list
ones = Cons 1 ones
morse = Cons 1 (Cons 0 morse)
xs = Cons 1 (Cons 2 Empty) Cons 1
Cons 1
Cons 1
Cons 1
Cons 2
Empty
Cons 0
zeros = Cons 0 zeros
big = Cons 1 zeros
Cons 0
CS 381 • Haskell
30

Changing Data Structures
data List = Empty
| Cons Int List
zs = Cons 1 (Cons 2 (Cons 3 Empty))
Data types value are read-only
Cons 1
Cons 1 chgLast 7 zs
Cons 2
Cons 2
Cons 3
Empty
Cons
7
CS 381 • Haskell
31
chgLast :: Int → List → List chgLast y [x] = [y]
chgLast y (x:xs) = x:chgLast y xs

CS 381 • Haskell
32
Summary: Haskell so far
•Functions (vs. state manipulation)
•No side effects
•Higher-Order Functions (i.e. flexible control structures) •Recursion
•Data Types (constructors and pattern matching)
•More Haskell features:
list comprehensions, where blocks,

“Curried” Dinners are More Spicy
Experience dinner(Drink d, Entree e, Dessert f){…}
dinner(wine, pasta, pie)
Must provide all arguments at once
Haskell
dinner :: Drink → Entree → Dessert → Experience dinner wine :: Entree → Dessert → Experience
Partial function application is possible
CS 381 • Haskell
33

Curry-Howard Isomorphism
The values of a type are the proofs for the proposition represented by it.
Proof for Proposition Program : Type
even: Int→Bool
sort : List → SortedList
Currying
(a,b) → c
✓
a→b→c ≡
a → (b → c)
A∧B⇒C
(A ∧ B) ⇒ C ¬(A ∧ B) ∨ C ¬A ∨ ¬B ∨ C A ⇒ (¬B ∨ C) A ⇒ (B ⇒ C)
CS 381 • Haskell
34

Research in PL ?
CS 381 • Haskell
Haskell?
Haskell
Research Experience as Undergrad ? Grad School ?
35

Related Posts