Scala，使用typelevel的代数定义一个lattice

Question

前提：我是 Scala 新手

我想在数学意义上定义一个 (semi)lattice：每两个元素都有一个连接或 supremium 的偏序。元素不一定是数字，但必须定义偏序关系

我需要构建的格子是这样的(diagram):

    Grandparent
    |        |
    v        v
Parent     Uncle
    |
    v 
Children

其中 Children < Parent、Parent < Grandparent、Uncle < Grandparent 而不是 Children < Uncle.

我发现了特质 BoundedLattice from Typelevel's Algebra library。这个库可以指定这个结构吗？

Answer 1

您的关系图只允许（无界连接）半格。您可以使用 cats-kernel 中的 Semilattice （无论如何它是 algebra 的依赖项）或 algebra 中的 JoinSemilattice （唯一的区别是操作被称为 "join").

有界 s-l。需要一个 "minimum" 元素，而 Grandparent 在你的例子中是一个 "maximum".

我将展示带有一些使用示例的示例实现。首先，让我们声明我们的类型：

sealed trait Rel
case object Grandparent extends Rel
case object Parent extends Rel
case object Child extends Rel
case object Uncle extends Rel

和类型类实例：

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
}

要获得部分订单，您需要 Eq 个实例。这个是 _ == _，对于单例对象来说完全没问题

implicit val relEq: Eq[Rel] = Eq.fromUniversalEquals

由于我们的操作是"join"，所以使用方法asJoinPartialOrder

implicit val relPartialOrder = relSemilattice.asJoinPartialOrder

一旦我们得到偏序，比较运算符就只差一个导入了。虽然有一个陷阱：

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)

现在我们可以检查您想要的属性是否成立：

assert(child < parent)
assert(parent < grandparent)
assert(uncle < grandparent)

对于顺序不确定的元素，常规比较总是return false:

assert(child < uncle == false)
assert(uncle < child == false)

您可以使用 pmin 或 pmax 从两个中得到一个 min/max，包裹在 Some 中，如果元素不能，则使用 None进行比较。

assert((child pmin uncle) == None)

还有一点，格子形成了一个Semigroup，所以你可以用"tie-fighter"加上得到join:

import cats.syntax.semigroup._
assert((parent |+| uncle) == grandparent)
assert((child |+| parent) == parent)

您也可以定义不带半格的偏序：

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
}

你不需要 Eq，但你没有得到半群组合运算符。

Scala，使用typelevel的代数定义一个lattice

Scala, define a lattice using typelevel's algebra

scala

algebra