Ignus - 3 years ago 151
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?

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