Functional Programming

Terminology

Category Theory

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 higher-order 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 \to D$

$F$ maps any object $A \in C$ to $F (A) \in D$ (the type constructor)
$F$ maps morphisms $f : A \to B \in C$ to $F (f) : F (A) \to F (B) \in D$ (fmap). Importantly, this means that all functors must be generic over at least one parameter (e.g. Maybe and not Integer)
- applying fmap is sometimes called ‘lifting’ as it lifts a function from the normal context into the ‘f’ world

class Functor f where
	-- fmap maps morphisms
	fmap :: (a -> b) -> f a -> f b
 
	-- applies a 'constant' function to replace the values in a container
	(<$) :: a -> f b -> f a
	-- default implementation
	(<$) = fmap . const

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 context-specific 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 \to C$ along with two morphisms $\forall X \in C$

$unit_{X} : X \to M (X)$ (return)
$join_{X} : M (M (X)) \to M (X)$ (can be recovered from bind)

class Monad m where
  -- join operation (optional, only one of bind or join need to be defined)
  join :: m (m a) -> m a
 
  -- bind operation
  -- takes an f :: (a -> m b) and applies it to
  -- the inner value a of m
  (>>=)  :: m a -> (a -> m b) -> m b
 
  -- replaces m a with m b
  (>>)   :: m a ->  m b       -> m b
 
  -- constructs the simplest monad m using a
  return ::   a               -> m a

Monad laws

return a >>= k                  =  k a
m        >>= return             =  m
m        >>= (\x -> k x >>= h)  =  (m >>= k) >>= h

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)
Left-associative: operations are grouped left to right
1. a ~ b ~ c is interpreted as (a ~ b) ~ c
2. Examples include
  1. Function application operator
Right-associative: operations are grouped right to left
1. a ~ b ~ c is interpreted as a ~ (b ~ c)
2. Examples include
  1. Variable assignment (=)
  2. Exponentiation (^)
Non-associative: 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 string a
a.or(b) parse a, if a fails, try parsing b
a.choice(b,c,d...) try parsing b, c, d, return first one that succeeds
a.or_not() optionally parse a
a.ignore_then(b) ignore pattern a then parse b
a.then_ignore(b) parse a then ignore b
a.then(b) parse both a and b and return a tuple of (a,b)
a.padded() ignore whitespace around a
a.repeated().at_least(n) parse a at least n times
a.filter(fn) only accept a if fn(a) evaluates to true

Result Methods

a.collect() turn results of a into an iterator
a.map(b) map results of a into type b
a.chain(b) concatenate results of parsers a and b into collection
a.copy(b) duplicate parser definition
a.flatten() flatten nested collection
a.to(b) marks result of a as type b
a.labelled(b) label result of a with b
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)
1. Normally, sort "abc" ++ "def" would be interpreted as (sort "abc") ++ "def"
2. If we use the $ operator, we can do sort $ "abc" ++ "def" which is interpreted as sort ("abc" ++ "def") as intended.
. is function composition. Read the dot as the little dot in $f \circ g$
<> is a synonym for mappend :: Monoid m => m -> m -> m or the monoidal append
<$> is a synonym for fmap :: (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 as void x = () <$ x. Read as: whatever you give me, I will return the unit value

jzhao.xyz

Table of Contents