## Terminology

### Category Theory

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
*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→D$

- $F$ maps any object $A∈C$ to $F(A)∈D$ (the type constructor)
- $F$ maps morphisms $f:A→B∈C$ to $F(f):F(A)→F(B)∈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

- applying

```
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→C$ along with two morphisms $∀X∈C$

- $unit_{X}:X→M(X)$ (
`return`

) - $join_{X}:M(M(X))→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
`a ~ b ~ c`

is interpreted as`(a ~ b) ~ c`

- Examples include
- Function application operator

- Right-associative: operations are grouped right to left
`a ~ b ~ c`

is interpreted as`a ~ (b ~ c)`

- Examples include
- Variable assignment (
`=`

) - Exponentiation (
`^`

)

- Variable assignment (

- 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)- Normally,
`sort "abc" ++ "def"`

would be interpreted as`(sort "abc") ++ "def"`

- If we use the
`$`

operator, we can do`sort $ "abc" ++ "def"`

which is interpreted as`sort ("abc" ++ "def")`

as intended.

- Normally,
`.`

is function composition. Read the dot as the little dot in $f∘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