CS代考计算机代写 data structure algorithm python Haskell Java javascript Introduction to Functional Programming in Haskell

Introduction to Functional Programming in Haskell
1 / 53

Outline
Why learn functional programming?
The essence of functional programming
What is a function?
Equational reasoning
First-order vs. higher-order functions Lazy evaluation
How to functional program
Haskell style
Functional programming workflow Data types
Type classes
Type-directed programming Refactoring (bonus section)
Type inference
2 / 53

Outline
Why learn functional programming?
The essence of functional programming How to functional program
Type inference
Why learn functional programming?
3 / 53

Why learn (pure) functional programming?
1. This course: strong correspondence of core concepts to PL theory • abstract syntax can be represented by algebraic data types
• denotational semantics can be represented by functions
2. It will make you a better (imperative) programmer • forces you to think recursively and compositionally • forces you to minimize use of state
. . . essential skills for solving big problems
3. It is the future!
• more scalable and parallelizable (MapReduce)
• functional features have been added to most mainstream languages • many cool new libraries built around functional paradigm
Why learn functional programming?
4 / 53

Outline
Why learn functional programming?
The essence of functional programming
What is a function?
Equational reasoning
First-order vs. higher-order functions Lazy evaluation
How to functional program Type inference
The essence of functional programming
5 / 53

What is a (pure) function?
A function is pure if:
• it always returns the same output for the same inputs • it doesn’t do anything else — no “side effects”
In Haskell: whenever we say “function” we mean a pure function!
The essence of functional programming
6 / 53

What are and aren’t functions?
Always functions:
• mathematical functions f (x) = x2 + 2x + 3 • encryption and compression algorithms
Usually not functions:
• C, Python, JavaScript, . . . “functions” (procedures) • Java, C#, Ruby, . . . methods
Haskell only allows you to write (pure) functions!
The essence of functional programming
7 / 53

Why procedures/methods aren’t functions
The essence of functional programming
8 / 53
• output depends on environment • may perform arbitrary side effects

Outline
Why learn functional programming?
The essence of functional programming
What is a function?
Equational reasoning
First-order vs. higher-order functions Lazy evaluation
How to functional program Type inference
The essence of functional programming
9 / 53

Getting into the Haskell mindset
Haskell
sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs
In Haskell, “=” means is not change to! The essence of functional programming
Java
int sum(List xs) {
int s = 0;
for (int x : xs) {
s = s + x; }
return s; }
10 / 53

Getting into the Haskell mindset
Quicksort in Haskell
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort (filter (<= x) xs) ++ x : qsort (filter (> x) xs)
Quicksort in C
void qsort(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) { swap(i, j); i++; j--; } } if (low < j) qsort(low, j); qsort(i, high); } void swap(int i, int j) { int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; } The essence of functional programming 11 / 53 Referential transparency a.k.a. referent without changing the overall program behavior An expression can be replaced by its value length [1,2,3] + 4 ⇒ 3+4 what if length was a Java method? Corollary: an expression can be replaced by any expression with the same value without changing program behavior Supports equational reasoning The essence of functional programming 12 / 53 Equational reasoning Computation is just substitution! sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs
equations
sum [2,3,4]
⇒ sum (2:(3:(4:[])))
⇒ 2 + sum (3:(4:[]))
⇒ 2+3+sum(4:[])
⇒ 2+3+4+sum[]
⇒ 2+3+4+0 ⇒9
The essence of functional programming
13 / 53

Describing computations
Function definition: a list of equations that relate inputs to output • matched top-to-bottom
• applied left-to-right
Example: reversing a list
imperative view: functional view:
how do I rearrange the elements in the list? # how is a list related to its reversal?
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
The essence of functional programming
14 / 53

Outline
Why learn functional programming?
The essence of functional programming
What is a function?
Equational reasoning
First-order vs. higher-order functions Lazy evaluation
How to functional program Type inference
The essence of functional programming
15 / 53

First-order functions
Examples
• cos :: Float -> Float • even :: Int -> Bool
• length :: [a] -> Int
The essence of functional programming
16 / 53

