Premise: I'm new to Scala
I would like to define a (semi)lattice in the mathematical sense: a partial order in which every two elements has a join or supremium. It is not necessary the elements to be numbers, but you have to define a partial order relation.
The lattice I need to build is something like this (diagram):
Grandparent
| |
v v
Parent Uncle
|
v
Children
Children < Parent
Parent < Grandparent
Uncle < Grandparent
Children < Uncle
Your relationship diagram only allows for (unbounded join) semilattice. You can use Semilattice
from cats-kernel
(it's a dependency of algebra
anyway) or JoinSemilattice
from algebra
(the only difference is that operation is called "join").
Having bounded s-l. requires a "minimum" element, and Grandparent
in your case is a "maximum".
I'll show a sample implementation with some usage examples. First, let's declare our types:
sealed trait Rel
case object Grandparent extends Rel
case object Parent extends Rel
case object Child extends Rel
case object Uncle extends Rel
and typeclass instances:
import cats.kernel._
// Using Scala 2.12 Single Abstract Method syntax
implicit val relSemilattice: Semilattice[Rel] = {
case (a, b) if a == b => a
case (Grandparent | Uncle, _) | (_, Grandparent | Uncle) => Grandparent
case (Child, b) => b
case (a, Child) => a
}
To get a partial order, you need Eq
instance. This one is _ == _
, which is totally fine for singleton objects
implicit val relEq: Eq[Rel] = Eq.fromUniversalEquals
Since our operation is "join", method asJoinPartialOrder
is used
implicit val relPartialOrder = relSemilattice.asJoinPartialOrder
Once we get partial order, comparison operators are one import away. Although there is a catch:
import cats.syntax.partialOrder._
// Parent < Grandparent // <- this will not compile
// You have to "upcast" to same type to use partial order syntax:
(Parent: Rel) < (Grandparent: Rel)
// for brevity, let's just quickly upcast 'em all in a fresh variables
val List(grandparent, parent, child, uncle) = List[Rel](Grandparent, Parent, Child, Uncle)
Now we can check that your desired properties hold:
assert(child < parent)
assert(parent < grandparent)
assert(uncle < grandparent)
For elements where order is undecidable, regular comparisons will always return false
:
assert(child < uncle == false)
assert(uncle < child == false)
You can use pmin
or pmax
to get a min/max out of two, wrapped in Some
, or None
if the elements could not be compared.
assert((child pmin uncle) == None)
Another thing, lattices form a Semigroup
, so you can use "tie-fighter" plus to get the join:
import cats.syntax.semigroup._
assert((parent |+| uncle) == grandparent)
assert((child |+| parent) == parent)
You can also define a partial order without a semilattice:
implicit val relPartialOrder: PartialOrder[Rel] = {
case (a, b) if a == b => 0.0
case (Grandparent, _) => 1.0
case (_, Grandparent) => -1.0
case (_, Uncle) | (Uncle, _) => Double.NaN
case (Child, _) => -1.0
case (_, Child) => 1.0
}
You don't need Eq
for this, but you don't get semigroup combine operator.