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 functionMonoidArgument m → m
- F-Algebra: for some functor
f
, it's somem
and a functionf 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