Functional Programming
General 2
Basics 3
Types 6
Recursion 7
Higher-order functions 9
Folds 10
Data types 12
Type classes 13
Data structures in memory 15
Modules 16
Input/Output 17
Functors and Monads 21
Laws and induction 24
Testing 28
Lazy evaluation 31
Notes 34
1
,General
FP is a way of thinking about problems (some even dare say that it is a way of life). Instead of
writing an algorithm to solve something you give a definition of what it is.
- Fewer bugs in the short term, due to purity, which makes for fewer surprises when
programming and it makes it easier to reason about programs
- More maintainable code in the long term, due to types
Function Mapping of arguments to a result
Functional Programming features
1. Recursion instead of iteration
- Recursive function instead of a for loop
2. Pattern matching on values
- Functions are defined by series of equations
- Input value is compared with each left side until one fits (more below)
3. Expressions instead of statements
- Statements manipulate the state of the program (variables)
- Values of an expression depends only on its subexpressions
- Easier to compose and reason about
4. Functions as first-class citizens
- Functions can be parameters of another function (the map function, for example)
- Functions can be returned from other functions
Haskell defined by four adjectives
- Functional
- Statically typed
- Every expression and function has a type
- Compiler prevents wrong combinations
- Pure
- Cannot use statement based programming (variables don’t change, just names)
- Functions which interact with the outer world are marked in their type with IO
- Lazy
- “Progress isn't made by early risers. It's made by lazy men trying to find
easier ways to do something.”
- Lazy evaluated, things only get calculated if they get used
When writing Haskell, it’s good practice to separate pure and impure parts
- Pure functions deal with values only
- Impure functions communicate with the outside world (I/O, networking, interaction)
- Most common pattern:
1. Impure part obtains input
2. Pure part manipulates input data
3. Impure part outputs the result
2
,Basics
Lists Sequences of elements of the same type
- A list is well-typed if all elements of the list are of the same type. For example, the list
[id,length] is not well-typed as the types of the two functions differ, but the list
[sum,length] is well-typed since sum will adjust to the more specific type signature of
length with Int
- [] :: [a] is the empty list
- [1 .. 5] creates a list [1,2,3,4,5]
- (:) :: a -> [a] -> [a] adds an item to (the beginning of) a given list
- null :: [a] -> Bool tells you whether a list is empty or not
- length :: [a] -> Int computes the length of the list (the number of elements)
- head :: [a] -> a returns the first element in a list
- tail :: [a] -> [a] returns a new list with the first element removed
- Returns a new list, because every data type in Haskell is immutable
- init :: [a] -> [a] returns a new list with the last element removed
- sum :: [a] -> a computes the sum of all elements in a list
- and :: [Bool] -> Bool Boolean AND operation on all the elements of the list
- or :: [Bool] -> Bool Boolean OR operation on all the elements of the list
- replicate :: Int -> a -> [a] creates a list of a length given by the first argument
with items with the value that is given as the second argument
- reverse :: [a] -> [a] returns a list with the elements reversed
- map :: (a -> b) -> [a] -> [b] returns a list constructed by applying the given
function to the elements of the given list
- filter :: (a -> Bool) -> [a] -> [a] goes through the elements of the given list
and applies the given function to it, if it returns false, the element is removed from the
resulting list
Tuples Combination of a number of components, possibly of different types
- fst :: (a, b) -> a takes a tuple and returns the first element of it
- snd :: (a, b) -> b takes a tuple and returns the second element of it
Conditionals vs Guards
- If then else
abs n = if (n < 0) then -n else n
- Guards
abs n | n < 0 = -n
| otherwise = n
Layout rule Related elements must start on the same column
Local definitions
- Assign a name to an expression, which has multiple benefits:
- Maintainability: reduce code repetition
- Performance: the expression is only computed once
3
, - Documentation: assign names to concepts
- For example, instead of distance px py qx qy = sqrt ((px - qx)*(px - qx) +
(py - qy)*(py - qy)), it’s better to use where or let
- Where (top-down, not an expression in and of itself)
distance px py qx qy = sqrt (xDiff + yDiff)
where
xDiff = square (px - qx)
yDiff = square (py - qy)
square z = z * z
- Use this when you need a variable across several guards
- Let (bottom up, is an expression itself, so can be used mid-code)
distance px py qx qy =
let xDiff = square (px - qx)
yDiff = square (py - qy)
square z = z * z
in sqrt (xDiff + yDiff)
- In accordance to the layout rule, alle definitions must start in the same column and it’s
good style (but not mandatory) to align the = symbols
Comments
funcion = undefined --this is a one line comment
function = undefined {- this is a multi-
line comment -}
Pattern matching
- Define a function by providing different patterns that the input might have and
expressions to execute if the input is matched to one of these patterns
- For example, given the function fac below, the first argument is first compared to 0, and
if it doesn’t match, the second branch is executed (because the type variable n will
match any type that the given argument might have)
fac :: Int -> Int null [] = True length [] = 0
fac 0 = 1 null _ = False length (_ : xs) = 1 + length xs
fac n = n * fac (n-1)
- If you do not care about nor use a value, you can use _ instead of type variables (more
on them below), as seen above; The length function there uses _ : xs to make xs the
given list with the first element removed
- This can also be used to avoid repetitiveness, as seen below
conj True True = True conj True True = True
conj True False = False conj _ _ = False
conj False True = False
conj False False = False
- When you have a function defined with guards and one of the condition uses a ==
comparison, it’s better to use pattern matching instead, because == is more expensive
4
