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

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

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]

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]