Comparison of programming languages (algebraic data type)

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

ATS

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

datatype tree =
	| Empty of () 
	| Node of (int, tree, tree)

And instantiated as:

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

Additionally in ATS dataviewtypes are the linear type version of ADTs for the purpose of providing in the setting of manual memory management with the convenience of pattern matching.^[3] An example program might look like:

(* Alternatively one can use the datavtype keyword *)
dataviewtype int_or_string_vt (bool) =
	| String_vt (true) of string
	| Int_vt (false) of int

(* Alternatively one can use the vtypedef keyword *)
viewtypedef Int_or_String_vt = [b: bool] int_or_string_vt b

fn print_int_or_string (i_or_s: Int_or_String_vt): void =
	case+ i_or_s of
	(* ~ indicates i_or_s will be implicitly freed in this case *)
	| ~String_vt(s) => println!(s)
	(* @ indicates i_or_s must be explicitly freed in this case *)
	| @Int_vt(i) => begin
			$extfcall(void, "fprintf", stdout_ref, "%d\n", i);
			free@i_or_s;
		end

implement main0 (): void = let
	val string_hello_world = String_vt "Hello, world!"
	val int_0 = Int_vt 0
in
	print_int_or_string string_hello_world;
	print_int_or_string int_0;
	(* which prints:
	Hello, world!
	0
	*)
end

Ceylon

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

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

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

:: Tree
  = Empty
  | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Coq

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

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

And instantiated as:

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

C++

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

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

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

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

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

type Tree
  = Empty
  | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

F#

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

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

And instantiated as:

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

F*

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

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

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

{$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

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

data Tree
    = Empty
    | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Haxe

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

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

And instantiated as:

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

Hope

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

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

And instantiated as:

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

Idris

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

data Tree
    = Empty
    | Node Nat Tree Tree

And instantiated as:

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

Java

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

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

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

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

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

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

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

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

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

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

And instantiated as:

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

Miranda

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

tree ::=
    Empty
    | Node num tree tree

And instantiated as:

my_tree = Node 42 (Node 0 Empty Empty) Empty

Nemerle

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

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

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

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

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

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

And instantiated as:

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

Opa

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

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

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

PureScript

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

data Tree
  = Empty
  | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Python

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

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

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

(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

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

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

And instantiated as:

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

ReScript

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

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

And instantiated as:

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

Rust

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

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

Scala 2

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

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

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

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

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

And instantiated as:

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

Swift

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

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

And instantiated as:

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

TypeScript

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

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

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

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

And instantiated as:

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

Zig

In Zig, an ADT may be defined with:^[41]

const Tree = union(enum) {
    empty,
    node: struct {
        value: i32,
        left: *const Tree,
        right: *const Tree,
    },
};

And instantiated as:

const my_tree: Tree = .{ .node = .{
    .value = 42,
    .left = &.{ .node = .{
        .value = 0,
        .left = &.empty,
        .right = &.empty,
    } },
    .right = &.empty,
} };

References

^ "Recursively Defined Datatypes".
^ "Example: Binary Search Tree".
^ "Dataviewtypes as Linear Datatypes".
^ "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. Archived from the original on 2021-12-04. 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
^ "PEP 604 – Allow writing union types as X | Y | peps.python.org". Python Enhancement Proposals (PEPs). Retrieved 2024-11-05.
^ "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.
^ "Documentation - The Zig Programming Language". ziglang.org. Retrieved 2024-12-16.

[1] "Recursively Defined Datatypes".

[2] "Example: Binary Search Tree".

[3] "Dataviewtypes as Linear Datatypes".

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[23] "An Overview of Miranda". www.cs.kent.ac.uk. Archived from the original on 2021-12-04. Retrieved 2021-12-04.

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

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

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

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

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

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

[30] PEP 484 – Type Hints, Python

[31] "PEP 604 – Allow writing union types as X | Y | peps.python.org". Python Enhancement Proposals (PEPs). Retrieved 2024-11-05.

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

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

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

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

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

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

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

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

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

[41] "Documentation - The Zig Programming Language". ziglang.org. Retrieved 2024-12-16.

[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]

[37]

[38]

[39]

[40]

[41]