## Algebras and Coalgebras

Tikhon Jelvis (tikhon@jelv.is)

Press key to advance.
Zoom in/out: Ctrl or Command + +/-

# 1 Abstract Algebra

• Algebraic structure:
• some set $$S$$
• some functions closed over $$S$$
• some "identity" elements

# 2 Example Structures

• Monoid
• $$S \times S \to S$$
• $$S$$
• Group
• $$S \times S \to S$$
• $$S$$
• $$S \to S$$
• More: ring, field, lattice, Boolean algebra…

# 3 Algebra

• Different arities: $$S^n \to S$$
• where $$S^n = S \times S \times \ldots \times S$$, $$n$$ times.
• $$(S,S,\ldots,S)$$
• $$S^0 = ?$$
• $$()$$
• Identity: $$S^0 \to S = () \to S$$
• mempty ∷ () → m

# 4 Either

• A bunch of functions: $$a \to S$$, $$b \to S$$, $$c \to S$$…
• Combine with Either!
mempty  ∷ m         -- () → m
mappend ∷ m → m → m -- (m, m) → m

op ∷ Either () (m, m) → m
op (Left ()) = mempty
op (Right (l, r)) = mappend l r


# 5 ADTs

• A bunch of sum and product types!
• Turn it into a normal data type:
data MonoidArgument m = Mempty
| Mappend m m

op (Mempty)          = mempty
op (Mappend m_1 m_2) = mappend m_1 m_2

• Hey, this is a Functor!

# 6 F-Algebra

• So, a monoid is just m with a function MonoidArgument m → m
• F-Algebra: for some functor f, it's some m and a function f m → m.

# 7 Coalgebra

• Algebra: (m, f m → m)
• Flip
• Coalgebra: (m, m → f m)

# 8 Uses:

• algebra : fold
• coalgebra : unfold
• coalgebras can represent:
• infinite streams
• automata
• reactive systems
• object-oriented classes