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

Ответ 1

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

В Scala "объектно-функциональной" модели вы определяете trait, который представляет ADT и все его параметры. Затем для каждого из ваших случаев вы определяете либо 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, хотя в этом случае это немного сложно, потому что a 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 позволяет разработчику сбивать с толку множество опций, чтобы выбрать, как организовать функциональность, которая работает с ADT. Я могу думать о четырех основных подходах.

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