WIXLIB

Algebras inProgrammingWhat do we mean by algerbra

Harry Laoulakos@harrylaou Senior Scala Consultant Functional Programming Check Cost vs BenefitAlgebras in Programming2

For absolute beginners not necessary to know scala stay focussed on semantics build a vocabulary to communicate with fellowprogrammers "touches" mathematical concepts, but doesn't godeepAlgebras in Programming3

rogramming.pdfAlgebras in Programming4

Areas of Mathematics Elementary algebra Abstract algebra Linear algebra Boolean algebra Commutative algebra Homological algebraAlgebras in Programming5

more areas Universal algebra Algebraic number theory Algebraic geometry Algebraic combinatorics Relational algebraAlgebras in Programming6

Algebras can also be mathematical structuresFor example in category theory F-algebra F-coalgebra T-algebraAlgebras in Programming7

When we are talking about algebra, it is notnecessarily one or even similar things.Algebras in Programming8

In Programming ADTs: algebraic data types GADTs: Generalized algebraic data types Tagless Final Algebra Free Μonads Algebra Recursion Schemes AlgebraAlgebras in Programming9

ADTAlgebraic data typeAlgebras in Programming10

ADTis a composite type of- Product Types (or Tagged Unions)- Sum Types (or Co-Product or Unions)Algebras in Programming11

Product Type case class tuple HListAlgebras in Programming12

Product Typecase class User(id:Long, username:String, .)Algebras in Programming13

Product Typecase class User(id:Long, username:String, .)Think ANDAlgebras in Programming14

Sum Type Either sealed trait CoproductAlgebras in Programming15

Sum Typesealed trait Animalcase class Cat(name:String) extends Animalcase class Dog(name: String) extends AnimalAlgebras in Programming16

Sum Typesealed trait Animalcase class Cat(name:String) extends Animalcase class Dog(name: String) extends AnimalThink ORAlgebras in Programming17

NoteIt is a different than inheritance.There are GADTs in Rust, which doesn't supportinheritance.Algebras in Programming18

Product TypeRuststruct User {id: u64,name: String}Algebras in Programming19

Sum TypeRustenum Animal {Cat(String),Dog(String)}Algebras in Programming20

Union TypeScala 3case class Cat(name:String)case class Dog(name: String)type Animal Cat Dogor evendef func(a: Cat Dog ) : String ?Algebras in Programming21

Enums as ADTScala 3enum Color(val rgb: Int) {case Redextends Color(0xFF0000)case Green extends Color(0x00FF00)case Blue extends Color(0x0000FF)case Mix(mix: Int) extends Color(mix)}Algebras in Programming22

Very common ADTs Option EitherAlgebras in Programming23

Option(more or less)sealed trait Option[ A]final case class Some[ A](value: A) extends Option[A]case object None extends Option[Nothing]Algebras in Programming24

Either(more or less)sealed trait Either[ A, B] extendsfinal case class Left[ A, B] (value: A) extends Either[A, B]final case class Right[ A, B]( value: B) extends Either[A, B]Algebras in Programming25

ADT Parametrized : They can have type parameters Product Types: Think AND Sum Types: Think ORAlgebras in Programming26

GADTGeneralized Algebraic Data Type A generalization of parametric algebraic datatypes.Algebras in Programming27

GADTExamplesealed trait Expr[T]case class Num(i: Int) extends Expr[Int]case class Bool(b: Boolean) extends Expr[Boolean]case class Add(x: Expr[Int], y: Expr[Int]) extends Expr[Int]case class Mult(x: Expr[Int], y: Expr[Int]) extends Expr[Int]case class Eq[A](x: Expr[A], y: Expr[A]) extends Expr[Boolean]Algebras in Programming28

GADTExampledef eval[T](e: Expr[T]): T e match {case Num(i) icase Bool(b) bcase Add(x,y) eval(x) eval(y)case Mult(x,y) eval(x)*eval(y)case Eq(x,y) eval(x) eval(y)}Algebras in Programming29