Higher-order functions
Examples
• map :: (a -> b) -> [a] -> [b]
• filter :: (a -> Bool) -> [a] -> [a]
• (.) :: (b -> c) -> (a -> b) -> a -> c
The essence of functional programming
17 / 53

Higher-order functions as control structures
map: loop for doing something to each element in a list
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
map f [2,3,4,5] = [f 2, f 3, f 4, f 5]
map even [2,3,4,5]
= [even 2, even 3, even 4, even 5]
= [True,False,True,False]
fold: loop for aggregating elements in a list
foldr :: (a->b->b) -> b -> [a] -> b
foldr f y [] = y
foldr f y (x:xs) = f x (foldr f y xs)
foldr f y [2,3,4] = f 2 (f 3 (f 4 y))
foldr (+) 0 [2,3,4]
= (+) 2 ((+) 3 ((+) 4 0)) = 2 + (3 + (4 + 0))
=9
The essence of functional programming
18 / 53

Function composition
Can create new functions by composing existing functions • apply the second function, then apply the first
Function composition
(.) :: (b -> c) -> (a -> b) -> a -> c f . g = \x -> f (g x)
Types of existing functions
not :: Bool -> Bool
succ :: Int -> Int
even :: Int -> Bool
head :: [a] -> a
tail :: [a] -> [a]
(f . g) x = f (g x)
Definitions of new functions
plus2 = succ . succ
odd = not . even
second = head . tail
drop2 = tail . tail
The essence of functional programming
19 / 53

Currying / partial application
In Haskell, functions that take multiple arguments are
implicitly higher order
plus :: Int -> Int -> Int
Haskell Curry
plus 2 3
Curried
increment :: Int -> Int
increment = plus 1
plus :: Int -> Int -> Int
Uncurried plus (2,3) plus :: (Int,Int) -> Int
The essence of functional programming
20 / 53
a pair of ints

Outline
Why learn functional programming?
The essence of functional programming
What is a function?
Equational reasoning
First-order vs. higher-order functions Lazy evaluation
How to functional program Type inference
The essence of functional programming
21 / 53

Lazy evaluation
In Haskell, expressions are reduced: • only when needed
• at most once
nats :: [Int]
nats = 1 : map (+1) nats
fact :: Int -> Int
fact n = product (take n nats)
Supports:
• infinite data structures • separation of concerns
min3 :: [Int] -> [Int]
min3 = take 3 . sort
What is the running time of this function?
John Hughes, Why Functional Programming Matters, 1989 The essence of functional programming 22 / 53

Outline
Why learn functional programming?
The essence of functional programming
How to functional program
Haskell style
Functional programming workflow Data types
Type classes
Type-directed programming Refactoring (bonus section)
Type inference
How to functional program
23 / 53

Good Haskell style
How to functional program
24 / 53
Why it matters:
• layout is significant!
• eliminate misconceptions • we care about elegance
Easy stuff:
• use spaces! (tabs cause layout errors) • align patterns and guards
See style guides on course web page

Formatting function applications
Function application:
• is just a space
• associates to the left • binds most strongly
f(x) fx
Use parentheses only to override this behavior: • f (g x)
• f (x + y)
How to functional program
25 / 53
(f x) y
(f x) + (g y)
f x y
f x + g y

Outline
Why learn functional programming?
The essence of functional programming
How to functional program
Haskell style
Functional programming workflow
Data types
Type classes
Type-directed programming Refactoring (bonus section)
Type inference
How to functional program
26 / 53

FP workflow (simple)
How to functional program
27 / 53
“obsessive compulsive refactoring disorder”

FP workflow (detailed)
Norman Ramsey, On Teaching “How to Design Programs”, ICFP’14 How to functional program 28 / 53

Algebraic data types Data type definition
• introduces new type of value • enumerates ways to construct
values of this type
Some example data types
data Bool = True | False
data Nat = Zero | Succ Nat
data Tree = Node Int Tree Tree
| Leaf Int
Definitions consists of . . .
• a type name
• a list of data constructors with argument types
Definition is inductive
• the arguments may recursively
include the type being defined
• the constructors are the only way to build values of this type
How to functional program
30 / 53

