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.

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

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);

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

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.

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>()
} };

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());

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

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)

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

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.

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

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);

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);

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

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()
);

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())

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,
)

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()
);

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).

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

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(),
);

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

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)

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

This section needs expansion. You can help by adding to it. (December 2021)

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

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

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())

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

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);

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)

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),
);

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
)

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
)

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)

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)

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" },
};

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).

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,
} };