Scala,使用typelevel的代数定义一个点阵

Question

前提:我是Scala的新手

我想在数学意义上定义一个(半)格子:一个部分顺序,其中每两个元素都有一个连接或supremium.元素不必是数字,但您必须定义部分顺序关系.

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

    Grandparent
    |        |
    v        v
Parent     Uncle
    |
    v 
Children

其中Children < Parent,Parent < Grandparent,Uncle < Grandparent但不是Children < Uncle.

我从Typelevel的代数库中找到了特征BoundedLattice.是否可以使用此库来指定此结构？

Answer 1

您的关系图仅允许(无界连接)半格.您可以使用Semilatticefrom cats-kernel(它是algebra无论如何的依赖关系)或JoinSemilatticefrom algebra(唯一的区别是该操作被称为"join").

有边界sl.需要一个"最小"元素,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这个,但你没有得到半群组合算子.