haskell - Writing Algebraic Data Type in Scala

Question

In Haskell, I can define a Tree:

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

How could I write this in Scala?

I'm not sure how to keep the type parameter [A] in Scala for Node to match Tree's type, a.

Answer 1

Defining an ADT

In Scala's "object-functional" model, you define a trait that represents the ADT and all of its parameters. Then for each of your cases, you define either a case class or a case object. Type and value parameters are treated as arguments to the class constructor. Typically, you make the trait sealed so that nothing outside the current file can add cases.

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]

Then you can do:

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

It's kind of annoying that we have to create a whole bunch of new Empty instances, when that class carries no data. In Scala, it's common practice to replace a zero-argument case class, like Empty, with a case object, although in this case, it's a little tricky, because a case object is a singleton, but we need an Empty for every type of tree.

Fortunately (or not, depending on who you ask), with a covariance annotation, you can have one case object Empty act as the empty Tree of type Nothing, which is Scala's universal subtype. Due to covariance, this Empty is now a subtype of Tree[A] for all possible 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]

Then you get the cleaner syntax:

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

This is, in fact, how Scala's standard library Nil works, with respect to List.

Operating on an ADT

To use the new ADT, it's common in Scala to define recursive functions that employ the match keyword to deconstruct it. See:

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 characteristically gives the developer a bewildering array of options to choose from in how to organize functionality that operates on ADTs. I can think of four basic approaches.

1) You can make it a standalone function external to the 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))
  }
}

This might be nice if you want your API to feel more functional than object-oriented, or if your operation might product an instance of your ADT from other data. The companion object is often a natural place to put such methods.

2) You can make it a concrete method of the trait itself:

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]

This is particularly useful if your operation can be defined purely in terms of other methods of the trait, in which case you probably won't explicitly use match.

3) You can make it an abstract method of the trait with concrete implementations in the subtypes (obviating the need to use 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)
}

This is most similar to the approach traditional object-oriented polymorphism. It feels natural to me when defining the low-level operations of the trait, with richer functionality defined in terms of these operations in the trait itself. It's also most appropriate when working with traits that aren't sealed.

4) Or, in the case you want to add a method to an ADT whose source is external to your project, you could use an implicit conversion to a new type that has the method:

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

This is a particularly handy way to enhance types defined in code you don't control, to factor auxiliary behavior out of your types so that they can be focused on core behavior, or to facilitate of ad hoc polymorphism.

Method 1 is a function that takes a Tree and works like the first example. Methods 2-4 are all operations on a Tree:

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