Category Theory for Haskellers

Types as objects, functions as morphisms, id and (.) (identity and associative composition)

fmap preserving identity and composition (endofunctors on Hask) Natural transformation

forall a. f a -> g a (e.g., maybeToList, listToMaybe) (<>) + mempty with associativity and identity

A monoid in the category of endofunctors: join :: m (m a) -> m a and return

Lax monoidal functor: liftA2 (,):: f a -> f b -> f (a, b) Products and coproducts (a, b) and Either a b Initial/terminal objects Void and ()

Function types a -> b; currying is the adjunction (a, b) -> c ≅ a -> b -> c

Curry/uncurry; State arises from the product–exponential adjunction

f a -> a; folds are catamorphisms (recursion-schemes: cata, ana, para)

extract :: w a -> a, extend (e.g., zippers, Store, cellular automata)

Profunctor, Arrow, Category class Generalized function-like abstractions (used by optics) Kleisli category a -> m b with >=> composition

Recommended reading: Bartosz Milewski's *Category Theory for Programmers*; *Haskell Programming from First Principles* (for the typeclass laws).

import Control.Comonad   -- comonad package
-- Recursion schemes
{-# LANGUAGE DeriveFunctor #-}
newtype Fix f = Fix (f (Fix f))
data ExprF r = Const Int | AddF r r | MulF r r deriving Functor
cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg (Fix x) = alg (fmap (cata alg) x)
evalAlg :: ExprF Int -> Int
evalAlg (Const n) = n
evalAlg (AddF a b) = a + b
evalAlg (MulF a b) = a * b
-- cata evalAlg (Fix (AddF (Fix (Const 2)) (Fix (MulF (Fix (Const 3)) (Fix (Const 4)))))) == 14