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]ATS
[edit]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
[edit]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
[edit]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
[edit]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++
[edit]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
[edit]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
[edit]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#
[edit]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*
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]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
[edit]This section needs expansion. You can help by adding to it. (December 2021) |
In OpenCog, an ADT may be defined with:[28]
PureScript
[edit]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
[edit]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
[edit]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
[edit]Reason
[edit]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
[edit]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
[edit]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
[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:[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
[edit]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
[edit]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
[edit]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
[edit]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).
References
[edit]- ^ "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.