AbstractAlgebra.MD

Abstract Algebra

Summary of structures with one operation

Summary of structures in abstract algebra consisting of:

• a Set S
• binary operation * that are total (so they form a Magma).

Algebraic structure	associativity	identity	invertibility	commutativity	idempotency
Semigroup	associativity
Commutative semigroup	associativity			commutativity
Inverse semigroup	associativity		invertibility
Monoid	associativity	identity
Commutative Monoid	associativity	identity		commutativity
Group	associativity	identity	invertibility
Abelian Group	associativity	identity	invertibility	commutativity
Band	associativity				idempotency
Semilattice	associativity			commutativity	idempotency
Bounded semilattice	associativity	identity		commutativity	idempotency

Properties of operation

property	definition
closure (totality)	x * y belongs to S
associativity	x * (y * z) = (x * y) * z
identity	x * id = id * x = x
invertibility	x * x' = x' * x = id
commutativity	x * y = y * x
idempotency	x * x = x

Magma

• PR for Cats
• Medial Magma

Semigroup

Abstract over associative operation combine on some proper type A.

trait Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
}

• Semigroup Law - associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))

• Derived methods:

def combineN(a: A, n: Int): A // multiply1
def combineAllOption(as: TraversableOnce[A]): Option[A]

• Semigroup can be defined for:

  • containers like List, Vector, Nel with concatenation
  • numeric types like Short/Int/Long/BigInteger with + or *
  • Strings with string concatenation

• Examples how to define alternative Semigroup instances for Option, Int with * and usage. Examples for usage of derived methods and combine (src)

• Implementations: Cats Scalaz 7, Scalaz 8, twitter/algebird, zio-prelude, Haskell, Racket algebraic, Java

• Resources:

  • herding cats - Semigroup (blog post)
  • Cats docs
  • Scalaz example

Commutative Semigroup

Semigroup where operation is commutative

trait CommutativeSemigroup[A] extends Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
}

• laws:
  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. commutativity: (x |+| y) == (y |+| x)

Monoid

Abstract over associative operation combine that have default value empty.

trait Monoid[A] extends Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
}

• Monoid Laws

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. right identity: (x |+| empty) == x
  3. left identity: (empty |+| x) == x

• Derived methods:

def combineAll(as: TraversableOnce[A]): A

• Monoid can be defined for List (with list concatenation, Nil), Vector, Int with +, Strings with string concatenation. NEL is Semigroup but not a Monoid, same with non empty Strings :)

• We can create Monoid for any Semigroup by wrapping it in Option (None is empty value) same with Map

• It is possible to provide additional structure to Monoid (but not as much as in Group). Such monoids (ReductiveMonoid, CancellativeMonoid, GCDMonoid) are implemented in monoid-subclasses in Haskell described in paper Adding Structure to Monoids by Mario Blaževic

• We can joint two monoids into tuple of monoids.

• Implementations: Cats, Scalaz, Scalaz 8, Racket algebraic, Java functionaljava Java DataFixerUpper

• Resources:

  • FSiS 4 - Semigroup, Monoid, and Foldable type classes - Michael Pilquist video 23:02
  • herding cats - Monoid (blog post)
  • Cats docs
  • twitter/algebird src docs
  • (Haskell) base/Data-Monoid
  • (Haskell) Monoids, theme and variations - Brent Yorgey (video) (paper)
  • (Haskell) https://byorgey.wordpress.com/2011/04/18/monoids-for-maybe/
  • (Haskell) http://blog.sigfpe.com/2009/01/haskell-monoids-and-their-uses.html
  • (Haskell) https://apfelmus.nfshost.com/articles/monoid-fingertree.html
  • On Monoids - Rúnar Bjarnason (blog post)

Monoid homomorphisms

Function f between two monoids A, B that preserve the structure of monoid:

1. f(A.empty) == B.empty
2. f(A.combine(a1,a2)) == B.compine( f(a1), f(a2) )

For example size and Monoid - list with concatenation and integers with addition.

• Resources:
  • Rúnar Óli Bjarnason - Composing Programs (video)
  • (Haskell) Monoids, theme and variations - Brent Yorgey (video) (paper)

Commutative Monoid

Monoid where operation is commutative

trait CommutativeMonoid[A] extends Monoid[A] with CommutativeSemigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. right identity: (x |+| empty) == x
  3. left identity: (empty |+| x) == x
  4. commutativity: (x |+| y) == (y |+| x)

• Resources

  • Cats src (laws)

RegularSemigroup

Semigroup where element with it's inverse don't produce neutral element but produce sth that behaves like one.

