Algebraic data types: Difference between revisions

</pre>

=={{header|Scala}}==

{{trans|Haskell}}

Algebraic data types are implemented in Scala through the combination of a number of

different features, to ensure principles of Object Oriented Programming.

The main type

is usually defined as a <code>sealed abstract class</code>, which ensures it can't be

instantiated, and guarantees that it can't be expanded outside the file it was defined

at. This last feature is used so the compiler can verify that the pattern matching is

complete, or warn when there are missing cases. It can be ommitted if preferred.

Each subtype is defined either as a <code>case object</code>, for non-paremeterized types,

or <code>case class</code>, for parameterized types, all extending the main type. The

<code>case</code> keyword is not required, but, when used, it provides a number of default

methods which ensure they can be used without any further definitions.

The most important of those default methods for the purpose of algebraic data types is the

''extractor'', a method called either <code>unapply</code> or <code>unapplySeq</code>, and

which returns an <code>Option</code> containing the deconstructed parameters, or <code>None</code>

if the passed object can't be deconstructed by this method. Scala uses the extractors to

implement pattern matching without exposing the internal representation of the data.

This specific task is made much harder than necessary because Scala doesn't have a variant

ordering class. Given that limitation, one has to either give up on a singleton object representing

the empty tree, or give up on parameterizing the tree itself.

The solution below, uses the latter approach. The algebraic data types are members of a <code>RedBlackTree</code>

class, which, itself, receives a type parameter for the keys of the tree, and an implicit

parameter for an <code>Ordering</code> for that type. To use the tree it is thus necessary

to instantiate an object of type <code>RedBlackTree</code>, and then reference the members

of that object.

<lang scala>class RedBlackTree[A](implicit ord: Ordering[A]) {

sealed abstract class Color

case object R extends Color

case object B extends Color

sealed abstract class Tree {

def insert(x: A): Tree = ins(x) match {

case T(_, a, y, b) => T(B, a, y, b)

case E => E

}

def ins(x: A): Tree

}

case object E extends Tree {

override def ins(x: A): Tree = T(R, E, x, E)

}

case class T(c: Color, left: Tree, a: A, right: Tree) extends Tree {

private def balance: Tree = (c, left, a, right) match {

case (B, T(R, T(R, a, x, b), y, c), z, d ) => T(R, T(B, a, x, b), y, T(B, c, z, d))

case (B, T(R, a, x, T(R, b, y, c)), z, d ) => T(R, T(B, a, x, b), y, T(B, c, z, d))

case (B, a, x, T(R, T(R, b, y, c), z, d )) => T(R, T(B, a, x, b), y, T(B, c, z, d))

case (B, a, x, T(R, b, y, T(R, c, z, d))) => T(R, T(B, a, x, b), y, T(B, c, z, d))

case _ => this

}

override def ins(x: A): Tree = ord.compare(x, a) match {

case -1 => T(c, left ins x, a, right ).balance

case 1 => T(c, left, a, right ins x).balance

case 0 => this

}

}

}</lang>

Usage example:

<pre>

scala> val rbt = new RedBlackTree[Int]

rbt: RedBlackTree[Int] = RedBlackTree@17dfcf1

scala> import rbt._

import rbt._

scala> List.range(1, 17).foldLeft(E: Tree)(_ insert _)

res5: rbt.Tree = T(B,T(B,T(B,T(B,E,1,E),2,T(B,E,3,E)),4,T(B,T(B,E,5,E),6,T(B,E,7,E))),8,T(B,T(B,T(B,E,9,E),10,T(B,E,11,E

)),12,T(B,T(B,E,13,E),14,T(B,E,15,T(R,E,16,E)))))