Написание алгебраического типа данных в Scala

Определение ADT

В «объектно-функциональной» модели Scala вы определяете trait, который представляет АТД и все его параметры. Затем для каждого из ваших случаев вы определяете либо case class, либо case object. Параметры типа и значения рассматриваются как аргументы конструктора класса. Как правило, вы делаете трейт sealed, чтобы ничто за пределами текущего файла не могло добавлять наблюдения.

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]

Затем вы можете сделать:

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

Немного раздражает, что нам приходится создавать целую кучу новых экземпляров Empty, когда этот класс не несет данных. В Scala обычной практикой является замена case class без аргументов, например Empty, на case object, хотя в данном случае это немного сложно, потому что case object — это синглтон, а нам нужен Empty для каждого типа дерева.

К счастью (или нет, в зависимости от того, кого вы спросите), с ковариационной аннотацией вы можете иметь одно действие case object Empty в качестве пустого Tree типа Nothing, который является универсальным подтипом Scala. Из-за ковариации этот Empty теперь является подтипом Tree[A] для всех возможных 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]

Затем вы получаете более чистый синтаксис:

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

Именно так стандартная библиотека Scala Nil работает в отношении List.

Работа с ADT

Чтобы использовать новый ADT, в Scala принято определять рекурсивные функции, которые используют ключевое слово match для его деконструкции. Видеть:

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, как правило, предоставляет разработчику ошеломляющий набор возможностей для выбора в том, как организовать функциональность, работающую с АТД. Я могу назвать четыре основных подхода.

1) Вы можете сделать это отдельной функцией, внешней по отношению к трейту:

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))
  }
}

Это может быть удобно, если вы хотите, чтобы ваш API выглядел более функциональным, чем объектно-ориентированным, или если ваша операция может создавать экземпляр вашего ADT из других данных. сопутствующий объект часто является естественным место для размещения таких методов.

2) Вы можете сделать это конкретным методом самой черты:

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]

Это особенно полезно, если ваша операция может быть определена исключительно с точки зрения других методов trait, и в этом случае вы, вероятно, не будете явно использовать match.

3) Вы можете сделать его абстрактным методом трейта с конкретными реализациями в подтипах (избавляясь от необходимости использовать 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)
}

Это больше всего похоже на подход традиционного объектно-ориентированного полиморфизма. Мне кажется естественным определять низкоуровневые операции trait, а более богатые функциональные возможности определяются с точки зрения этих операций в самом trait. Это также наиболее уместно при работе с чертами, которые не являются sealed.

4) Или, если вы хотите добавить метод в ADT, источник которого является внешним по отношению к вашему проекту, вы можете использовать неявное преобразование в новый тип, который имеет метод:

// 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)
  }
}

Это особенно удобный способ улучшить типы, определенные в коде, который вы не контролируете, выделить вспомогательное поведение из ваших типов, чтобы они могли быть сосредоточены на основном поведении, или упростить специальный полиморфизм.

Метод 1 — это функция, которая принимает Tree и работает так же, как в первом примере. Методы 2-4 — это все операции над Tree:

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

Начиная с Scala 3 и нового объединения тип, это станет возможным:

type Tree[A] = Node[A] | Empty.type
case object Empty
case class Node[A](value: A, left: Tree[A], right: Tree[A])

который вы можете создать как таковой:

val empty: Tree[String] = Empty
val tree:  Tree[String] = Node("foo", Node("bar", Empty, Empty), Empty)

и использовать как часть конкретного примера:

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

depth(tree)  // 2
depth(empty) // 0