trait RegularSemigroup[A] extends Monoid[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
  def inverse(a: A): A
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. pseudoinverse 1: x |+| -x |+| x == x
  3. pseudoinverse 2: -x |+| x |+| -x == -x

• there could be multiple inverse elements (in group there is only one inverse)

• x |+| -x is idempotent, because (x |+| -x) |+| (x |+| -x) == (x |+| -x |+| x) |+| -x == x |+| -x

• Resources:

  • Haskell Live-Coding, Session 4.1, Regular and Inverse Semigroups - Edward Kmett video

InverseSemigroup

Semigroup (or regular semigroup) in which every element has unique inverse. Other definition: Semigroup in which every element has at least one inverse and all indempotent elements commute.

trait InverseSemigroup[A] extends RegularSemigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
  def inverse(a: A): A
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. pseudoinverse 1: x |+| -x |+| x == x
  3. pseudoinverse 2: -x |+| x |+| -x == -x
  4. pseudoinverse is unique

• Resources:

  • Haskell Live-Coding, Session 4.1, Regular and Inverse Semigroups - Edward Kmett video

Group

Monoid where each element has an inverse

trait Group[A] extends Monoid[A] {
  def combine(x: A, y: => A): A // |+| mappend <>
  def empty: A // mempty
  def inverse(a: A): A
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. right identity: (x |+| empty) == x
  3. left identity: (empty |+| x) == x
  4. inverse: (x |+| -x) == (-x |+| x) == empty

• derived methods:

def remove(a: A, b: A): A = combine(a, inverse(b))

• Resources:
  • (Cats Group src) (laws)
  • twitter/algebird Group src docs
  • (Haskell) monoids Data.Group

Abelian Group (Commutative Group)

Group where operation |+| is commutative

trait CommutativeGroup[A] extends Group[A] with CommutativeMonoid[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
  def inverse(a: A): A
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. right identity: (x |+| empty) == x
  3. left identity: (empty |+| x) == x
  4. inverse: (x |+| -x) == (-x |+| x) == empty
  5. commutativity: (x |+| y) == (y |+| x)

• Resources:

  • Cats src laws
  • (Haskell) algebra/Numeric.Additive Abelian

Band (Idempotent semigroup)

Semigroup whose operation is also idempotent

trait Band[A] extends Semigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. idempotent: (x |+| x) == x

• Resources:

  • cats (src) (laws)

bands with additional structure:

type of band	additional law
left zero band	x + y == x
right zero band	x + y == y
rectangular band	x + y + x == x
normal band	z + x + y + z == z + y + x + z
left-regular band	x + y + x == x + y
right-regular band	x + y + x == y + x
regular bands	z + x + z + y + z == z + x + y + z

Semilattice

Semilattice is commutative semigroup whose operation is also idempotent.

trait Semilattice[A] extends Band[A] with CommutativeSemigroup[A] {
  def combine(x: A, y: => A): A // |+| mappend
}

• laws:
  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. commutativity: (x |+| y) == (y |+| x)
  3. idempotent: (x |+| x) == x

MeetSemilattice and JoinSemilattice

Sometimes (in typelevel/algebra) there are two definitions of Semilattice:

A meet-semilattice (or lower semilattice) is a semilattice whose operation is called "meet", and which can be thought of as a greatest lower bound.

trait MeetSemilattice[A] {
 def meet(lhs: A, rhs: A): A
}

and a join-semilattice (or upper semilattice) is a semilattice whose operation is called "join", and which can be thought of as a least upper bound

trait JoinSemilattice[A] {
 def join(lhs: A, rhs: A): A
}

• Resources:
  • Cats Semilattice src laws
  • scalaz Semilattice src
  • typelevel/algebra Meet Semilattice
  • typelevel/algebra Join Semilattice

Bounded Semilattice

Semilattice that has identity or Commutative Monoid that idempotent.

trait BoundedSemilattice[A] extends Semilattice[A] with CommutativeMonoid[A] {
  def combine(x: A, y: => A): A // |+| mappend
  def empty: A // mempty
}

• laws:
  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. right identity: (x |+| empty) == x
  3. left identity: (empty |+| x) == x
  4. commutativity: (x |+| y) == (y |+| x)
  5. idempotent: (x |+| x) == x

Bounded Join Semilattice, Bounded Meet Semilattice

Similar as with Semilattice definition we can define Bounded Join Semilattice and Bounded Meet Semilattice

trait BoundedJoinSemilattice[A] extends JoinSemilattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
}

trait BoundedMeetSemilattice[A] extends MeetSemilattice[A] {
  def meet(lhs: A, rhs: A): A
  def one: A
}

• Resources:
  • typelevel/cats BoundedSemilattice src laws
  • typelevel/algebra Bounded Join Semilattice
  • typelevel/algebra Bounded Meet Semilattice

Algebraic structures with two operations

Lattice

Has two associativity, commutativity and idempotent operations: join and meet that obey absorption law:

trait Lattice[A] extends JoinSemilattice[A] with MeetSemilattice[A] {
  def join(lhs: A, rhs: A): A
  def meet(lhs: A, rhs: A): A
}

• laws:

  1. associativity: (x join y) join z) == (x join (y join z))
  2. commutativity: (x join y) == (y join x)
  3. idempotent: (x join x) == x
  4. associativity: (x meet y) meet z) == (x meet (y meet z))
  5. commutativity: (x meet y) == (y meet x)
  6. idempotent: (x meet x) == x
  7. absorption: a meet (a join b) == a join (a meet b) == a

