CS 403: Introduction to functional programming
Stefan D. Bruda
Fall 2021
FUNCTIONAL PROGRAMMING IS PROGRAMMING
WITHOUT. . .
Selective assignments (a[i] = 6 is not allowed)
The goal of an imperative program is to change the state [of the machine]
The goal of a functional programs is to evaluate (reduce, simplify)
expressions
More generally updating assignments (y = x + 1 is fine but x = x + 1 is
not fine)
A variable in an imperative program: a name for a container
There is no proper concept of “variable” in functional programs. What is
called “variable” is a name for an expression
Explicit pointers, storage and storage management
Input/output
Control structures (loops, conditional statements)
Jumps (break, goto, exceptions)
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 1 / 51
WHAT’S LEFT?
Expressions (without side effects)
Referential transparency (i.e., substitutivity, congruence)
Definitions (of constants, functions)
Functions defined almost as in mathematics
Math Haskell
square : N→ N
square(x) = x × x
square :: Integer -> Integer
square x = x * x
A function is defined by a type definition and a set of rewriting rules
The type definition may appear optional, but is not
Types (including higher-order, polymorphic, and recursively-defined)
tuples, lists, trees, shared sub-structures, implicit cycles
Automatic storage management (garbage collection)
Actually we do not care about storage at all; we abstract over the physical
machine instead!
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 2 / 51
SESSIONS, SCRIPTS, EVALUATION
< godel:306/slides > ghci
GHCi, version 7.4.1: http://www.haskell.org/ghc/ 😕 for help
Loading package ghc-prim … linking … done.
Loading package integer-gmp … linking … done.
Loading package base … linking … done.
Prelude> 66
66
Prelude> 6 * 7
42
Prelude> square 35567
‘square’
Prelude> :load example
[1 of 1] Compiling Main
( example.hs, interpreted )
Ok, modules loaded: Main.
*Main> square 35567
1265011489
*Main> square (smaller (5, 78))
25
*Main> square (smaller (5*10, 5+10))
225
*Main>
(file example.hs)
— a value (of type Integer):
infty :: Integer
infty = infty + 1
— a function
— (from Integer to Integer):
square :: Integer -> Integer
square x = x * x
— another function:
smaller :: (Integer,Integer)->Integer
smaller (x,y) = if x<=y then x else y CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 3 / 51 WHAT’S LEFT? (CONT’D) Functions are first order objects twice :: (Integer -> Integer) -> (Integer -> Integer)
twice f = g
where g x = f (f x)
A program (or script) is a collection of definitions
Predefined data types in a nutshell:
Numerical: Integer , Int , Float , Double
Logical: Bool (values: True, False)
Characters: Char (’a’, ’b’, etc.)
Composite:
Functional: Integer → Integer ;
Tuples: (Int , Int ,Float);
Combinations: (Int ,Float) → (Float ,Bool), Int → (Int → Int)
Sole solution for iterative/repeated computations: recursion
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 4 / 51
SCRIPTS
A script is a collection of definitions of values (including functions)
Syntactical sugar: definitions by guarded equations:
smaller :: (Integer, Integer) -> Integer
smaller (x,y)
| x <= y = x | x > y = y
Recursive definitions:
fact :: Integer -> Integer
fact x = if x==0 then 1 else x * fact (x-1)
Syntactical sugar: definitions by pattern matching (aka by cases):
fact :: Integer -> Integer
fact 0 = 1
fact x = x * fact (x-1)
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 5 / 51
LOCAL DEFINITIONS
Two forms:
let v1 = e1
v2 = e2
.
.
.
vk = ek
in expression
definition
where v1 = e1
v2 = e2
.
.
.
vk = ek
Definitions are qualified by where clauses, while expressions are
qualified by let clauses
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 6 / 51
SCOPING
Haskell uses static scoping.
cylinderArea :: Float -> Float -> Float
cylinderArea h r = h * 2 * pi * r + 2 * pi * r * r
cylinderArea1 :: Float -> Float -> Float
cylinderArea1 h r = x + 2 * y
where x = h * circLength r
y = circArea r
circArea x = pi * x * x
circLength x = 2 * pi * x
cylinderArea2 :: Float -> Float -> Float
cylinderArea2 h r = let x = h * circLength r
y = circArea r
in x + 2 * y
where circArea x = pi * x * x
circLength x = 2 * pi * x
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 7 / 51
TYPES
Each type has associated operations that are not necessarily meaningful
to other types
Arithmetic operations (+, −, ∗, /) can be applied to numerical types, but it
does not make any sense to apply them on, say, values of type Bool
It does, however make sense to compare (using = (==), 6= (/=), ≤ (<=), <,
etc.) both numbers and boolean values
Every well formed expression can be assigned a type (strong typing)
The type of an expression can be inferred from the types of the constituents
of that expression
Those expression whose type cannot be inferred are rejected by the
compiler
badType x
| x == 0 = 0
| x > 0 = ’p’
| x < 0 = ’n’ fact :: Integer -> Integer
fact x
| x < 0 = error "Negative argument." | x == 0 = 1 | x > 0 = x * fact (x-1)
What is the type of error?
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 8 / 51
TWO DATA TYPES
Booleans. Values: True, False
operations on Bool : logic operators: ∨ (||), ∧ (&&), ¬ (not); comparisons: =
(==), 6= (/=); relational <, ≤ (<=), >, ≥ (>=)
Characters. Values: 256 of them, e.g., ’a’, ’b’, ’\n’
Oerations on characters: comparison, relational, plus:
ord :: Char -> Int
chr :: Int -> Char
Prelude> import Data.Char
Prelude Data.Char> ord ’a’
97
Prelude Data.Char> chr 100
’d’
toLower :: Char -> Char
toLower c | isUpper c = chr (ord c – (ord ’A’ – ord ’a’))
| True = c
where isUpper c = ’A’ <= c && c <= ’Z’ CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 9 / 51 LISTS A list is an ordered set of values. [1,2,3] :: [Int ] [[1,2], [3]] :: [[Int ]] [′h′,′ i ′] :: [Char ] [div , rem] :: ?? [1,′ h′] :: ?? [ ] :: ?? Syntactical sugar: Prelude> [’h’,’i’]
“hi”
Prelude> “hi” == [’h’,’i’]
True
Prelude> [[’h’,’i’],”there”]
[“hi”,”there”]
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 10 / 51
CONSTRUCTING LISTS
Constructors: [ ] (the empty list) and : (constructs a longer list)
Prelude> 1:[2,3,4]
[1,2,3,4]
Prelude> ’h’:’i’:[]
“hi”
The operator : (pronounced “cons”) is right associative
The operator : does not concatenate lists together! (++ does this instead)
Prelude> [1,2,3] : [4,5]
No instance for (Num [t0])
arising from the literal ‘4’
Possible fix: add an instance declaration for (Num [t0])
In the expression: 4
In the second argument of ‘(:)’, namely ‘[4, 5]’
In the expression: [1, 2, 3] : [4, 5]
Prelude> [1,2,3] : [[4,5]]
[[1,2,3],[4,5]]
Prelude> [1,2,3] ++ [4,5]
[1,2,3,4,5]
Prelude>
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 11 / 51
OPERATIONS AND PATTERN MATCHING ON LISTS
Comparisons (<, ≥, ==, etc.), if possible, are made in lexicographical order Subscript operator: !! (e.g., [1,2,3] !!1 evaluates to 2) – expensive Arguably the most common list processing: Given a list, do something with each and every element of that list In fact, such a processing is so common that there exists the predefined map that does precisely this: map f [] = [] map f (x:xs) = f x : map f xs This is also an example of pattern matching on lists Variant to pattern matching: head and tail (predefined) head (x:xs) = x tail (x:xs) = xs map f l = if l == [] then [] else f (head l) : map f (tail l) CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 12 / 51 TUPLES While lists are homogenous, tuples group values of (posibly) diferent types divRem :: Integer -> Integer -> (Integer, Integer)
divRem x y = (div x y, rem x y)
divRem1 :: (Integer, Integer) -> (Integer, Integer)
divRem1 (x, 0) = (0, 0)
divRem1 (x, y) = (div x y, rem x y)
The latter variant is also an example of pattern matching on tuples
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 13 / 51
OPERATORS AND FUNCTIONS
An operator contains symbols from the set !#$%&*+./<=>?@\ˆ|: (− and ˜
may also appear, but only as the first character)
Some operators are predefined (+, −, etc.), but you can define your own
as well
An (infix) operator becomes (prefix) function if surrounded by brackets. A
(prefix) function becomes operator if surrounded by backquotes:
divRem :: Integer -> Integer -> (Integer, Integer)
x ‘divRem‘ y = (div x y, rem x y)
— precisely equivalent to
— divRem x y = (div x y, rem x y)
(%%) :: Integer -> Integer -> (Integer, Integer)
(%%) x y = (div x y, rem x y)
— precisely equivalent to
— x %% y = (div x y, rem x y)
Main> 3 %% 2
(1,1)
Main> (%%) 3 2
(1,1)
Main> divRem 3 2
(1,1)
Main> 3 ‘divRem‘ 2
(1,1)
Main>
These are just lexical conventions
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 14 / 51
IDENTIFIERS
Identifiers consist in letters, numbers, simple quotes (’), and underscores
( ), but they must start with a letter
For the time being, they must actually start with a lower case letter
A Haskell idenitifer starting with a capital letter is considered a type (e.g.,
Bool) or a type constructor (e.g., True)—we shall talk at length about those
later
By convention, types (i.e., class names) in Java start with capital letters, and
functions (i.e., method names) start with a lower case letter. What is a
convention in Java is the rule in Haskell!
Some identifiers are language keywords and cannot be redefined (if,
then, else, let, where, etc.).
Some identifiers (e.g., either) are defined in the standard prelude and
possibly cannot be redefined (depending on implementation, messages like
“Definition of variable “either” clashes with import”)
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 15 / 51
INDUCTION AND RECURSIVE FUNCTIONS
An inductive proof for a fact P(n), for all n ≥ α consists in two steps:
Proof of the base case P(α), and
The inductive step: assume that P(n − 1) is true and show that P(n) is also
true
Example
Proof that all the crows have the same colour: For all sets C of crows, |C| ≥ 1,
it holds that all the crows in set C are identical in colour
Base case, |C| = 1: immediate.
For a set of crows C, |C| = n, remove a crow for the set; the remaining (a set of
size n − 1) have the same colour by inductive assumption. Repeat by removing
other crow. The desired property follows
Note: According to the Webster’s Revised Unabridged Dictionary, a crow is “A
bird, usually black, of the genus Corvus [. . . ].”
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 16 / 51
INDUCTION AND RECURSIVE FUNCTIONS (CONT’D)
The same process is used for building recursive functions: One should
provide the base case(s) and the recursive definition(s):
To write a function f :: Integer → Integer , write the base case (definition for
f 0) and the inductive case (use f (n − 1) to write a definition for f n)
Example: computing the factorial
Base case: fact 0 = 1
Induction step: fact n = n * fact (n-1)
To write a function f :: [a]→ β, use induction over the length of the
argument; the base case is f [] and the inductive case is f (x : xs) defined
using f xs
Example: function that concatenates two lists together; we perform induction
on the length of the first argument:
Base case: concat [] ys = ys
Induction step: concat (x:xs) ys = x : concat xs ys
Induction is also an extremely useful tool to prove functions that are
already written
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 17 / 51
EXAMPLE: LISTS AS SETS
Membership (x ∈ A):
member x [] = False
member x (y:ys) | x == y = True
| True = member x ys
Union (A ∪ B), intersection (A ∩ B), difference (A \ B):
union [] t = t
union (x:xs) t | member x t = union xs t
| True = x : union xs t
intersection [] t = []
intersection (x:xs) t | member x t = x : intersection xs t
| True = intersection xs t
difference [] t = []
difference (x:xs) t | member x t = difference xs t
| True = x : difference xs t
Constructor: no recursion. makeSet x = [x]
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 18 / 51
HIGHER ORDER FUNCTIONS
In Haskell, all objects (including functions) are first class citizens. That is,
all objects can be named,
all objects can be members of a list/tuple,
all objects can be passed as arguments to functions,
all objects can be returned from functions,
all objects can be the value of some expression
twice :: (a -> a) -> (a -> a)
twice f = g
where g x = f (f x)
compose f g = h
where h x = f (g x)
twice :: (a -> a) -> a -> a
twice f x = f (f x)
compose f g x = f (g x)
— or —
compose f g = f.g
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 19 / 51
TO CURRY OR NOT TO CURRY
curried form: uncurried form:
compose :: (a->b) -> (c->a) -> c->b
compose f g = f.g
compose :: (a->b, c->a) -> c->b
compose (f,g) = f.g
In Haskell, any function takes one argument and returns one value.
What if we need more than one argument?
Uncurried We either present the arguments packed in a tuple, or
Curried We use partial application: we build a function that takes one
argument and that return a function which in turn takes one
argument and returns another function which in turn. . .
curried: uncurried:
add :: (Num a) => a -> a -> a
add x y = x + y
— equivalent to the explicit version
— add x = g
— where g y = x + y
incr :: (Num a) => a -> a
incr = add 1
add :: (Num a) => (a, a) -> a
add (x,y) = x + y
incr :: (Num a) => a -> a
incr x = add (1,x)
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 20 / 51
TO CURRY OR NOT TO CURRY (CONT’D)
Curying is made possible by lexical closures→all the values existing
when a particular function is defined will exist when the function is run
What if we have a curried function and we want an uncurried one (or the
other way around)?
The following two functions are predefined:
curry f = g
where g a b = f (a,b) — lexical closure:
— f available inside g
uncurry g = f
where f (a,b) = g a b
Alternatively,
curry f a b = f (a,b)
uncurry g (a,b) = g a b
Note that the two functions are curried themselves. . .
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 21 / 51
GLOBAL VARIABLES
Given a nonnegative number x :: Float , write a function mySqrt that
computes an approximation of
√
x with precision � = 0.0001
Newton says that, if yn is an approximation of
√
x , then a better
approximation is yn+1 = (yn + x/yn)/2
So we have:
mySqrt :: Float -> Float
mySqrt x = sqrt’ x
where sqrt’ y = if good y then y else sqrt’ (improve y)
good y = abs (y*y – x) < eps improve y = (y + x/y)/2 eps = 0.0001 x is very similar to a global variable in procedural programming Even closer to procedural programming: mySqrt :: Float -> Float
mySqrt x = until done improve x
where done y = abs (y*y – x)
< eps improve y = (y + x/y)/2 eps = 0.0001 until :: (a -> Bool) ->
(a -> a) -> a -> a
until p f x
| p x = x
| True = until p f (f x)
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 22 / 51
ACCUMULATING RESULTS
1 mystery x = aux x []
where aux [] ret = ret
aux (x:xs) ret = aux xs (x:ret)
2 reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
What is the difference between these two implementations?
An accumulating argument is used for efficiency purposes
It basically transforms a general recursion into a tail recursion
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 23 / 51
MAPS
map applies a function to each element in a list
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
For example:
upto m n = if m > n then [] else m: upto (m+1) n
square x = x * x
Prelude> map ((<) 3) [1,2,3,4] [True,True,False,False] Prelude> sum (map square (upto 1 10))
385
Prelude>
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 24 / 51
MAPS (CONT’D)
Intermission: zip and unzip
Prelude> zip [0,1,2,3,4] “hello”
[(0,’h’),(1,’e’),(2,’l’),(3,’l’),(4,’o’)]
Prelude> zip [0,1,2,3,4,5,6] “hello”
[(0,’h’),(1,’e’),(2,’l’),(3,’l’),(4,’o’)]
Prelude> unzip [(0,’h’),(1,’e’),(2,’l’),(4,’o’)]
([0,1,2,4],”helo”)
Prelude>
A more complex (and useful) example of map:
mystery :: (Ord a) => [a] -> Bool
mystery xs = and (map (uncurry (<=)) (zip xs (tail xs))) This finds whether the argument list is in nondecreasing order CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 25 / 51 FILTERS filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs) = if p x then x : filter p xs else filter p xs
Example:
mystery :: [(String,Int)] -> [String]
mystery xs = map fst (filter ( ((<=) 80) . snd ) xs)
Prelude> mystery [(“a”,70),(“b”,80),(“c”,91),(“d”,79)]
[“b”,”c”]
Suppose that the final grades for some course are kept as a list of pairs
(student name, grade). This then finds all the students that got an A
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 26 / 51
FOLDS
[l1, l2, . . . , ln]
foldr−→ l1 • (l2 • (l3 • (· · · • (ln • id) · · · )))
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr op id [] = id
foldr op id (x:xs) = x ‘op‘ (foldr op id xs)
[l1, l2, . . . , ln]
foldl−→ (· · · (((id • l1) • l2) • l3) • · · · • ln)
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl op id [] = id
foldl op id (x:xs) = foldl op (x ‘op‘ id) xs
Almost all the interesting functions on lists are or can be implemented
using foldr or foldl :
and = foldr (&&) True concat = foldr (++) []
sum = foldr (+) 0 length = foldr oneplus 0
map f = foldr ((:).f) [] where oneplus x n = 1 + n
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 27 / 51
LIST COMPREHENSION
Examples:
triples :: Int -> [(Int,Int,Int)]
triples n = [(x,y,z) | x <- [1..n],y <- [1..n],z <- [1..n]] -- or [(x,y,z) | x <- [1..n],y <- [x..n],z <- [z..n]] pyth :: (Int,Int,Int) -> Bool
pyth (x,y,z) = x*x + y*y == z*z
triads :: Int -> [(Int,Int,Int)]
triads n = [(x,y,z) | (x,y,z) <- triples n, pyth (x,y,z)] General form: [exp|gen1,gen2, . . . ,genn,guard1,guard2, . . .guardp] Quicksort: qsort :: (Ord a) => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y <= x] ++ [x] ++ qsort [y | y <- xs, y > x]
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 28 / 51
POLYMORPHIC TYPES
Some functions have a type definition involving only type names:
and :: [Bool] -> Bool
and = foldr (&&) True
These functions are monomorphic
It is however useful sometimes to write functions that can work on data of
more than one type. These are polymorphic functions
length :: [a] -> Int — For any type a: length :: [a]->Int
map :: (a -> b) -> [a] -> [b]
Restricted polymorphism: What is the most general type of a function
that sorts a list of values, and why?
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y <= x] ++ [x] ++ qsort [y | y <- xs, y > x]
qsort :: (Ord a) => [a] -> [a]
([a]→ [a] for any type a such that an order is defined over a)
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 29 / 51
TYPE SYNONYMS
A function that adds two polynomials with floating point coefficients:
polyAdd :: [Float] -> [Float] -> [Float]
polyAdd :: Poly -> Poly -> Poly would have been nicer though. . .
This can be done by defining “Poly” as a type synonym for [Float]:
type Poly = [Float]
Type synonyms can also be parameterized:
type Stack a = [a]
newstack :: Stack a
newstack = []
push :: a -> Stack a -> Stack a
push x xs = x:xs
aCharStack :: Stack Char
aCharStack = push ’a’ (push ’b’ newstack)
Main> aCharStack
“ab”
Main> push ’x’ aCharStack
“xab”
Main> :t aCharStack
aCharStack :: Stack Char
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 30 / 51
ALGEBRAIC TYPES
Remember when we defined functions using induction (aka recursion)?
Types can be defined in a similar manner (the general form of
mathematical induction is called structural induction): Take for example
natural numbers:
data Nat = Zero | Succ Nat
deriving Show
— Operations:
addNat,mulNat :: Nat -> Nat -> Nat
addNat m Zero = m
addNat m (Succ n) = Succ (addNat m n)
mulNat m Zero = Zero
mulNat m (Succ n) = addnat (mulNat m n) m
Again, type definitions can be parameterized:
data List a = Nil | Cons a (List a)
— data [a] = [] | a : [a]
data BinTree a = Null | Node a (BinTree a) (BinTree a)
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 31 / 51
TYPE CLASSES
Each type may belong to a type class that define general operations. This
also offers a mechanism for overloading
Type classes in Haskell are similar with abstract classes in Java
data Nat = Zero | Succ Nat
deriving (Eq,Show)
instance Ord Nat where
Zero <= x = True x <= Zero = False (Succ x) <= (Succ y) = x <= y one,two,three :: Nat one = Succ Zero two = Succ one three = Succ two Main> one
Succ Zero
Main> two
Succ (Succ Zero)
Main> three
Succ (Succ (Succ Zero))
Main> one > two
False
Main> one > Zero
True
Main> two < three True Main>
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 32 / 51
Ord Nat WORKS BECAUSE. . .
. . . The class Ord is defined in the standard prelude as follows:
class (Eq a) => Ord a where
compare :: a -> a -> Ordering
(<), (<=), (>=), (>) :: a -> a -> Bool
max, min :: a -> a -> a
— Minimal complete definition: (<=) or compare -- using compare can be more efficient for complex types compare x y | x==y = EQ | x<=y = LT | otherwise = GT x <= y = compare x y /= GT x < y = compare x y == LT x >= y = compare x y /= LT
x > y = compare x y == GT
max x y | x >= y = x
| otherwise = y
min x y | x <= y = x | otherwise = y CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 33 / 51 TYPE CLASSES (CONT’D) data Nat = Zero | Succ Nat deriving (Eq,Ord,Show) instance Num Nat where m + Zero = m m + (Succ n) = Succ (m + n) m * Zero = Zero m * (Succ n) = (m * n) + m one,two,three :: Nat one = Succ Zero two = Succ one three = Succ two Main> one + two
Succ (Succ (Succ Zero))
Main> two * three
Succ (Succ (Succ (Succ
(Succ (Succ Zero)))))
Main> one + two == three
True
Main> two * three == one
False
Main> three – two
ERROR – Control stack
overflow
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 34 / 51
DEFINITION OF Num
class (Eq a, Show a) => Num a where
(+), (-), (*) :: a -> a -> a
negate :: a -> a
abs, signum :: a -> a
fromInteger :: Integer -> a
fromInt :: Int -> a
— Minimal complete definition: All, except negate or (-)
x – y = x + negate y
fromInt = fromIntegral
negate x = 0 – x
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 35 / 51
SUBTRACTION
instance Num Nat where
m + Zero = m
m + (Succ n) = Succ (m + n)
m * Zero = Zero
m * (Succ n) = (m * n) + m
m – Zero = m
(Succ m) – (Succ n) = m – n
Nat> one – one
Zero
Nat> two – one
Succ Zero
Nat> two – three
Program error: pattern match failure:
instNum_v1563_v1577 Nat_Zero one
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 36 / 51
OTHER INTERESTING TYPE CLASSES
class Enum a where
succ, pred :: a -> a
toEnum :: Int -> a
fromEnum :: a -> Int
enumFrom :: a -> [a] — [n..]
enumFromThen :: a -> a -> [a] — [n,m..]
enumFromTo :: a -> a -> [a] — [n..m]
enumFromThenTo :: a -> a -> a -> [a] — [n,n’..m]
— Minimal complete definition: toEnum, fromEnum
succ = toEnum . (1+) . fromEnum
pred = toEnum . subtract 1 . fromEnum
enumFrom x = map toEnum [ fromEnum x ..]
enumFromTo x y = map toEnum [ fromEnum x .. fromEnum y ]
enumFromThen x y = map toEnum [ fromEnum x, fromEnum y ..]
enumFromThenTo x y z = map toEnum [ fromEnum x, fromEnum y ..
fromEnum z ]
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 37 / 51
OTHER INTERESTING TYPE CLASSES (CONT’D)
class Show a where
show :: a -> String
showsPrec :: Int -> a -> ShowS
showList :: [a] -> ShowS
— Minimal complete definition: show or showsPrec
show x = showsPrec 0 x “”
showsPrec _ x s = show x ++ s
showList [] = showString “[]”
showList (x:xs) = showChar ’[’ . shows x . showl xs
where showl [] = showChar ’]’
showl (x:xs) = showChar ’,’ .
shows x . showl xs
instance Show Nat where
show Zero = “0”
show (Succ n) = “1 + ” ++ show n
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 38 / 51
EXAMPLE OF TYPE CLASSES
Eq Show Ord Enum
Num
Real
Fractional
Integral
FloatingRealFrac
RealFloat
Bounded
Int Integer Float Double
+ – *
negate
abs
signum
div
mod
even
odd /
recip
pi exp log
sqrt
logBase
sin, cos, etc.
minBound
maxBoun
d
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 39 / 51
TYPE INFERENCE
Different from type checking; in fact precedes type checking
allows the compilers to find the types automatically
Example:
scanl f q [] = q : []
scanl f q (x : xs) = q : scanl f (f q x) xs
First count the arguments: α→ β → γ → δ
Inspect the argument patterns if any: α→ β → [γ]→ δ
parse definitions top to bottom, right to left:
“q : []” =⇒ no extra information
“(f q x)” =⇒ f is a function with 2 arguments: (β → γ → η) → β → [γ] → δ
“scanl f (f q x) xs” =⇒ β = δ i.e. (β → γ → β) → β → [γ] → δ
“q : scanl f (f q x) xs” =⇒ δ = [β] i.e. (β → γ → β) → β → [γ] → [β]
So the overall type is
scanl :: (a -> b -> a) -> a -> [b] -> [a]
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 40 / 51
THE LAMBDA NOTATION
Recall that a Haskell function accepts one argument and returns one
result
peanuts → chocolate-covered peanuts
raisins → chocolate-covered raisins
ants → chocolate-covered ants
Using the lambda calculus, a general “chocolate-covering” function (or
rather λ-expression) is described as follows:
λx .chocolate-covered x
Then we can get chocolate-covered ants by applying this function:
(λx .chocolate-covered x) ants → chocolate-covered ants
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 41 / 51
THE LAMBDA NOTATION (CONT’D)
A general covering function:
λy .λx .y -covered x
The result of the application of such a function is itself a function:
(λy .λx .y -covered x) caramel → λx .caramel-covered x
((λy .λx .y -covered x) caramel) ants → (λx .caramel-covered x) ants
→ caramel-covered ants
Functions can also be parameters to other functions:
λf .(f ) ants
((λf .(f ) ants) λx .chocolate-covered) x
→ (λx .chocolate-covered x) ants
→ chocolate-covered ants
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 42 / 51
LAMBDA CALCULUS
The lambda calculus is a formal system designed to investigate function
definition, function application and recursion
Introduced by Alonzo Church and Stephen Kleene in the 1930s
We start with a countable set of identifiers, e.g.,
{a,b, c, . . . , x , y , z, x1, x2, . . .} and we build expressions using the
following rules:
LEXPRESSION → IDENTIFIER
LEXPRESSION → λIDENTIFIER.LEXPRESSION (abstraction)
LEXPRESSION → (LEXPRESSION)LEXPRESSION (combination)
LEXPRESSION → (LEXPRESSION)
In an expression λx .E , x is called a bound variable; a variable that is not
bound is a free variable
Syntactical sugar: Normally, no literal constants exist in lambda calculus.
We use, however, literals for clarity
Further sugar: HASKELL
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 43 / 51
REDUCTIONS
In lambda calculus, an expression (λx .E)F can be reduced to E [F/x ]
E [F/x ] stands for the expression E , where F is substituted for all the bound
occurrences of x
In fact, there are three reduction rules:
α: λx .E reduces to λy .E [y/x ] if y is not free in E (change of variable)
β: (λx .E)F reduces to E [F/x ] (functional application)
γ: λx .(Fx) reduces to F if x is not free in F (extensionality)
The purpose in life of a Haskell program, given some expression, is to
repeatedly apply these reduction rules in order to bring that expression to
its “irreducible” form or normal form
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 44 / 51
HASKELL AND THE LAMBDA CALCULUS
In a Haskell program, we write functions and then apply them
Haskell programs are nothing more than collections of λ-expressions, with
added sugar for convenience (and diabetes)
We write a Haskell program by writing λ-expressions and giving names to
them:
succ x = x + 1
length = foldr onepl 0
where onepl x n = 1+n
Main> succ 10
11
succ = \ x -> x + 1
length = foldr (\ x -> \ n -> 1+n) 0
— shorthand: (\ x n -> 1+n)
Main> (\ x -> x + 1) 10
11
Another example: map (\ x -> x+1) [1,2,3] maps (i.e., applies) the
λ-expression λx .x + 1 to all the elements of the list, thus producing
[2,3,4]
In general, for some expression E , λx .E (in Haskell-speak: \ x -> E)
denotes the function that maps x to the (value of) E
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 45 / 51
MULTIPLE REDUCTIONS
More than one order of reduction is usually possible in lambda calculus
(and thus in Haskell):
square :: Integer -> Integer
square x = x * x
smaller :: (Integer, Integer) -> Integer
smaller (x,y) = if x<=y then x else y square (smaller (5, 78)) ⇒ (def. smaller) square 5 ⇒ (def. square) 5× 5 ⇒ (def. ×) 25 square (smaller (5, 78)) ⇒ (def. square) (smaller (5, 78))× (smaller (5, 78)) ⇒ (def. smaller) 5× (smaller (5, 78)) ⇒ (def. smaller) 5× 5 ⇒ (def. ×) 25 CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 46 / 51 MULTIPLE REDUCTIONS (CONT’D) Sometimes it even matters: three :: Integer -> Integer
three x = 3
infty :: Integer
infty = infty + 1
three infty
⇒ (def. infty)
three (infty + 1)
⇒ (def. infty)
three ((infty + 1) + 1)
⇒ (def. infty)
three (((infty + 1) + 1) + 1)
…
three infty
⇒ (def. three)
3
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 47 / 51
LAZY HASKELL
Haskell uses the second variant, called lazy evaluation (normal order,
outermost reduction), as opposed to eager evaluation (applicative order,
innermost reduction):
Main> three infty
3
Why is good to be lazy:
Doesn’t hurt: If an irreducible form can be obtained by both kinds of
reduction, then the results are guaranteed to be the same
More robust: If an irreducible form can be obtained, then lazy evaluation is
guaranteed to obtain it
Even useful: It is sometimes useful (and, given the lazy evaluation, possible)
to work with infinite objects
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 48 / 51
INFINITE OBJECTS
[1 .. 100] produces the list of numbers between 1 and 100, but what is
produced by [1 .. ]?
Prelude> [1 ..] !! 10
11
Prelude> [1 .. ] !! 12345
12346
Prelude> zip [’a’ .. ’g’] [1 ..]
[(’a’,1),(’b’,2),(’c’,3),(’d’,4),(’e’,5),(’f’,6),(’g’,7)]
A stream of prime numbers:
primes :: [Integer]
primes = sieve [2 .. ]
where sieve (x:xs) = x : [n | n <- sieve xs, mod n x /= 0] -- alternate: -- sieve (x:xs) = x : sieve (filter (\ n -> mod n x /= 0) xs)
Main> take 20 primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 49 / 51
MEMO FUNCTIONS
Streams can also be used to improve efficiency (dramatically!)
Take the Fibonacci numbers:
fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n – 1) + fib (n – 2)
Complexity? O(2n)
Now take them again, using a memo stream:
fastfib :: Integer -> Integer
fastfib n = fibList %% n
where fibList = 1 : 1 : zipWith (+) fibList (tail fibList)
(x:xs) %% 0 = x
(x:xs) %% n = xs %% (n – 1)
Complexity? O(n)
Typical application: dynamic programming
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 50 / 51
FUNCTIONAL PROGRAMMING
Functional programming Ordinary programming
1. Identify problem Identify problem
2. Assemble information Assemble information
3. Write functions that define the problem Figure out solution
4. Coffee break Program solution
5. Encode problem instance Encode problem instance
as data as data
6. Apply function to data Apply program to data
7. Mathematical analysis Debug procedural errors
CS 403: Introduction to functional programming (S. D. Bruda) Fall 2021 51 / 51