All subjects that are discussed in the Functional Programming course, clearly summarized in a structured way. Based on the lectures and the book Programming in Haskell.
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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Suniht. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.77. You're not tied to anything after your purchase.
