Écriture Type de données algébriques en Scala

Définition d'un ADT

dans le modèle "object-functional" de Scala, vous définissez un trait qui représente L'ADT et tous ses paramètres. Puis pour chacun de vos cas, vous définissez soit un case class et case object. Les paramètres de Type et de valeur sont traités comme des arguments au constructeur de classe. Typiquement, vous faites le trait sealed de sorte que rien en dehors du fichier courant ne peut ajouter de cas.

sealed trait Tree[A]
case class Empty[A]() extends Tree[A]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

alors vous pouvez faire:

scala> Node("foo", Node("bar", Empty(), Empty()), Empty())
res2: Node[String] = Node(foo,Node(bar,Empty(),Empty()),Empty())

c'est un peu ennuyeux que nous devions créer un tas de nouveaux Empty cas, lorsque cette classe ne contient pas de données. En Scala, il est pratique courante de remplacer un argument zéro case class, comme Empty avec un case object, mais dans ce cas, c'est un peu compliqué, parce que un case object est un singleton, mais nous avons besoin d'un Empty pour chaque type d'arbre.

heureusement (ou pas, selon qui vous demandez), avec une annotation de covariance, vous pouvez avoir case object Empty agir comme le vide Tree de type Nothing, qui est le sous-type universel de Scala. En raison de la covariance, ceci Empty est un sous-type de Tree[A] pour tout A:

sealed trait Tree[+A]
case object Empty extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

puis vous obtenez la syntaxe de nettoyage:

scala> Node("foo", Node("bar", Empty, Empty), Empty)
res4: Node[String] = Node(foo,Node(bar,Empty,Empty),Empty)

C'est, en fait, comme la bibliothèque standard de Scala Nil œuvres, à l'égard de List.

d'Exploitation sur l'ADT

Pour utiliser le nouveau ADT, il est courant dans Scala de définir les fonctions récursives qui emploient le match mot clé pour le déconstruire. Voir:

scala> :paste
// Entering paste mode (ctrl-D to finish)

import scala.math.max
def depth[A](tree: Tree[A]): Int = tree match {
  case Empty => 0
  case Node(_, left, right) => 1 + max(depth(left), depth(right))
}

// Exiting paste mode, now interpreting.

import scala.math.max
depth: [A](tree: Tree[A])Int

scala> depth(Node("foo", Node("bar", Empty, Empty), Empty))
res5: Int = 2

Scala donne typiquement au développeur un tableau déconcertant d'options à choisir dans la façon d'organiser la fonctionnalité qui fonctionne sur ADTs. Je peux penser à quatre approches de base.

1) vous pouvez en faire une fonction autonome externe au trait:

sealed trait Tree[+A]
case object Empty extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

object Tree {
  def depth[A](tree: Tree[A]): Int = tree match {
    case Empty => 0
    case Node(_, left, right) => 1 + max(depth(left), depth(right))
  }
}

cela peut être agréable si vous voulez que votre API se sente plus fonctionnel que orienté objet, ou si votre opération pourrait produire une instance de votre ADT à partir d'autres données. compagnon de l'objet est souvent un lieu naturel pour mettre de telles méthodes.

2) Vous pouvez en faire une méthode concrète du caractère lui-même:

sealed trait Tree[+A] {
  def depth: Int = this match {
    case Empty => 0
    case Node(_, left, right) => 1 + max(left.depth, right.depth)
  }
}
case object Empty extends Tree[Nothing]
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]

ceci est particulièrement utile si votre opération peut être définie purement en termes d'autres méthodes de la trait, auquel cas vous n'aurez probablement pas explicitement utiliser match.

3) vous peut en faire une méthode abstraite du trait avec des implémentations concrètes dans les sous-types (évitant la nécessité d'utiliser match):

sealed trait Tree[+A] {
  def depth: Int
}
case object Empty extends Tree[Nothing] {
  val depth = 0
} 
case class Node[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A] {
  def depth = 1 + max(left.depth, right.depth)
}

ceci est très similaire à l'approche traditionnelle du polymorphisme orienté objet. Il me semble naturel de définir les opérations de bas niveau de la trait, avec des fonctionnalités plus riches définies en termes de ces opérations dans le trait lui-même. Il est également plus approprié de travailler avec des traits qui ne sont pas sealed.

4) ou, dans le cas où vous voulez ajouter une méthode à un ADT dont la source est externe à votre projet, vous pouvez utiliser une conversion implicite à un nouveau type qui a la méthode:

// assuming Tree defined elsewhere
implicit class TreeWithDepth[A](tree: Tree[A]) {
  def depth: Int = tree match {
    case Empty => 0
    case Node(_, left, right) => 1 + max(left.depth, right.depth)
  }
}

C'est un moyen particulièrement pratique pour améliorer les types définis dans le code que vous ne contrôlez pas, pour prendre en compte le comportement auxiliaire hors de vos types afin qu'ils puissent se concentrer sur le comportement de base, ou pour faciliter de polymorphisme ad hoc.

la méthode 1 est fonction qui prend un Tree et fonctionne comme le premier exemple. Méthodes 2-4 sont toutes les opérations sur un Tree:

scala> Node("foo", Node("bar", Empty, Empty), Empty).depth
res8: Int = 2