 Ignus - 3 years ago 161
Scala Question

# Scala, define a lattice using typelevel's algebra

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
``````

where
`Children < Parent`
,
`Parent < Grandparent`
,
`Uncle < Grandparent`
but not
`Children < Uncle`
.

I found the trait BoundedLattice from Typelevel's Algebra library. Is it possible with this library to specify this structure? Oleg Pyzhcov

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download