tur/typeclass-lattice
Semigroup, Monoid, and the selection newtypes.
The vocabulary for "these two values combine, associatively". Turmeric had none of it: no Semigroup, no Monoid, no name for the operation that effects-chain in tur-signal and Category's comp in stdlib/arrow.tur each hand-roll for one shape.
NOT auto-loaded -- (load "stdlib/typeclass-lattice.tur") to use it. The auto-load list is paid by every TU in every build, and nothing in stdlib depends on these classes.
Since: lattice-vocabulary-plan L2 (lattice four: L3)
Semigroup
(defclass Semigroup [a])
an associative binary operation.
| a | the type being combined |
(combine [x :a y :a] :a)-
the associative operation on
xandy
associativity -- (combine (combine x y) z) = (combine x (combine y z))
(combine (:: 3 Sum) (:: 7 Sum)) ; => Sum 10
Since: lattice-vocabulary-plan L2
Monoid
(defclass Monoid [a] [(Semigroup a)])
a Semigroup with an identity element.
| a | the type being combined |
(mempty [] :a)-
the identity element (nullary; dispatched by the expected type)
identity -- (combine (mempty) x) = x = (combine x (mempty))
(let [unit : Sum (mempty)] (combine unit (:: 3 Sum))) ; => Sum 3
Note the binding: (combine (mempty) x) does not elaborate, because argument inference runs left-to-right and in first position mempty has nothing to fix its type yet. In second position, or bound to a typed local, it is fine.
Since: lattice-vocabulary-plan L2
Sum
(defopaque Sum :int)
int under addition. Identity 0.
Product
(defopaque Product :int)
int under multiplication. Identity 1.
MinI
(defopaque MinI :int)
int under minimum. Identity is the largest int64.
MaxI
(defopaque MaxI :int)
int under maximum. Identity is the smallest int64.
Any
(defopaque Any :bool)
bool under disjunction. Identity false.
All
(defopaque All :bool)
bool under conjunction. Identity true.
Eq[Sum]
(definstance Eq [Sum])
structural equality on the carrier.
Eq[Product]
(definstance Eq [Product])
structural equality on the carrier.
Eq[MinI]
(definstance Eq [MinI])
structural equality on the carrier.
Eq[MaxI]
(definstance Eq [MaxI])
structural equality on the carrier.
Eq[Any]
(definstance Eq [Any])
structural equality on the carrier.
Eq[All]
(definstance Eq [All])
structural equality on the carrier.
Semigroup[Sum]
(definstance Semigroup [Sum])
addition.
Semigroup[Product]
(definstance Semigroup [Product])
multiplication.
Semigroup[MinI]
(definstance Semigroup [MinI])
minimum.
Semigroup[MaxI]
(definstance Semigroup [MaxI])
maximum.
Semigroup[Any]
(definstance Semigroup [Any])
disjunction.
Semigroup[All]
(definstance Semigroup [All])
conjunction.
Monoid[Sum]
(definstance Monoid [Sum])
identity 0.
Monoid[Product]
(definstance Monoid [Product])
identity 1.
Monoid[MinI]
(definstance Monoid [MinI])
identity is the largest int64.
Monoid[MaxI]
(definstance Monoid [MaxI])
identity is the smallest int64.
Monoid[Any]
(definstance Monoid [Any])
identity false.
Monoid[All]
(definstance Monoid [All])
identity true.
law-associative?
(law-associative? [^Semigroup A ^Eq A])
does combine associate for these three values?
| x y z -- values to check |
true when (combine (combine x y) z) equals (combine x (combine y z)).
(law-associative? (:: 1 Sum) (:: 2 Sum) (:: 3 Sum)) ; => true
Since: lattice-vocabulary-plan L2
law-identity?
(law-identity? [^Monoid A ^Eq A])
is mempty a two-sided identity for this value?
| x | value to check |
true when (combine (mempty) x) and (combine x (mempty)) both equal x.
(law-identity? (:: 5 Product)) ; => true
Since: lattice-vocabulary-plan L2
mconcat-from
(mconcat-from [^Monoid A])
fold a Vec into an accumulator with combine.
| v | the Vec to fold | |
| i | index to start at | |
| n | index to stop before | |
| acc | accumulator |
acc combined with v[i..n).
Since: lattice-vocabulary-plan L4
mconcat
(mconcat [^Monoid A])
combine every element of a Vec, left to right, from mempty.
| v | the Vec to fold |
mempty when v is empty, else v[0] combined with the rest in order.
(mconcat (vec-of (:: 1 Sum) (:: 2 Sum) (:: 3 Sum))) ; => Sum 6
Since: lattice-vocabulary-plan L4
JoinSemilattice
(defclass JoinSemilattice [a])
associative, commutative, IDEMPOTENT combine (least upper bound).
| a | the type being joined |
(join [x :a y :a] :a)-
the least upper bound of
xandy
associativity -- (join (join x y) z) = (join x (join y z)) commutativity -- (join x y) = (join y x) idempotence -- (join x x) = x
(join (:: 3 MaxI) (:: 7 MaxI)) ; => MaxI 7
Since: lattice-vocabulary-plan L3
MeetSemilattice
(defclass MeetSemilattice [a])
the dual of JoinSemilattice (greatest lower bound).
| a | the type being met |
(meet [x :a y :a] :a)-
the greatest lower bound of
xandy
associativity, commutativity, idempotence -- as for join
(meet (:: 3 MinI) (:: 7 MinI)) ; => MinI 3
Since: lattice-vocabulary-plan L3
BoundedJoin
(defclass BoundedJoin [a] [(JoinSemilattice a)])
a JoinSemilattice with a least element.
(bottom [] :a)-
the least element (nullary; dispatched by the expected type)
identity -- (join (bottom) x) = x
(let [z : MaxI (bottom)] (join z (:: 3 MaxI))) ; => MaxI 3
Since: lattice-vocabulary-plan L3
BoundedMeet
(defclass BoundedMeet [a] [(MeetSemilattice a)])
a MeetSemilattice with a greatest element.
(top [] :a)-
the greatest element (nullary; dispatched by the expected type)
identity -- (meet (top) x) = x
(let [t : MinI (top)] (meet t (:: 3 MinI))) ; => MinI 3
Since: lattice-vocabulary-plan L3
JoinSemilattice[MaxI]
(definstance JoinSemilattice [MaxI])
least upper bound is the larger int.
BoundedJoin[MaxI]
(definstance BoundedJoin [MaxI])
least element is the smallest int64.
MeetSemilattice[MinI]
(definstance MeetSemilattice [MinI])
greatest lower bound is the smaller int.
BoundedMeet[MinI]
(definstance BoundedMeet [MinI])
greatest element is the largest int64.
JoinSemilattice[Any]
(definstance JoinSemilattice [Any])
disjunction.
BoundedJoin[Any]
(definstance BoundedJoin [Any])
least element is false.
MeetSemilattice[All]
(definstance MeetSemilattice [All])
conjunction.
BoundedMeet[All]
(definstance BoundedMeet [All])
greatest element is true.
law-join-associative?
(law-join-associative? [^JoinSemilattice A ^Eq A])
does join associate?
| x y z -- values to check |
true when (join (join x y) z) equals (join x (join y z)).
(law-join-associative? (:: 1 MaxI) (:: 2 MaxI) (:: 3 MaxI)) ; => true
Since: lattice-vocabulary-plan L3
law-join-commutative?
(law-join-commutative? [^JoinSemilattice A ^Eq A])
does join commute?
| x y -- values to check |
true when (join x y) equals (join y x).
(law-join-commutative? (:: 1 MaxI) (:: 2 MaxI)) ; => true
Since: lattice-vocabulary-plan L3
law-join-idempotent?
(law-join-idempotent? [^JoinSemilattice A ^Eq A])
is join idempotent?
| x | value to check |
true when (join x x) equals x.
(law-join-idempotent? (:: 1 MaxI)) ; => true
Since: lattice-vocabulary-plan L3
law-bottom-identity?
(law-bottom-identity? [^BoundedJoin A ^Eq A])
is bottom a left identity for join?
| x | value to check |
true when (join (bottom) x) equals x.
(law-bottom-identity? (:: 3 MaxI)) ; => true
Since: lattice-vocabulary-plan L3
lattice-leq?
(lattice-leq? [^JoinSemilattice A ^Eq A])
the partial order induced by join.
| x | candidate lower value | |
| y | candidate upper value |
true when (join x y) equals y, i.e. x <= y in the lattice order.
(lattice-leq? (:: 3 MaxI) (:: 7 MaxI)) ; => true
Since: lattice-vocabulary-plan L3
law-meet-idempotent?
(law-meet-idempotent? [^MeetSemilattice A ^Eq A])
is meet idempotent?
| x | value to check |
true when (meet x x) equals x.
(law-meet-idempotent? (:: 1 MinI)) ; => true
Since: lattice-vocabulary-plan L3
law-top-identity?
(law-top-identity? [^BoundedMeet A ^Eq A])
is top a left identity for meet?
| x | value to check |
true when (meet (top) x) equals x.
(law-top-identity? (:: 3 MinI)) ; => true
Since: lattice-vocabulary-plan L3