• typelevel/algebra Lattice src laws

Distributive Lattice

Lattice that obey distributive law

trait DistributiveLattice[A] extends Lattice[A] {
  def join(lhs: A, rhs: A): A
  def meet(lhs: A, rhs: A): A
}

• laws:

  1. associativity: (x join y) join z) == (x join (y join z))
  2. commutativity: (x join y) == (y join x)
  3. idempotent: (x join x) == x
  4. associativity: (x meet y) meet z) == (x meet (y meet z))
  5. commutativity: (x meet y) == (y meet x)
  6. idempotent: (x meet x) == x
  7. absorption: a meet (a join b) == a join (a meet b) == a
  8. distributive: a meet (b join c) == (a meet b) join (a meet c)
  9. distributive: a join (b meet c) == (a join b) meet (a join c)

• typelevel/algebra Distributive Lattice

BoundedLattice

trait BoundedLattice[A] extends Lattice[A] with BoundedMeetSemilattice[A] with BoundedJoinSemilattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
}

• laws:
  1. associativity: (x join y) join z) == (x join (y join z))
  2. commutativity: (x join y) == (y join x)
  3. idempotent: (x join x) == x
  4. associativity: (x meet y) meet z) == (x meet (y meet z))
  5. commutativity: (x meet y) == (y meet x)
  6. idempotent: (x meet x) == x
  7. absorption: a meet (a join b) == a join (a meet b) == a
  8. identity of zero: a join zero == a
  9. identity of one: a meet one == a

Bounded Distributive Lattice

trait BoundedDistributiveLattice[A] extends BoundedLattice[A] with DistributiveLattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
}

• laws:

  1. associativity: (x join y) join z) == (x join (y join z))
  2. commutativity: (x join y) == (y join x)
  3. idempotent: (x join x) == x
  4. associativity: (x meet y) meet z) == (x meet (y meet z))
  5. commutativity: (x meet y) == (y meet x)
  6. idempotent: (x meet x) == x
  7. absorption: a meet (a join b) == a join (a meet b) == a
  8. distributive: a meet (b join c) == (a meet b) join (a meet c)
  9. distributive: a join (b meet c) == (a join b) meet (a join c)
  10. identity of zero: a join zero == a
  11. identity of one: a meet one == a

• typelevel/algebra Bounded Distributive Lattice

Heyting algebras

Heyting algebra is bounded distributive lattices equipped with operation imp (written as ->) and complement operation (written as -a)

trait Heyting[A] extends BoundedDistributiveLattice[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
  def imp(a: A, b: A): A
  def complement(a: A): A // a imp 0
}

• laws:

  1. associativity: (x join y) join z) == (x join (y join z))
  2. commutativity: (x join y) == (y join x)
  3. idempotent: (x join x) == x
  4. associativity: (x meet y) meet z) == (x meet (y meet z))
  5. commutativity: (x meet y) == (y meet x)
  6. idempotent: (x meet x) == x
  7. absorption: a meet (a join b) == a join (a meet b) == a
  8. distributive: a meet (b join c) == (a meet b) join (a meet c)
  9. distributive: a join (b meet c) == (a join b) meet (a join c)
  10. identity of zero: a join zero == a
  11. identity of one: a meet one == a
  12. complement law: a meet -a == 0
  13. implication laws: a -> a == 1 a ∧ (a -> b) == a meet b b ∧ (a -> b) == b a -> (b meet c) == (a -> b) meet (a -> c)

• derived methods:

def or(a: A, b: A): A = join(a, b)
def and(a: A, b: A): A = meet(a, b)
def xor(a: A, b: A): A = or(and(a, complement(b)), and(complement(a), b))
def nand(a: A, b: A): A = complement(and(a, b))
def nor(a: A, b: A): A = complement(or(a, b))
def nxor(a: A, b: A): A = complement(xor(a, b))

• typelevel/algebra Heyting

Boolean algebras

Boolean algebra is Heyting algebras were law of the excluded middle is true

trait Bool[A] extends Heyting[A] {
  def join(lhs: A, rhs: A): A
  def zero: A
  def meet(lhs: A, rhs: A): A
  def one: A
  def imp(a: A, b: A): A
  def complement(a: A): A // a imp 0
}

