Algebraic data types outside of functional languages?

Question

Which languages that are not solely functional have algebraic data types (or something similar) and pattern matching? I'm also interested in multi-paradigm languages - I know that Ocaml and F# are ML dialects with OO added, so they inherit the algebraic data types from ML.

They can be kind-of emulated using enums and unions (as in C, C++, ...more?), but this soon gets cumbersome and ugly, and the compiler can't warn you if you forget a case in your pattern matching or (much more propable, and much more dangerous) when accessing the union "in wrong ways", i.e. you ask for a field of a Left value when it's actually a Right value (what you get then is a meaningless reinterpretation of the bits that happen to be there).

I've heard that Pascal has something like tagged unions and the Cyclone language supports tagged unions, too. Wikipedia also mentions Ada and Algol. Any other languages?

(In case you never heard of algebraic data types, you can read an Answer to "What is 'Pattern Matching' in functional languages?" for an excellent introduction).

Answer 1

In Scala, you'd usually use case classes to emulate the algebraic data types as found in true-blue functional languages like ML and Haskell.

For example, following F# code (taken from here):

type Shape =
| Circle of float
| EquilateralTriangle of double
| Square of double
| Rectangle of double * double

let area myShape =
    match myShape with
    | Circle radius -> Math.PI * radius * radius
    | EquilateralTriangle s -> (sqrt 3.0) / 4.0 * s * s
    | Square s -> s * s
    | Rectangle (h, w) -> h * w

can be roughly translated to Scala as follows:

sealed abstract class Shape
case class Circle(radius: Float) extends Shape
case class EquilateralTriangle(side: Double) extends Shape
case class Square(side: Double) extends Shape
case class Rectangle(height: Double, width: Double) extends Shape

def area(myShape: Shape) = myShape match {
  case Circle(radius) => math.Pi * radius * radius
  case EquilateralTriangle(s) => math.sqrt(3.0) / 4.0 * s * s
  case Square(s) => s * s
  case Rectangle(h, w) => h * w
}

The sealed keyword above is used to have the compiler warn you in case you forget any case in the match expression.

Answer 2

In Mozilla's Rust language, algebraic data types and pattern matching are important concepts. The syntax is also fairly nice. Consider the following simple program:

static PI: f32 = 3.14159;

enum Shape {
    Circle(f32),
    Rectangle(f32, f32),
    Point
}

fn area(shape: Shape) -> f32 {
    match shape {
        Point                    => 0.0
        Circle(radius)           => PI * radius * radius,
        Rectangle(width, height) => width * height,
    }
}

fn main() {
    let radius = 4.0;
    let circle = Circle(radius);
    let area = area(circle);
    println!("The area of a circle with radius {} is {}", radius, area);
}

Answer 3

The logic programming language Mercury calls them discriminated unions. The constraint language CHR, embedded in Prolog, has them too, but there they are entirely optional, general Prolog terms being the default type.

Answer 4

Erlang has a dynamic type system, so it doesn't provide any of the guarantees you cite, but Erlang code does tend to look like the product of an algebraic type system:

count([]) -> 0;
count([H|T]) -> 1 + count(T).

length({rect, X, Y}) -> math:sqrt(X*X + Y*Y);
length({polar, R, _A}) -> R.

Answer 5

I think that Whiley would qualify. Whiley has record types (.ie. product) and type unions (i.e. sum), hence.

Matching seems to be possible on type only, i.e. you can ask if a value with union type is one of the types in the union and then the value is "re-typed" and you can access the fields of the type you checked for.