[WIP] Foundations of Functional Design, Abstract Algebra, and Category Theory

Work in progress.

Transcript

1. Foundations of Functional Design, Abstract Algebra, & Category Theory Michael Ficarra
2. Part I: Functional Principles • First-Class and Higher-Order Functions • Referential Transparency and Equational Reasoning • Immutability • Lazy Evaluation • Totality: Guaranteed Termination Through Substructural Recursion Part II: Abstract Algebra • Magma (Integral Sum) • Semigroup (Integral Sum, Integral Product, All, Any, Min, Max) • Monoid (Integral Sum, Integral Product, All, Any, List Concatenation, Set Union) • Group (Integral Sum, Rational Product, Modular Arithmetic, Square Symmetry) • Abelian Group (Integral Sum) Part III: Category Theory • Category • Arrow • Homomorphism • Functor • Applicative • Monad
3. In abstract algebra, an algebraic structure is a set of values, one or more finitary operations, and a set of laws the operations must obey Algebraic Structure
4. a means of expressing a recurring construct in one or more programming languages Idiom a technique used for solving a common problem within the confines of a particular paradigm or environment Design Pattern Algebraic Structure a formalisation of a universal mathematical construct, applicable in all languages, paradigms, and environments
5. class Magma a where (<>) :: a -> a -> a Magma
6. class Magma a where (<>) :: a -> a -> a class Magma a => Semigroup a Semigroup
7. (x <> y) <> z = x <> (y <> z) (associativity) Semigroup Laws
8. newtype Sum a = Sum { getSum :: a } instance Integral a => Magma (Sum a) where Sum x <> Sum y = Sum (x + y) instance Integral a => Semigroup (Sum a) function Sum(x) { this.valueOf = function() { return x; }; } Sum.prototype.concat = function(y) { return new Sum(this + y); }; Semigroup Instance - (Integers, +)
9. newtype Product a = Product { getProduct :: a } instance Integral a => Magma (Product a) where Product x <> Product y = Product (x * y) instance Integral a => Semigroup (Product a) function Product(x) { this.valueOf = function() { return x; }; } Product.prototype.concat = function(y) { return new Product(this * y); }; Semigroup Instance - (Integers, *)
10. newtype All { getAll :: Bool } instance Magma All where All x <> All y = All (x && y) instance Semigroup All function All(x) { this.valueOf = function() { return x; }; } All.prototype.concat = function(y) { return this.valueOf() ? y : this; }; Semigroup Instance - (Booleans, AND)
11. newtype Any { getAny :: Bool } instance Magma Any where Any x <> Any y = Any (x || y) instance Semigroup Any function Any(x) { this.valueOf = function() { return x; }; } Any.prototype.concat = function(y) { return this.valueOf() ? this : y; }; Semigroup Instance - (Booleans, OR)
12. newtype Min a = Min { getMin :: a } instance Ord a => Magma (Min a) where Min x <> Min y = Min (min x y) instance Ord a => Semigroup (Min a) function Min(x) { this.valueOf = function() { return x; }; } Min.prototype.concat = function(y) { return this < y ? this : y; }; Semigroup Instance - (Ordered Sets, Min)
13. newtype Max a = Max { getMax :: a } instance Ord a => Magma (Max a) where Max x <> Max y = Max (max x y) instance Ord a => Semigroup (Max a) function Max(x) { this.valueOf = function() { return x; }; } Max.prototype.concat = function(y) { return this > y ? this : y; }; Semigroup Instance - (Ordered Sets, Max)
14. function sconcat(xs) { xs.reduceRight(function(a, b) { return a.concat(b); }); } Semigroup - Derived Functions -- Fold a non-empty list using the semigroup. sconcat :: [a] -> a sconcat = foldr1 (<>)
15. class Magma a where (<>) :: a -> a -> a class Magma a => Semigroup a class Semigroup a => Monoid a where identity :: a Monoid
16. (x <> y) <> z = x <> (y <> z) (associativity) identity <> x = x x <> identity = x (identity) Monoid Laws
17. newtype Sum a = Sum { getSum :: a } instance Integral a => Magma (Sum a) where Sum x <> Sum y = Sum (x + y) instance Integral a => Semigroup (Sum a) instance Integral a => Monoid (Sum a) where identity = Sum 0 function Sum(x) { this.valueOf = function() { return x; }; } Sum.empty = function() { return new Sum(0); }; Sum.prototype.concat = function(y) { return new Sum(this + y); }; Monoid Instance - (Integers, +)
18. newtype Product a = Product { getProduct :: a } instance Integral a => Magma (Product a) where Product x <> Product y = Product (x * y) instance Integral a => Semigroup (Product a) instance Integral a => Monoid (Product a) where identity = Product 1 function Product(x) { this.valueOf = function() { return x; }; } Product.empty = function() { return new Product(1); }; Product.prototype.concat = function(y) { return new Product(this * y); }; Monoid Instance - (Integers, *)
19. newtype All = All { getAll :: Bool } instance Magma All where All x <> All y = All (x && y) instance Semigroup All instance Monoid All where identity = All True function All(x) { this.valueOf = function() { return x; }; } All.empty = function() { return new All(true); }; All.prototype.concat = function(y) { return this.valueOf() ? y : this; }; Monoid Instance - (Booleans, All)
20. newtype Any = Any { getAny :: Bool } instance Magma Any where Any x <> Any y = Any (x || y) instance Semigroup Any instance Monoid Any where identity = Any False function Any(x) { this.valueOf = function() { return x; }; } Any.empty = function() { return new Any(false); }; Any.prototype.concat = function(y) { return this.valueOf() ? this : y; }; Monoid Instance - (Booleans, Any)
21. instance Magma [a] where (<>) = (++) instance Semigroup [a] where instance Monoid [a] where identity = [] Array.empty = function() { return []; }; // Array.prototype.concat is already Fantasy Land compatible Monoid Instance - (lists, concatenation)
22. import qualified Data.Set as Set import Data.Set (Set) instance Ord a => Magma (Set a) where (<>) = Set.union instance Ord a => Semigroup (Set a) instance Ord a => Monoid (Set a) where identity = Set.empty function uniq(xs) { return xs.sort().filter(function(x, i) { return i === 0 || xs[i - 1] !== x; }); } function Set(xs) { this.valueOf = function() { return uniq(xs); }; } Set.prototype.empty = function() { return new Set([]); }; Set.prototype.concat = function(y) { return new Set(this.valueOf().concat(y.valueOf())); }; Monoid Instance - (finite sets, union)
23. -- Fold a list using the monoid. mconcat :: [a] -> a mconcat = foldr (<>) identity function mconcat(xs) { xs.reduceRight( function(a, b) { return a.concat(b); }, // Empty lists in JS are untyped, so we cannot // derive the appropriate identity to use here. ); } Monoid - Derived Functions
24. class Magma a where (<>) :: a -> a -> a class Magma a => Semigroup a class Semigroup a => Monoid a where identity :: a class Monoid a => Group a where inverse :: a -> a Group
25. (x <> y) <> z = x <> (y <> z) (associativity) identity <> x = x x <> identity = x (identity) x <> inverse x = identity inverse x <> x = identity (invertibility) Group Laws
26. newtype Sum a = Sum { getSum :: a } -- Magma, Semigroup, Monoid ... instance Integral a => Group (Sum a) where inverse (Sum x) = Sum (-x) function Sum(x) { this.valueOf = function() { return x; }; } Sum.empty = function() { return new Sum(0); }; Sum.prototype.inverse = function() { return new Sum(-this); }; Sum.prototype.concat = function(y) { return new Sum(this + y); }; Group Instance - (Integers, +)
27. import Data.Ratio instance Integral a => Magma (Ratio a) where (<>) = (*) instance Integral a => Semigroup (Ratio a) instance Integral a => Monoid (Ratio a) where identity = 1 instance Integral a => Group (Ratio a) where inverse a = denominator a % numerator a Group Instance - (Nonzero Rationals, *)
28. function Ratio(num, den) { if(den === 0) throw new Error("division by zero"); var d = gcd(num, den); this.num = Math.floor((den > 0 ? num : -num) / d); this.den = Math.floor(Math.abs(den) / d); } Ratio.empty = function() { return new Ratio(1, 1); }; Ratio.prototype.concat = function(y) { return new Ratio(this.num * y.num, this.den * y.den); }; Ratio.prototype.inverse = function() { return new Ratio(this.den, this.num); }; Ratio.prototype.valueOf = function() { return this.num / this.den; }; function gcd(a, b) { return b ? gcd(b, a % b) : Math.abs(a); } Group Instance - (Nonzero Rationals, *)
29. newtype Mod12 = Mod12 { getMod12 :: Int } instance Magma Mod12 where (Mod12 a) <> (Mod12 b) = Mod12 (mod (a + b) 12) instance Semigroup Mod12 instance Monoid Mod12 where identity = Mod12 0 instance Group Mod12 where inverse (Mod12 a) = Mod12 (mod (12 - a) 12) function Mod12(x) { this.valueOf = function() { return x; }; } Mod12.empty = function() { return new Mod12(0); }; Mod12.prototype.inverse = function() { return new Mod12((12 - this) % 12); }; Mod12.prototype.concat = function(y) { return new Mod12((this + y) % 12); }; Group Instance - (Integers mod 12, +)
30. Group Instance - Square Symmetry Rotate 90° Rotate 180° Rotate 270° Identity Vertical Flip Horizontal Flip Diag. Flip #1 Diag. Flip #2
31. Group - Derived Functions -- find the unique x ∈ G that solves `x <> a = b` gdivl :: a -> a -> a gdivl a b = b <> inverse a -- find the unique x ∈ G that solves `a <> x = b` gdivr :: a -> a -> a gdivr a b = inverse a <> b function gdivl(a, b) { return b.append(a.inverse()); } function gdivr(a, b) { return a.inverse().append(b); }
32. class Magma a where (<>) :: a -> a -> a class Magma a => Semigroup a class Semigroup a => Monoid a where identity :: a class Monoid a => Group a where inverse :: a -> a class Group a => AbelianGroup a Abelian Group
33. (x <> y) <> z = x <> (y <> z) (associativity) identity <> x = x x <> identity = x (identity) x <> inverse x = identity inverse x <> x = identity (invertibility) x <> y = y <> x (commutativity) Abelian Group Laws
34. Abelian Group - Instances Boring.
35. Abelian Group - Derived Functions -- find the unique x ∈ G that solves `x <> a = b` gdivl :: a -> a -> a gdivl a b = b <> inverse a -- find the unique x ∈ G that solves `a <> x = b` gdivr :: a -> a -> a gdivr = gdivl function gdivl(a, b) { return b.append(a.inverse()); } var gdivr = gdivl;
36. Group-likes Summary class Magma a where (<>) :: a -> a -> a class Magma a => Semigroup a where sconcat :: [a] -> a sconcat = foldr1 (<>) class Semigroup a => Monoid a where identity :: a mconcat :: [a] -> a mconcat = foldr (<>) identity class Monoid a => Group a where inverse :: a -> a gdivl :: a -> a -> a gdivl a b = b <> inverse a gdivr :: a -> a -> a gdivr a b = inverse a <> b class Group a => AbelianGroup a
37. Group-likes Summary* (closure) Magma (+ associativity) Semigroup (+ identity) Monoid (+ invertibility) Group (+ commutativity) Abelian Group * This is just a subset of all Group-likes.
39. Other Algebraic Structures • Simple structures: No binary operation • Group-like structures: One binary operation • Ring-like structures: Two binary operations, often called addition and multiplication, with multiplication distributing over addition • Lattice structures: Two or more binary operations, including operations called meet and join, connected by the absorption law • Arithmetics: Two binary operations, addition and multiplication. S is an infinite set. Arithmetics are pointed unary systems, whose unary operation is injective successor, and with distinguished element 0 And these are just the kinds of algebraic structures involving one set!
40. Part I: Functional Principles • First-Class and Higher-Order Functions • Referential Transparency and Equational Reasoning • Immutability • Lazy Evaluation • Totality: Guaranteed Termination Through Substructural Recursion Part II: Abstract Algebra • Magma (Integral Sum) • Semigroup (Integral Sum, Integral Product, All, Any, Min, Max) • Monoid (Integral Sum, Integral Product, All, Any, List Concatenation, Set Union) • Group (Integral Sum, Rational Product, Modular Arithmetic, Square Symmetry) • Abelian Group (Integral Sum) Part III: Category Theory • Category • Arrow • Homomorphism • Functor • Applicative • Monad