THC Science

This article compares the syntax for defining and instantiating an algebraic data type (ADT), sometimes also referred to as a tagged union, in various programming languages.

Examples of algebraic data types[edit]

Ceylon[edit]

In Ceylon, an ADT may be defined with:^[1]

abstract class Tree()
    of empty | Node {}

object empty
    extends Tree() {}

final class Node(shared Integer val, shared Tree left, shared Tree right)
    extends Tree() {}

And instantiated as:

value myTree = Node(42, Node(0, empty, empty), empty);

Clean[edit]

In Clean, an ADT may be defined with:^[2]

:: Tree
  = Empty
  | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Coq[edit]

In Coq, an ADT may be defined with:^[3]

Inductive tree : Type :=
| empty : tree
| node : nat -> tree -> tree -> tree.

And instantiated as:

Definition my_tree := node 42 (node 0 empty empty) empty.

C++[edit]

In C++, an ADT may be defined with:^[4]

struct Empty final {};

struct Node final {
    int value;
    std::unique_ptr<std::variant<Empty, Node>> left;
    std::unique_ptr<std::variant<Empty, Node>> right;
};

using Tree = std::variant<Empty, Node>;

And instantiated as:

Tree myTree { Node{
    42,
    std::make_unique<Tree>(Node{
        0,
        std::make_unique<Tree>(),
        std::make_unique<Tree>()
    }),
    std::make_unique<Tree>()
} };

Dart[edit]

In Dart, an ADT may be defined with:^[5]

sealed class Tree {}

final class Empty extends Tree {}

final class Node extends Tree {
  final int value;
  final Tree left, right;

  Node(this.value, this.left, this.right);
}

And instantiated as:

final myTree = Node(42, Node(0, Empty(), Empty()), Empty());

Elm[edit]

In Elm, an ADT may be defined with:^[6]

type Tree
  = Empty
  | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

F#[edit]

In F#, an ADT may be defined with:^[7]

type Tree =
    | Empty
    | Node of int * Tree * Tree

And instantiated as:

let myTree = Node(42, Node(0, Empty, Empty), Empty)

F*[edit]

In F*, an ADT may be defined with:^[8]

type tree =
  | Empty : tree
  | Node : value:nat -> left:tree -> right:tree -> tree

And instantiated as:

let my_tree = Node 42 (Node 0 Empty Empty) Empty

Free Pascal[edit]

In Free Pascal (in standard ISO Pascal mode^[9]), an ADT may be defined with variant records:^[10]

{$mode ISO}
program MakeTree;

type TreeKind = (Empty, Node);
  PTree = ^Tree;
  Tree = record
    case Kind: TreeKind of
      Empty: ();
      Node: (
        Value: Integer;
        Left, Right: PTree;
      );
  end;

And instantiated as:

var MyTree: PTree;

begin new(MyTree, Node);
  with MyTree^ do begin
    Value := 42;
    new(Left,  Node);
    with Left^ do begin
      Value := 0;
      new(Left,  Empty);
      new(Right, Empty);
    end;
    new(Right, Empty);
  end;
end.

Haskell[edit]

In Haskell, an ADT may be defined with:^[11]

data Tree
    = Empty
    | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Haxe[edit]

In Haxe, an ADT may be defined with:^[12]

enum Tree {
	Empty;
	Node(value:Int, left:Tree, right:Tree);
}

And instantiated as:

var myTree = Node(42, Node(0, Empty, Empty), Empty);

Hope[edit]

In Hope, an ADT may be defined with:^[13]

