Scala, define a lattice using typelevel's algebra

Question

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?

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

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.

Scala, define a lattice using typelevel's algebra

Sign up