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