Functional Programming
# Terminology
# Category Theory
In essence, a simple collection which can be thought of as a graph. Three components
 A collection of objects (nodes)
 A collection of morphisms (edges).
 If $f$ is a morphism with source C and target B, we write $f: C \rightarrow B$
 A notion of composition of morphisms.
 If we have $g: A \rightarrow B$ and $f: B \rightarrow C$, they can be composed resulting in a morphism $f \circ g: A \rightarrow C$
 Composition of morphisms needs to be associative. Typically applied right to left
Category theory to Haskell
 Objects are types
 Morphisms are functions
 Things that take a type and return another type are type constructors
 Things that take a function and return another function are higherorder functions
 Typeclasses capture the fact that things are often defined for a ‘set’ of objects at once
# Functor
A ‘container’ of some sort, along with the ability to apply a function uniformly to every element in it
Essentially a transformation between categories. Given categories $C$ and $D$ and a functor $F: C \rightarrow D$
 $F$ maps any object $A \in C$ to $F(A) \in D$ (the type constructor)
 $F$ maps morphisms $f: A \rightarrow B \in C$ to $F(f): F(A) \rightarrow F(B) \in D$ (
fmap
). Importantly, this means that all functors must be generic over at least one parameter (e.g.Maybe
and notInteger
) applying
fmap
is sometimes called ’lifting’ as it lifts a function from the normal context into the ‘f’ world
 applying


fmap
takes a function which maps a value from a
to b
and applies it to a Functor f
. Think of f
as the container, (a > b)
as the function that operates on the ‘inner’ values.
# Monad
Monads are functors from a category $A$ to that same category. A container for values that can be mapped over.
Think of it like a contextspecific environment. You need a function to transform things outside of it to things in it. You also need a function to manipulate stuff inside of that environment.
A monad is a functor $M: C \rightarrow C$ along with two morphisms $\forall X \in C$
 $\textrm{unit}_X : X \rightarrow M(X)$ (
return
)  $\textrm{join}_X: M(M(X)) \rightarrow M(X)$ (can be recovered from
bind
)


Monad laws


# Left and Right Associativity
Associativity of an operator determines how operators are grouped in the absence of parentheses.
For the following examples, we consider a fictional operator ~
 Associative: operations can be grouped arbitrarily (e.g. addition, order doesn’t matter)
 Leftassociative: operations are grouped left to right
a ~ b ~ c
is interpreted as(a ~ b) ~ c
 Examples include
 Function application operator
 Rightassociative: operations are grouped right to left
a ~ b ~ c
is interpreted asa ~ (b ~ c)
 Examples include
 Variable assignment (
=
)  Exponentiation (
^
)
 Variable assignment (
 Nonassociative: operations cannot be chained
# Parser Combinators
Parser combinators are a technique for implementing parsers by defining them in terms of other parsers
Notes on Chumsky
Where a
and b
are both parsers.
Parser Methods
just(a)
accepts a single stringa
a.or(b)
parsea
, ifa
fails, try parsingb
a.choice(b,c,d...)
try parsingb
,c
,d
, return first one that succeedsa.or_not()
optionally parsea
a.ignore_then(b)
ignore patterna
then parseb
a.then_ignore(b)
parsea
then ignoreb
a.then(b)
parse botha
andb
and return a tuple of(a,b)
a.padded()
ignore whitespace arounda
a.repeated().at_least(n)
parsea
at leastn
timesa.filter(fn)
only accepta
iffn(a)
evaluates to true
Result Methods
a.collect()
turn results ofa
into an iteratora.map(b)
map results ofa
into typeb
a.chain(b)
concatenate results of parsersa
andb
into collectiona.copy(b)
duplicate parser definitiona.flatten()
flatten nested collectiona.to(b)
marks result ofa
as typeb
a.labelled(b)
label result of a withb
a.end()
indicate end of parser
# Haskell Syntax Quirks
$ :: (a > b) > a > b
is function application (adds implicit parentheses and makes it right associative instead of left associative) Normally,
sort "abc" ++ "def"
would be interpreted as(sort "abc") ++ "def"
 If we use the
$
operator, we can dosort $ "abc" ++ "def"
which is interpreted assort ("abc" ++ "def")
as intended.
 Normally,
.
is function composition. Read the dot as the little dot in $f \circ g$<>
is a synonym formappend :: Monoid m => m > m > m
or the monoidal append<$>
is a synonym forfmap :: (a > b) > f a > f b
 Intuitively like applying a function to a container
<*>
is like<$>
but for wrapped functions(<*>) :: Applicative f => f (a > b) > f a > f b
 Intuitively like applying a function in a container to another container
 Remember that
(<$)
and($>)
point towards the value that will be kept void :: Functor f => f a > f ()
is implemented asvoid x = () <$ x
. Read as: whatever you give me, I will return the unit value