Anatomy of a data type definition
type name
data Expr = Lit Int
| Plus Expr Expr
cases
data constructor
types of arguments
Example: 2 + 3 + 4 Plus (Lit 2)
(Plus
(Lit 3) (Lit 4))
How to functional program
31 / 53

FP data types vs. OO classes
Haskell Java
data Tree = Node Int Tree Tree
| Leaf
abstract class Tree { … }
class Node extends Tree {
int label;
Tree left, right;
…
}
class Leaf extends Tree { … }
• merger of type- and value-level • set of cases open
• set of operations closed
How to functional program
32 / 53
• separation of type- and value-level • set of cases closed
• set of operations open
Extensibility of cases vs. operations = the “expression problem”

Type parameters
type parameter (Like generics in Java)
data List a = Nil
| Cons a (List a)
reference to type parameter
Specialized lists
type IntList = List Int
type CharList = List Char
type RaggedMatrix a = List (List a)
recursive reference to type
How to functional program
33 / 53

What is a type class?
1. an interface that is supported by many different types
2. a set of types that have a common behavior
class Eq a where
(==) :: a -> a -> Bool
class Show a where
show :: a -> String
class Num a where
(+) :: a -> a -> a
(*) :: a -> a -> a
negate :: a -> a
…
types whose values can be compared for equality
types whose values can be shown as strings
typeswhosevaluescanbe manipulated like numbers
How to functional program
35 / 53

Type constraints
class Eq a where
(==) :: a -> a -> Bool
List elements can be of any type
length :: [a] -> Int
length [] =0
length (_:xs) = 1 + length xs
List elements must support equality!
elem :: Eq a => a -> [a] -> Bool
elem _ [] = False
elem y (x:xs) = x == y || elem y xs
use method ⇒ add type class constraint
How to functional program
36 / 53

Tools for defining functions Recursion and other functions
sum :: [Int] -> Int
sum xs = if null xs then 0
else head xs + sum (tail xs)
(1) case analysis
Pattern matching
sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs
(2) decomposition
Higher-order functions
sum :: [Int] -> Int
sum = foldr (+) 0
How to functional program
38 / 53
no recursion or variables needed!

What is type-directed programming?
Use the type of a function to help write its body
How to functional program 39 / 53

Type-directed programming
Basic goal: transform values of argument types into result type If argument type is … If result type is …
How to functional program
40 / 53
• atomic type (e.g. Int, Char) • apply functions to it
• algebraic data type
• use pattern matching
• caseanalysis
• decomposeintoparts
• function type
• apply it to something
• atomic type
• output of another function
• algebraic data type
• build with data constructor
• function type
• function composition or
partial application
• build with lambda abstraction

Refactoring in the FP workflow
How to functional program
42 / 53
“obsessive compulsive refactoring disorder”
Motivations:
• separate concerns
• promote reuse
• promote understandability • gain insights

Refactoring relations
Semantics-preserving laws can prove with equational reasoning + induction • Eta reduction:
\x -> f x ≡ f • Map–map fusion:
mapf.mapg ≡ map(f.g) • Fold–map fusion:
foldrfb.mapg ≡ foldr(f.g)b “Algebra of computer programs”
John Backus, Can Programming be Liberated from the von Neumann Style?, ACM Turing Award Lecture, 1978 How to functional program
43 / 53

Strategy: systematic generalization
commas :: [String] -> [String]
commas [] = []
commas [x] = [x]
commas (x:xs) = x : “, ” : commas xs
commas :: [String] -> [String]
commas = intersperse “, ”
Introduce parameters for constants
seps :: String -> [String] -> [String]
seps _ [] = []
seps _ [x] = [x]
seps s (x:xs) = x : s : seps s xs
Broaden the types
intersperse :: a -> [a] -> [a]
intersperse _ [] = []
intersperse _ [x] = [x]
intersperse s (x:xs) = x : s : intersperse s xs
How to functional program
44 / 53

