Summary

Summary Functional Programming (INFOFP)

2 purchases

Course
Functioneel Programmeren (INFOFP)

Institution
Universiteit Utrecht (UU)

Book
Programming in Haskell

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.

[Show more]

Last document update: 3 year ago

Preview 4 out of 35 pages

View example

Summarized whole book? Yes
Uploaded on November 2, 2021
File latest updated on November 12, 2021
Number of pages 35
Written in 2021/2022
Type Summary

types
lists
tuples
conditionals
guards
pattern matching
list comprehension
type classes
recursion
higher order functions
anonymous functions
folds
monoids
monads
functors
partial function application

Book Title:Programming in Haskell

Author(s):Graham Hutton

Edition:Unknown
ISBN:9781316626221
Edition:2

Institution
Universiteit Utrecht (UU)
Education
Informatica
Course
Functioneel Programmeren (INFOFP)

Suniht

Member since 3 year 89 documents sold

$9.68

Add to cart

Add to wishlist

100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached

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

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.68. You're not tied to anything after your purchase.

Can Stuvia be trusted?

4.6 stars on Google & Trustpilot (+1000 reviews)

69411 documents were sold in the last 30 days

Founded in 2010, the go-to place to buy study notes for 15 years now

Start selling

Summary

Summary Functional Programming (INFOFP)

Document information

Subjects

Connected book

Written for

Seller

Reviews received

Content preview