Escribir tipo de datos algebraicos en Scala

haskell type-parameter

Question

En Haskell, puedo definir un Tree :

data Tree a = Empty | Node a (Tree a) (Tree a)

¿Cómo podría escribir esto en Scala?

No estoy seguro de cómo mantener el parámetro de tipo [A] en Scala para que el Node coincida con el tipo de Tree , a .

Answer 1

Definiendo un ADT

En el modelo "objeto-funcional" de Scala, usted define un trait que representa el ADT y todos sus parámetros. Luego, para cada uno de sus casos, defina una case class o un case object . Los parámetros de tipo y valor se tratan como argumentos para el constructor de clase. Por lo general, haces el rasgo sealed para que nada fuera del archivo actual pueda agregar casos.

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]

Entonces puedes hacer:

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

Es un poco molesto que tengamos que crear un montón de nuevas instancias Empty , cuando esa clase no contiene datos. En Scala, es una práctica común reemplazar una case class argumento cero, como Empty , con un case object , aunque en este caso, es un poco complicado, porque un case object es un singleton, pero necesitamos un Empty para cada tipo de árbol.

Afortunadamente (o no, dependiendo de a quién le pregunte), con una anotación de covarianza, puede tener un case object Empty como el Tree vacío de tipo Nothing , que es el subtipo universal de Scala. Debido a la covarianza, este Empty ahora es un subtipo de Tree[A] para todos los posibles 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]

Entonces obtienes la sintaxis más limpia:

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

Esto es, de hecho, cómo funciona la biblioteca estándar de Scala, Nil , con respecto a List .

Operando en un ADT

Para usar el nuevo ADT, es común en Scala definir las funciones recursivas que emplean la palabra clave de match para deconstruirlo. Ver:

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 ofrece de manera característica al desarrollador una variedad desconcertante de opciones para elegir en cómo organizar la funcionalidad que opera en ADT. Puedo pensar en cuatro enfoques básicos.

1) Puede convertirlo en una función independiente externa al rasgo:

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

Esto podría ser útil si desea que su API se sienta más funcional que orientada a objetos, o si su operación puede generar una instancia de su ADT a partir de otros datos. El objeto complementario es a menudo un lugar natural para poner tales métodos.

2) Puedes convertirlo en un método concreto del rasgo en sí mismo:

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]

Esto es particularmente útil si su operación puede definirse puramente en términos de otros métodos del trait , en cuyo caso probablemente no use explícitamente la match .

3) Puede convertirlo en un método abstracto del rasgo con implementaciones concretas en los subtipos (obviando la necesidad de usar 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)
}

Esto es muy similar al enfoque del polimorfismo tradicional orientado a objetos. Me parece natural a la hora de definir las operaciones de bajo nivel del trait , con una funcionalidad más rica definida en términos de estas operaciones en el trait mismo. También es más apropiado cuando se trabaja con rasgos que no están sealed .

4) O, en el caso de que desee agregar un método a un ADT cuya fuente sea externa a su proyecto, podría usar una conversión implícita a un nuevo tipo que tenga el método:

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

Esta es una forma particularmente útil para mejorar los tipos definidos en el código que no controla, para factorizar el comportamiento auxiliar de sus tipos, de modo que puedan centrarse en el comportamiento del núcleo o facilitar el polimorfismo ad hoc .

El Método 1 es una función que toma un Tree y funciona como el primer ejemplo. Los métodos 2-4 son todas operaciones en un Tree :

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