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