data tree == empty
          ++ node (num # tree # tree);

And instantiated as:

dec mytree : tree;
--- mytree <= node (42, node (0, empty, empty), empty);

Idris[edit]

In Idris, an ADT may be defined with:^[14]

data Tree
    = Empty
    | Node Nat Tree Tree

And instantiated as:

myTree : Tree
myTree = Node 42 (Node 0 Empty Empty) Empty

Java[edit]

In Java, an ADT may be defined with:^[15]

sealed interface Tree {
    record Empty() implements Tree {}
    record Node(int value, Tree left, Tree right) implements Tree {}
}

And instantiated as:

var myTree = new Tree.Node(
    42,
    new Tree.Node(0, new Tree.Empty(), new Tree.Empty()),
    new Tree.Empty()
);

Julia[edit]

In Julia, an ADT may be defined with:^[16]

struct Empty
end

struct Node
    value::Int
    left::Union{Empty, Node}
    right::Union{Empty, Node}
end

const Tree = Union{Empty, Node}

And instantiated as:

mytree = Node(42, Node(0, Empty(), Empty()), Empty())

Kotlin[edit]

In Kotlin, an ADT may be defined with:^[17]

sealed class Tree {
    object Empty : Tree()
    data class Node(val value: Int, val left: Tree, val right: Tree) : Tree()
}

And instantiated as:

val myTree = Tree.Node(
    42,
    Tree.Node(0, Tree.Empty, Tree.Empty),
    Tree.Empty,
)

Limbo[edit]

In Limbo, an ADT may be defined with:^[18]

Tree: adt {
	pick {
	Empty =>
	Node =>
		value: int;
		left: ref Tree;
		right: ref Tree;
	}
};

And instantiated as:

myTree := ref Tree.Node(
	42,
	ref Tree.Node(0, ref Tree.Empty(), ref Tree.Empty()),
	ref Tree.Empty()
);

Mercury[edit]

In Mercury, an ADT may be defined with:^[19]

:- type tree
    --->    empty
    ;       node(int, tree, tree).

And instantiated as:

:- func my_tree = tree.
my_tree = node(42, node(0, empty, empty), empty).

Miranda[edit]

In Miranda, an ADT may be defined with:^[20]

tree ::=
    Empty
    | Node num tree tree

And instantiated as:

my_tree = Node 42 (Node 0 Empty Empty) Empty

Nemerle[edit]

In Nemerle, an ADT may be defined with:^[21]

variant Tree
{
    | Empty
    | Node {
        value: int;
        left: Tree;
        right: Tree;
    }
}

And instantiated as:

def myTree = Tree.Node(
    42,
    Tree.Node(0, Tree.Empty(), Tree.Empty()),
    Tree.Empty(),
);

Nim[edit]

In Nim, an ADT may be defined with:^[22]

type
  TreeKind = enum
    tkEmpty
    tkNode

  Tree = ref TreeObj

  TreeObj = object
    case kind: TreeKind
    of tkEmpty:
      discard
    of tkNode:
      value: int
      left, right: Tree

And instantiated as:

let myTree = Tree(kind: tkNode, value: 42,
                  left: Tree(kind: tkNode, value: 0,
                             left: Tree(kind: tkEmpty),
                             right: Tree(kind: tkEmpty)),
                  right: Tree(kind: tkEmpty))

OCaml[edit]

In OCaml, an ADT may be defined with:^[23]

type tree =
  | Empty
  | Node of int * tree * tree

And instantiated as:

let my_tree = Node (42, Node (0, Empty, Empty), Empty)

Opa[edit]

In Opa, an ADT may be defined with:^[24]

type tree =
  { empty } or
  { node, int value, tree left, tree right }

And instantiated as:

my_tree = {
  node,
  value: 42,
  left: {
    node,
    value: 0,
    left: { empty },
    right: { empty }
  },
  right: { empty }
}

OpenCog[edit]

In OpenCog, an ADT may be defined with:^[25]

PureScript[edit]

In PureScript, an ADT may be defined with:^[26]

data Tree
  = Empty
  | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Python[edit]

In Python, an ADT may be defined with:^[27]

from __future__ import annotations
from dataclasses import dataclass

@dataclass
class Empty:
    pass

@dataclass
class Node:
    value: int
    left: Tree
    right: Tree

Tree = Empty | Node

And instantiated as:

my_tree = Node(42, Node(0, Empty(), Empty()), Empty())

Racket[edit]

In Typed Racket, an ADT may be defined with:^[28]

(struct Empty ())
(struct Node ([value : Integer] [left : Tree] [right : Tree]))
(define-type Tree (U Empty Node))

And instantiated as:

(define my-tree (Node 42 (Node 0 (Empty) (Empty)) (Empty)))

Reason[edit]

In Reason, an ADT may be defined with:^[29]

type Tree =
  | Empty
  | Node(int, Tree, Tree);

And instantiated as:

let myTree = Node(42, Node(0, Empty, Empty), Empty);

ReScript[edit]

In ReScript, an ADT may be defined with:^[30]

type rec Tree =
  | Empty
  | Node(int, Tree, Tree)

And instantiated as:

let myTree = Node(42, Node(0, Empty, Empty), Empty)

Rust[edit]

In Rust, an ADT may be defined with:^[31]

enum Tree {
    Empty,
    Node(i32, Box<Tree>, Box<Tree>),
}

And instantiated as:

let my_tree = Tree::Node(
    42,
    Box::new(Tree::Node(0, Box::new(Tree::Empty), Box::new(Tree::Empty)),
    Box::new(Tree::Empty),
);

Scala[edit]

Scala 2[edit]

In Scala 2, an ADT may be defined with:^{[citation needed]}

sealed abstract class Tree extends Product with Serializable

object Tree {
  final case object Empty extends Tree
  final case class Node(value: Int, left: Tree, right: Tree)
      extends Tree
}

And instantiated as:

val myTree = Tree.Node(
  42,
  Tree.Node(0, Tree.Empty, Tree.Empty),
  Tree.Empty
)

Scala 3[edit]

In Scala 3, an ADT may be defined with:^[32]

enum Tree:
  case Empty
  case Node(value: Int, left: Tree, right: Tree)

And instantiated as:

val myTree = Tree.Node(
  42,
  Tree.Node(0, Tree.Empty, Tree.Empty),
  Tree.Empty
)

Standard ML[edit]

In Standard ML, an ADT may be defined with:^[33]

datatype tree =
    EMPTY
  | NODE of int * tree * tree

And instantiated as:

val myTree = NODE (42, NODE (0, EMPTY, EMPTY), EMPTY)

Swift[edit]

In Swift, an ADT may be defined with:^[34]

enum Tree {
    case empty
    indirect case node(Int, Tree, Tree)
}

And instantiated as:

let myTree: Tree = .node(42, .node(0, .empty, .empty), .empty)

TypeScript[edit]

In TypeScript, an ADT may be defined with:^[35]

type Tree =
  | { kind: "empty" }
  | { kind: "node"; value: number; left: Tree; right: Tree };

And instantiated as:

const myTree: Tree = {
  kind: "node",
  value: 42,
  left: {
    kind: "node",
    value: 0,
    left: { kind: "empty" },
    right: { kind: "empty" },
  },
  right: { kind: "empty" },
};

Visual Prolog[edit]

In Visual Prolog, an ADT may be defined with:^[36]

domains
    tree = empty; node(integer, tree, tree).

And instantiated as:

constants
    my_tree : tree = node(42, node(0, empty, empty), empty).

References[edit]

^ "Eclipse Ceylon: Union, intersection, and enumerated types". ceylon-lang.org. Archived from the original on 2022-12-26. Retrieved 2021-11-29.
^ "Clean 2.2 Ref Man". clean.cs.ru.nl. Retrieved 2021-11-29.
^ "Inductive types and recursive functions — Coq 8.14.1 documentation". coq.inria.fr. Retrieved 2021-11-30.
^ "std::variant - cppreference.com". en.cppreference.com. Retrieved 2021-12-04.
^ "Patterns". dart.dev. Retrieved 2023-09-28.
^ "Custom Types · An Introduction to Elm". guide.elm-lang.org. Retrieved 2021-11-29.
^ cartermp. "Discriminated Unions - F#". docs.microsoft.com. Retrieved 2021-11-29.
^ "Inductive types and pattern matching — Proof-Oriented Programming in F* documentation". www.fstar-lang.org. Retrieved 2021-12-06.
^ "Mode iso". wiki.freepascal.org. Retrieved 2024-05-26.
^ "Record types". www.freepascal.org. Retrieved 2021-12-05.
^ "4 Declarations and Bindings". www.haskell.org. Retrieved 2021-12-07.
^ "Enum Instance". Haxe - The Cross-platform Toolkit. Retrieved 2021-11-29.
^ "Defining your own data types". 2011-08-10. Archived from the original on 2011-08-10. Retrieved 2021-12-03.
^ "Types and Functions — Idris2 0.0 documentation". idris2.readthedocs.io. Retrieved 2021-11-30.
^ "JEP 409: Sealed Classes". openjdk.java.net. Retrieved 2021-12-05.
^ "Types · The Julia Language". docs.julialang.org. Retrieved 2021-12-03.
^ "Sealed classes | Kotlin". Kotlin Help. Retrieved 2021-11-29.
^ Stanley-Marbell, Phillip (2003). Inferno Programming with Limbo. Wiley. pp. 67–71. ISBN 978-0470843529.
^ "The Mercury Language Reference Manual: Discriminated unions". www.mercurylang.org. Retrieved 2021-12-07.
^ "An Overview of Miranda". www.cs.kent.ac.uk. Retrieved 2021-12-04.
^ "Basic Variants · rsdn/nemerle Wiki". GitHub. Retrieved 2021-12-03.
^ "Nim Manual". nim-lang.org. Retrieved 2021-11-29.
^ "OCaml - The OCaml language". ocaml.org. Retrieved 2021-12-07.
^ "The type system · MLstate/opalang Wiki". GitHub. Retrieved 2021-12-07.
^ "Type constructor - OpenCog". wiki.opencog.org. Retrieved 2021-12-07.
^ purescript/documentation, PureScript, 2021-11-24, retrieved 2021-11-30
^ PEP 484 – Type Hints, Python
^ "2 Beginning Typed Racket". docs.racket-lang.org. Retrieved 2021-12-04.
^ "Variants · Reason". reasonml.github.io. Retrieved 2021-11-30.
^ "Variant | ReScript Language Manual". ReScript Documentation. Retrieved 2021-11-30.
^ "enum - Rust". doc.rust-lang.org. Retrieved 2021-11-29.
^ "Algebraic Data Types". Scala Documentation. Retrieved 2021-11-29.
^ "Defining datatypes". homepages.inf.ed.ac.uk. Retrieved 2021-12-01.
^ "Enumerations — The Swift Programming Language (Swift 5.5)". docs.swift.org. Retrieved 2021-11-29.
^ "Documentation - TypeScript for Functional Programmers". www.typescriptlang.org. Retrieved 2021-11-29.
^ "Language Reference/Domains - wiki.visual-prolog.com". wiki.visual-prolog.com. Retrieved 2021-12-07.

[1] "Eclipse Ceylon: Union, intersection, and enumerated types". ceylon-lang.org. Archived from the original on 2022-12-26. Retrieved 2021-11-29.

[2] "Clean 2.2 Ref Man". clean.cs.ru.nl. Retrieved 2021-11-29.

[3] "Inductive types and recursive functions — Coq 8.14.1 documentation". coq.inria.fr. Retrieved 2021-11-30.

[4] "std::variant - cppreference.com". en.cppreference.com. Retrieved 2021-12-04.

[5] "Patterns". dart.dev. Retrieved 2023-09-28.

[6] "Custom Types · An Introduction to Elm". guide.elm-lang.org. Retrieved 2021-11-29.

[7] rtermp. "Discriminated Unions - F#". docs.microsoft.com. Retrieved 2021-11-29.

[8] "Inductive types and pattern matching — Proof-Oriented Programming in F* documentation". www.fstar-lang.org. Retrieved 2021-12-06.

[9] "Mode iso". wiki.freepascal.org. Retrieved 2024-05-26.

[10] "Record types". www.freepascal.org. Retrieved 2021-12-05.

[11] "4 Declarations and Bindings". www.haskell.org. Retrieved 2021-12-07.

[12] "Enum Instance". Haxe - The Cross-platform Toolkit. Retrieved 2021-11-29.

[13] "Defining your own data types". 2011-08-10. Archived from the original on 2011-08-10. Retrieved 2021-12-03.

[14] "Types and Functions — Idris2 0.0 documentation". idris2.readthedocs.io. Retrieved 2021-11-30.

[15] "JEP 409: Sealed Classes". openjdk.java.net. Retrieved 2021-12-05.

[16] "Types · The Julia Language". docs.julialang.org. Retrieved 2021-12-03.

[17] "Sealed classes | Kotlin". Kotlin Help. Retrieved 2021-11-29.

[18] Stanley-Marbell, Phillip (2003). Inferno Programming with Limbo. Wiley. pp. 67–71. ISBN 978-0470843529.

[19] "The Mercury Language Reference Manual: Discriminated unions". www.mercurylang.org. Retrieved 2021-12-07.

[20] "An Overview of Miranda". www.cs.kent.ac.uk. Retrieved 2021-12-04.

[21] "Basic Variants · rsdn/nemerle Wiki". GitHub. Retrieved 2021-12-03.

[22] "Nim Manual". nim-lang.org. Retrieved 2021-11-29.

[23] "OCaml - The OCaml language". ocaml.org. Retrieved 2021-12-07.

[24] "The type system · MLstate/opalang Wiki". GitHub. Retrieved 2021-12-07.

[25] "Type constructor - OpenCog". wiki.opencog.org. Retrieved 2021-12-07.

[26] purescript/documentation, PureScript, 2021-11-24, retrieved 2021-11-30

[27] PEP 484 – Type Hints, Python

[28] "2 Beginning Typed Racket". docs.racket-lang.org. Retrieved 2021-12-04.

[29] "Variants · Reason". reasonml.github.io. Retrieved 2021-11-30.

[30] "Variant | ReScript Language Manual". ReScript Documentation. Retrieved 2021-11-30.

[31] "enum - Rust". doc.rust-lang.org. Retrieved 2021-11-29.

[32] "Algebraic Data Types". Scala Documentation. Retrieved 2021-11-29.

[33] "Defining datatypes". homepages.inf.ed.ac.uk. Retrieved 2021-12-01.

[34] "Enumerations — The Swift Programming Language (Swift 5.5)". docs.swift.org. Retrieved 2021-11-29.

[35] "Documentation - TypeScript for Functional Programmers". www.typescriptlang.org. Retrieved 2021-11-29.

[36] "Language Reference/Domains - wiki.visual-prolog.com". wiki.visual-prolog.com. Retrieved 2021-12-07.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]