Scala，使用类型级别的代数定义格

Question

前提:我是 Scala 新手

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

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

    Grandparent
    |        |
    v        v
Parent     Uncle
    |
    v 
Children

哪里Children < Parent , Parent < Grandparent , Uncle < Grandparent但不是Children < Uncle .

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

Answer 1

您的关系图仅允许(无界连接)半格子。您可以使用Semilattice来自cats-kernel (无论如何，它是 algebra 的依赖项)或 JoinSemilattice来自algebra (唯一的区别是操作称为“加入”)。

有界 s-l。需要一个“最小”元素，并且 Grandparent在你的情况下是“最大值”。

---

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

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)

对于顺序无法确定的元素，常规比较将始终返回 false :

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

您可以使用pmin或pmax得到两个中的最小值/最大值，包裹在 Some 中，或None如果元素无法比较。

assert((child pmin uncle) == None)

另一件事，格子形成Semigroup ，因此您可以使用“tie-fighter”加号来获得连接:

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为此，但您没有得到半群组合运算符。