Ignus 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):

| |
v v
Parent Uncle

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?

Answer Source

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