Strategy: abstract repeated templates
abstract (v): extract and make reusable (as a function)
showResult :: Maybe Float -> String
showResult Nothing = “ERROR”
showResult (Just v) = show v
moveCommand :: Maybe Dir -> Command
moveCommand Nothing = Stay
moveCommand (Just d) = Move d
safeAdd :: Int -> Maybe Int -> Int
safeAdd x Nothing = x
safeAdd x (Just y) = x + y
Repeated structure:
• pattern match
• default value if Nothing
• apply function to contents if Just
How to functional program
45 / 53

Strategy: abstract repeated templates
Describe repeated structure in function
maybe :: b -> (a -> b) -> Maybe a -> b maybe b _ Nothing = b
maybe _ f (Just a) = f a
Reuse in implementations
showResult = maybe “ERROR” show
moveCommand = maybe Stay Move
safeAdd x = maybe x (x+)
How to functional program
46 / 53

Refactoring data types
data Expr = Var Name
| Add Expr Expr
| Sub Expr Expr
| Mul Expr Expr
vars :: Expr -> [Name]
vars (Var x) = [x]
vars (Add l r) = vars l ++ vars r
vars (Sub l r) = vars l ++ vars r
vars (Mul l r) = vars l ++ vars r
eval :: Env -> Expr -> Int
How to functional program
47 / 53
eval m (Var x)
eval m (Add l r)
eval m (Sub l r)
eval m (Mul l r)
=getxm
= eval m l + eval m r = eval m l – eval m r = eval m l * eval m r

Refactoring data types
Factor out shared structure
data Expr = Var Name
| BinOp Op Expr Expr
data Op = Add | Sub | Mul
vars :: Expr -> [Name]
vars (Var x) = [x]
vars (BinOp _ l r) = vars l ++ vars r
eval :: Env -> Expr -> Int
eval m (Var x) = get x m
eval m (BinOp o l r) = op o (eval m l) (eval m r)
where
op Add = (+)
op Sub = (-)
op Mul = (*)
How to functional program
48 / 53

Outline
Type inference
49 / 53
Why learn functional programming? The essence of functional programming How to functional program
Type inference

Type inference
How to perform type inference (bottom-up strategy)
For each literal, data constructor, and named function: write down the type Repeat until you know the type of the whole expression:
1. find an application e1 e2 where you know e1::T1 and e2::T2 2. T1 should be a function type T1 = Targ ->Tres
3. check that the argument type is what the function expects: Targ =? T2 􏰂 σ • this step is called type unification
• σ is an assignment of the type variables to make the two sides equal
4. write down e1 e2 :: σTres (σTres = Tres with type variables substituted) If any of these steps fails, it is a type error!
Type inference
50 / 53

Type unification (1/2)
Find a type variable assignment (σ) that makes the two sides equal Unification by example
T1 =? T2 a =? Int
Bool =? a a =? b
Int =? Bool
a =? Int -> Bool
a -> Bool =? Int -> Bool Type inference
􏰂 σ
􏰂 {a=Int}
􏰂 {a=Bool}
􏰂 {a=b}
􏰂 Fail!
􏰂 {a=Int -> Bool} 􏰂 {a=Int}
51 / 53

Type unification (2/2)
Find a type variable assignment (σ) that makes the two sides equal Unification by example
T1 =? a->b =?
Int->a =? a->b =? a -> b =? a -> b =?
(a->b)->c =? Type inference
T2
Int -> Bool
b -> Bool
Int
Int -> Bool -> Char (Int -> Bool) -> Char Int -> Bool -> Char
􏰂 σ
􏰂 {a=Int,b=Bool}
􏰂 {a=Bool,b=Int}
􏰂 Fail!
􏰂 {a=Int,b=Bool -> Char} 􏰂 {a =Int -> Bool,b =Char} 􏰂 Fail!
52 / 53

Exercises
Given
data Maybe a = Nothing | Just a
gt :: Int -> Int -> Bool
map ::(a->b)->[a]->[b]
(.) ::(b->c)->(a->b)->a->c
1. Just
2. not even 3
3. not (even 3)
4. not . even
5. even . not
6. map (Just . even)
not :: Bool -> Bool even::Int->Bool
Type inference
53 / 53

Related Posts