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


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 and and a functor

  1. maps any object to (the type constructor)
  2. maps morphisms to (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.


Monads are functors from a category 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 along with two morphisms

  1. (return)
  2. (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 ~

  1. Associative: operations can be grouped arbitrarily (e.g. addition, order doesn’t matter)
  2. 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
  3. 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 (^)
  4. 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

  1. just(a) accepts a single string a
  2. a.or(b) parse a, if a fails, try parsing b
  3. a.choice(b,c,d...) try parsing b, c, d, return first one that succeeds
  4. a.or_not() optionally parse a
  5. a.ignore_then(b) ignore pattern a then parse b
  6. a.then_ignore(b) parse a then ignore b
  7. a.then(b) parse both a and b and return a tuple of (a,b)
  8. a.padded() ignore whitespace around a
  9. a.repeated().at_least(n) parse a at least n times
  10. a.filter(fn) only accept a if fn(a) evaluates to true

Result Methods

  1. a.collect() turn results of a into an iterator
  2. a.map(b) map results of a into type b
  3. a.chain(b) concatenate results of parsers a and b into collection
  4. a.copy(b) duplicate parser definition
  5. a.flatten() flatten nested collection
  6. a.to(b) marks result of a as type b
  7. a.labelled(b) label result of a with b
  8. 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
  • <> 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