Scala, définir un réseau en utilisant l'algèbre de typelevel

Question

Prémisse: Je suis nouveau à Scala

Je voudrais définir une (semi)lattice au sens mathématique: un ordre partiel dans lequel tous les deux éléments a une jointure ou Supremium. Il n'est pas nécessaire que les éléments soient des nombres, mais vous devez définir une relation d'ordre partielle.

Le réseau que je dois construire est quelque chose comme ça (diagram):

Grandparent 
    |  | 
    v  v 
Parent  Uncle 
    | 
    v 
Children 

où Children < Parent, Parent < Grandparent, Uncle < Grandparent mais pas Children < Uncle. J'ai trouvé le trait BoundedLattice de Typelevel's Algebra library. Est-il possible avec cette bibliothèque de spécifier cette structure?

Answer 1

Votre diagramme de relations n'autorise que la création de (jointure non bornée). Vous pouvez utiliser Semilattice de cats-kernel (c'est une dépendance de algebra de toute façon) ou JoinSemilattice de algebra (la seule différence est que l'opération est appelée "join").

Ayant borné s-l. nécessite un élément "minimum", et Grandparent dans votre cas est un "maximum".

---

Je vais montrer un exemple d'implémentation avec quelques exemples d'utilisation. Tout d'abord, Déclarons nos types:

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

et instances classe de types:

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 
} 

Pour obtenir un ordre partiel, vous avez besoin Eq exemple. Celui-ci est _ == _, ce qui est tout à fait bien pour les objets singleton

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

Depuis notre opération est « join », méthode asJoinPartialOrder est utilisé

implicit val relPartialOrder = relSemilattice.asJoinPartialOrder 

Une fois que nous obtenons ordre partiel, les opérateurs de comparaison sont une importation loin . Bien qu'il y ait un hic:

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) 

Maintenant, nous pouvons vérifier que vos propriétés souhaitées détiennent:

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

Pour les éléments où l'ordre est indécidable, les comparaisons régulières renverront toujours false:

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

Vous pouvez utiliser pmin ou pmax pour obtenir un min/max sur deux, enveloppé dans Some, ou None si les éléments ne pouvaient pas être comparés.

assert((child pmin uncle) == None) 

Une autre chose, lattices forment un Semigroup, de sorte que vous pouvez utiliser "tie-combattant" plus pour obtenir le rejoindre:

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

---

Vous pouvez également définir un ordre partiel sans semitreillis :

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 
} 

vous n'avez pas besoin Eq pour cela, mais vous ne pas combiner semigroupe operato r.