GADTExampleval expr1 Mult(Add(Num(1),Num(2)),Num(4))val expr2 Num(12)val expr3 Eq(expr1,expr2)eval(expr3) true: BooleanAlgebras in Programming30

GADT Type-safe business logic Type-safe DSLsAlgebras in Programming31

Coool, but.where the heck is the Algebra?Algebras in Programming32

Sum Typesealed trait VehicleTypecase object Car extends VehicleTypecase object Moto extends VehicleTypeAlgebras in Programming33

Sum Typesealed trait VehicleTypecase object Car extends VehicleTypecase object Moto extends VehicleTypeHow many VehicleTypes?Algebras in Programming34

Sum Typesealed trait Colourcase object Red extends Colourcase object Yellow extends Colourcase object Blue extends ColourAlgebras in Programming35

Sum Typesealed trait Colourcase object Red extends Colourcase object Yellow extends Colourcase object Blue extends ColourHow many Colours?Algebras in Programming36

Sum Typesealed trait VehicleTypecase object Car extends VehicleTypecase object Moto extends VehicleType2 VehicleTypessealed trait Colourcase object Red extends Colourcase object Yellow extends Colourcase object Blue extends Colour3 ColoursAlgebras in Programming37

Product Typecase class Vehicle (vehicleType:VehicleType, colour:Colour)Algebras in Programming38

Product Typecase class Vehicle (vehicleType:VehicleType, colour:Colour)How many vehicles?If 2 VehicleTypes and 3 Colours?Algebras in Programming39

Product Typecase class Vehicle (vehicleType:VehicleType, colour:Colour)If 2 VehicleTypes and 3 Colours?2 * 3 6 VehiclesAlgebras in Programming40

Product Typecase class Vehicle (vehicleType:VehicleType, colour:Colour, isUsed:Boolean)If 2 VehicleTypes, 3 Colours and 2 Boolean types?Algebras in Programming41

Product Typecase class Vehicle (vehicleType:VehicleType, colour:Colour, isSecondHand:Boolean)If 2 VehicleTypes, 3 Colours and 2 Boolean types?2 * 3 * 2 12 VehiclesAlgebras in Programming42

ADTAs in elementary algebra Sum is the result of addition Product is the result of multiplication.Algebras in Programming43

Function TypeFunction is a type in Scaladef like(colour:Colour) :Booleanorval like : Colour Booleanalsotype Like Colour BooleanAlgebras in Programming44

Function Typetype Like Colour - BooleanRed - {t,f}Yellow - {t,f}Blue - {t,f}How many implementations?Algebras in Programming45

Function Typetype Like Colour - BooleanRed - {t,f}Yellow - {t,f}Blue - {t,f}3There can be 2 * 2 * 2 2 implementationsAlgebras in Programming46

Function Typesealed trait Countrycase object France extends Countrycase object UK extends Countrycase object Germany extends Countrycase object Japan extends Countrycase object USA extends Country5 countriesAlgebras in Programming47

Function Typesealed trait Brandcase object Brand1 extends Brandcase object Brand2 extends Brand.case object Brand20 extends Brand2O brandsAlgebras in Programming48

Function Typedef isProduced(brand:Brand) : CountryBrand1 - {France, UK, Germany, Japan, USA}Brand2 - {France, UK, Germany, Japan, USA}.Brand20 - {France, UK, Germany, Japan, USA}How many implementations?Algebras in Programming49

Function Typedef isProduced(brand:Brand) : CountryBrand1 - {France, UK, Germany, Japan, USA}Brand2 - {France, UK, Germany, Japan, USA}.Brand20 - {France, UK, Germany, Japan, USA}There can be 5 * 5 * . * 5 (20 times) 5implementationsAlgebras in Programming2050