• derived methods:

def without(a: A, b: A): A = and(a, complement(b))

• laws:

  1. associativity: (x join y) join z) == (x join (y join z))
  2. commutativity: (x join y) == (y join x)
  3. idempotent: (x join x) == x
  4. associativity: (x meet y) meet z) == (x meet (y meet z))
  5. commutativity: (x meet y) == (y meet x)
  6. idempotent: (x meet x) == x
  7. absorption: a meet (a join b) == a join (a meet b) == a
  8. distributive: a meet (b join c) == (a meet b) join (a meet c)
  9. distributive: a join (b meet c) == (a join b) meet (a join c)
  10. identity of zero: a join zero == a
  11. identity of one: a meet one == a
  12. complement law: a meet -a == 0
  13. implication laws:
  • a -> a == 1
  • a ∧ (a -> b) == a meet b
  • b ∧ (a -> b) == b
  • a -> (b meet c) == (a -> b) meet (a -> c)
  14. excluded middle law: (a join (a -> 0)) == 1

• typelevel/algebra Bool

Rig

Ring without (n)egation

trait Ring[T] extends CommutativeGroup[T] {
  def zero: T // empty mempty 
  def plus(l: T, r: T): T // combine mappend <> |+|
  def negate(v: T): T // inverse
  def one: T
  def times(l: T, r: T): T
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. identity: (x |+| zero) == x == (zero |+| x)
  3. inverse: (x |+| -x) == (-x |+| x) == zero
  4. commutativity: (x |+| y) == (y |+| x)
  5. associativity: ((x * y) * z) == (x * (y * z))
  6. right identity: (x * one) == x
  7. left identity: (one * x) == x
  8. distributive: a * (b |+| c) == (a * b) |+| (a * c)

• Resources

  • typelevel/algebra Rng
  • (Haskell) algebra/Numeric.Rig

Rng (Semiring)

Ring without an identity

trait Rng[T] extends CommutativeGroup[T] {
  def zero: T // empty mempty 
  def plus(l: T, r: T): T // combine mappend <> |+|
  def negate(v: T): T // inverse
  def times(l: T, r: T): T
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. identity: (x |+| zero) == x == (zero |+| x)
  3. inverse: (x |+| -x) == (-x |+| x) == zero
  4. commutativity: (x |+| y) == (y |+| x)
  5. associativity: ((x * y) * z) == (x * (y * z))
  6. distributive: a * (b |+| c) == (a * b) |+| (a * c)

• Resources

  • typelevel/algebra Rng
  • (Haskell) algebra/Numeric.Rng

Semiring

• https://github.com/typelevel/algebra/blob/master/core/src/main/scala/algebra/ring/Semiring.scala

Ring

Abelian group with a second binary operation that is associative, is distributive over the abelian group operation, and has an identity element.

trait Ring[T] extends CommutativeGroup[T] {
  def zero: T // empty mempty 
  def plus(l: T, r: T): T // combine mappend <> |+|
  def negate(v: T): T // inverse
  def one: T
  def times(l: T, r: T): T
}

• laws:

  1. associativity: ((x |+| y) |+| z) == (x |+| (y |+| z))
  2. identity: (x |+| zero) == x == (zero |+| x)
  3. inverse: (x |+| -x) == (-x |+| x) == zero
  4. commutativity: (x |+| y) == (y |+| x)
  5. associativity: ((x * y) * z) == (x * (y * z))
  6. right identity: (x * one) == x
  7. left identity: (one * x) == x
  8. distributive: a * (b |+| c) == (a * b) |+| (a * c)

• Resources

  • typelevel/algebra src laws
  • twitter/algebird src docs

United monoid

"Consider two monoids (S, +, 0) and (S, ⋅, 1), which operate on the same set S, such that + is commutative and ⋅ distributes over +.

We call these monoids united if 0 = 1."

• Resources
  • United Monoids - Andrey Mokhov (blog post)

Field

• https://github.com/typelevel/algebra/blob/master/core/src/main/scala/algebra/ring/Field.scala

Tropical semiring (Min-Plus algebra)

• twitter/algebird src

Vector Space

• Resources
  • twitter/algebird src
  • Life After Monoids - Tom Switzer talks about Group, Ring, Vector Space (video)

StarRig

• StarRig non/irreg

Kleene algebra

• Resources:
  • Erik Osheim - Regexes, Kleene Algebras, and Real Ultimate Power! (video)
  • (Haskell) A Very General Method of Computing Shortest Paths (article)

Advanced Algebra Resources

• Encoding of algebraic structures and properties in CubicalTT
• Algorithms for Lie algebras of algebraic groups - Roozemond, D.A.
• Graduate algebra - Drew Anderson