ExponentialsIn Category TheoryIn mathematical literature, the function object,or the internal hom-object between two objects aand b, is often called the exponential and denotedaby b .Algebras in Programming51

ExponentialsIn simpler termsA Function Type val f : A Bcorresponds to the exponentialAlgebras in Programming52

Practical exampleFrom the book: Functional Programming for Mortals (A C) ((B C) C) (Either[A, B] C) CAlgebras in Programming53

More Algebras Tagless Final Algebra Free Μonads AlgebraAlgebras in Programming54

Tagless Final vs Free Μonads The comparison is out of scope for this talk But let's try to find out what Algebra means A random blogpost: Free Monad vs Tagless FinalAlgebras in Programming55

Tagless Final Algebratraitdefdefdef}DatabaseAlgebra[F[ ], T] {create(t: T): F[Boolean]read(id: Long): F[Either[DatabaseError, T]]delete(id: Long): F[Either[DatabaseError, Unit]]. tagless final encoded algebras.Algebras in Programming56

Free Monad Algebrasealed trait DBFreeAlgebraT[T]case class Create[T](t: T)extends DBFreeAlgebraT[Boolean]case class Read[T](id: Long)extends DBFreeAlgebraT[Either[DatabaseError, T]]case class Delete[T](id: Long)extends DBFreeAlgebraT[Either[DatabaseError, Unit]] . We need to create some interpreters to interpret ouralgebra into actions' . For this section we’ll create interpreters to execute.Algebras in Programming57

Free Monad and Tagless Final in essence the Interpreter pattern A grammar for a simple language should bedefined in Free Monad and Tagless Final : the grammaris called "Algebra" the grammar/algebra is implemented by concreteimplementations.Algebras in Programming58

Category Theory formalizes mathematical structure and its conceptsin terms of a labeled directed graph called acategory, whose nodes are called objects, andwhose labelled directed edges are called arrows(or morphisms) the mathematics of mathematics the science of composition and abstraction the mathematics behind functional programmingAlgebras in Programming59

Algebras in Category Theory F-algebra F-coalgebra Free Algebra Cofree AlgebraAlgebras in Programming60

Algebra Set of A Some operator unary: A A binary (A, A) A n-ary (A,A,.,A ) A What about Seq[A] A ? or Option[A] A F[A] AAlgebras in Programming61

F-Algebra F[A] A If the F is also a functor this is called F-algebra F-algebra generalization of normal algebraAlgebras in Programming62

Co Co-Algebra Co-FreeAlgebras in Programming63

Co Co-Algebra Co-FreeWhat does co- mean?Algebras in Programming64

Duality in Category TheoryDuality is a correspondence between the propertiesof a category C and the dual properties of theopopposite category CAlgebras in Programming65

F-coalgebra if F[A] A is an algebra If we reverse the arrows type Coalgebra[F[ ], A] A F[A]Algebras in Programming66

Recursion Schemes a calculus for lazy functional programmingbased on recursion operators associated withdata type definitions. in simple terms: is an advanced functionalprogramming technique that moves the therecursion in the type level using F-Algebras and F- CoalgebrasAlgebras in Programming67

Recap (G)ADT analogy to elementary algebra Sum Type arithmetic addition Product Type arithmetic multiplication Function Type exponential operation Free Monads Algebra - Tagless Final Algebra Grammarin Interpreter Pattern F-algebra F-coalgebraAlgebras in Programming68

References / Read more https://en.wikipedia.org/wiki/Algebra What the F is a GADT? GADT support in Scala Function Types Functional Programming for Mortals Free Monad vs Tagless Final Recursion Schemes for Higher Algebras The Science Behind Functional Programming AST playground: recursion schemes and recursive dataAlgebras in Programming69

sInProgramming.pdfHarry Laoulakos : @harrylaouAlgebras in Programming70

a calculus for lazy functional programming based on recursion operators associated with data type definitions. in simple terms: is an advanced functional programming technique that moves the the recursion in the type level using F-Algebras and