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]

<syntaxhighlight lang="ocaml"> datatype tree = | Empty of () | Node of (int, tree, tree) </syntaxhighlight>

And instantiated as: <syntaxhighlight lang="ocaml"> val my_tree = Node(42, Node(0, Empty, Empty), Empty) </syntaxhighlight>

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:

<syntaxhighlight lang="ocaml"> (* 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 </syntaxhighlight>

Ceylon

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

<syntaxhighlight lang="ceylon"> abstract class Tree()

   of empty | Node {}

object empty

   extends Tree() {}

final class Node(shared Integer val, shared Tree left, shared Tree right)

   extends Tree() {}

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="ceylon"> value myTree = Node(42, Node(0, empty, empty), empty); </syntaxhighlight>

Clean

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

Tree

 = Empty
 | Node Int Tree Tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="clean"> myTree = Node 42 (Node 0 Empty Empty) Empty </syntaxhighlight>

Coq

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

<syntaxhighlight lang="coq"> Inductive tree : Type := | empty : tree | node : nat -> tree -> tree -> tree. </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="coq"> Definition my_tree := node 42 (node 0 empty empty) empty. </syntaxhighlight>

C++

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

<syntaxhighlight lang="cpp"> 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>; </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="cpp"> Tree myTree { Node{

   42,
   std::make_unique<Tree>(Node{
       0,
       std::make_unique<Tree>(),
       std::make_unique<Tree>()
   }),
   std::make_unique<Tree>()

} }; </syntaxhighlight>

Dart

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

<syntaxhighlight lang="dart"> 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);

} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="dart"> final myTree = Node(42, Node(0, Empty(), Empty()), Empty()); </syntaxhighlight>

Elm

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

<syntaxhighlight lang="elm"> type Tree

 = Empty
 | Node Int Tree Tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="elm"> myTree = Node 42 (Node 0 Empty Empty) Empty </syntaxhighlight>

F#

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

<syntaxhighlight lang="fsharp"> type Tree =

   | Empty
   | Node of int * Tree * Tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="fsharp"> let myTree = Node(42, Node(0, Empty, Empty), Empty) </syntaxhighlight>

F*

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

<syntaxhighlight lang="fstar"> type tree =

 | Empty : tree
 | Node : value:nat -> left:tree -> right:tree -> tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="fstar"> let my_tree = Node 42 (Node 0 Empty Empty) Empty </syntaxhighlight>

Free Pascal

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

<syntaxhighlight lang="pascal"> {$mode ISO} program MakeTree;

type TreeKind = (Empty, Node);

 PTree = ^Tree;
 Tree = record
   case Kind: TreeKind of
     Empty: ();
     Node: (
       Value: Integer;
       Left, Right: PTree;
     );
 end;

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="pascal"> 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. </syntaxhighlight>

Haskell

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

<syntaxhighlight lang="haskell"> data Tree

   = Empty
   | Node Int Tree Tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="haskell"> myTree = Node 42 (Node 0 Empty Empty) Empty </syntaxhighlight>

Haxe

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

<syntaxhighlight lang="haxe"> enum Tree { Empty; Node(value:Int, left:Tree, right:Tree); } </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="haxe"> var myTree = Node(42, Node(0, Empty, Empty), Empty); </syntaxhighlight>

Hope

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

<syntaxhighlight lang="haskell"> data tree == empty

         ++ node (num # tree # tree);

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="text"> dec mytree : tree; --- mytree <= node (42, node (0, empty, empty), empty); </syntaxhighlight>

Idris

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

<syntaxhighlight lang="idris"> data Tree

   = Empty
   | Node Nat Tree Tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="idris"> myTree : Tree myTree = Node 42 (Node 0 Empty Empty) Empty </syntaxhighlight>

Java

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

<syntaxhighlight lang="java"> sealed interface Tree {

   record Empty() implements Tree {}
   record Node(int value, Tree left, Tree right) implements Tree {}

} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="java"> var myTree = new Tree.Node(

   42,
   new Tree.Node(0, new Tree.Empty(), new Tree.Empty()),
   new Tree.Empty()

); </syntaxhighlight>

Julia

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

<syntaxhighlight lang="julia"> struct Empty end

struct Node

   value::Int
   left::Union{Empty, Node}
   right::Union{Empty, Node}

end

const Tree = Union{Empty, Node} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="julia"> mytree = Node(42, Node(0, Empty(), Empty()), Empty()) </syntaxhighlight>

Kotlin

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

<syntaxhighlight lang="kotlin"> sealed class Tree {

   object Empty : Tree()
   data class Node(val value: Int, val left: Tree, val right: Tree) : Tree()

} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="kotlin"> val myTree = Tree.Node(

   42,
   Tree.Node(0, Tree.Empty, Tree.Empty),
   Tree.Empty,

) </syntaxhighlight>

Limbo

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

<syntaxhighlight lang="limbo"> Tree: adt { pick { Empty => Node => value: int; left: ref Tree; right: ref Tree; } }; </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="limbo"> myTree := ref Tree.Node( 42, ref Tree.Node(0, ref Tree.Empty(), ref Tree.Empty()), ref Tree.Empty() ); </syntaxhighlight>

Mercury

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

- type tree

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

</syntaxhighlight>

And instantiated as:

- func my_tree = tree.

my_tree = node(42, node(0, empty, empty), empty). </syntaxhighlight>

Miranda

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

<syntaxhighlight lang="haskell"> tree ::=

   Empty
   | Node num tree tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="haskell"> my_tree = Node 42 (Node 0 Empty Empty) Empty </syntaxhighlight>

Nemerle

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

<syntaxhighlight lang="nemerle"> variant Tree {

   | Empty
   | Node {
       value: int;
       left: Tree;
       right: Tree;
   }

} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="nemerle"> def myTree = Tree.Node(

   42,
   Tree.Node(0, Tree.Empty(), Tree.Empty()),
   Tree.Empty(),

); </syntaxhighlight>

Nim

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

<syntaxhighlight lang="nim"> type

 TreeKind = enum
   tkEmpty
   tkNode

 Tree = ref TreeObj

 TreeObj = object
   case kind: TreeKind
   of tkEmpty:
     discard
   of tkNode:
     value: int
     left, right: Tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="nim"> 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))

</syntaxhighlight>

OCaml

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

<syntaxhighlight lang="ocaml"> type tree =

 | Empty
 | Node of int * tree * tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="ocaml"> let my_tree = Node (42, Node (0, Empty, Empty), Empty) </syntaxhighlight>

Opa

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

<syntaxhighlight lang="opa"> type tree =

 { empty } or
 { node, int value, tree left, tree right }

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="opa"> my_tree = {

 node,
 value: 42,
 left: {
   node,
   value: 0,
   left: { empty },
   right: { empty }
 },
 right: { empty }

} </syntaxhighlight>

OpenCog

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

PureScript

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

<syntaxhighlight lang="haskell"> data Tree

 = Empty
 | Node Int Tree Tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="haskell"> myTree = Node 42 (Node 0 Empty Empty) Empty </syntaxhighlight>

Python

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

<syntaxhighlight lang="python"> from __future__ import annotations from dataclasses import dataclass

@dataclass class Empty:

   pass

@dataclass class Node:

   value: int
   left: Tree
   right: Tree

Tree = Empty | Node </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="python"> my_tree = Node(42, Node(0, Empty(), Empty()), Empty()) </syntaxhighlight>

Racket

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

<syntaxhighlight lang="racket"> (struct Empty ()) (struct Node ([value : Integer] [left : Tree] [right : Tree])) (define-type Tree (U Empty Node)) </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="racket"> (define my-tree (Node 42 (Node 0 (Empty) (Empty)) (Empty))) </syntaxhighlight>

Reason

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

<syntaxhighlight lang="reason"> type Tree =

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

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="reason"> let myTree = Node(42, Node(0, Empty, Empty), Empty); </syntaxhighlight>

ReScript

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

<syntaxhighlight lang="haskell"> type rec Tree =

 | Empty
 | Node(int, Tree, Tree)

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="haskell"> let myTree = Node(42, Node(0, Empty, Empty), Empty) </syntaxhighlight>

Rust

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

<syntaxhighlight lang="rust"> enum Tree {

   Empty,
   Node(i32, Box<Tree>, Box<Tree>),

} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="rust"> let my_tree = Tree::Node(

   42,
   Box::new(Tree::Node(0, Box::new(Tree::Empty), Box::new(Tree::Empty)),
   Box::new(Tree::Empty),

); </syntaxhighlight>

Scala

Scala 2

In Scala 2, an ADT may be defined with:^{[citation needed]}

<syntaxhighlight lang="scala"> 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

} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="scala"> val myTree = Tree.Node(

 42,
 Tree.Node(0, Tree.Empty, Tree.Empty),
 Tree.Empty

) </syntaxhighlight>

Scala 3

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

<syntaxhighlight lang="scala"> enum Tree:

 case Empty
 case Node(value: Int, left: Tree, right: Tree)

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="scala"> val myTree = Tree.Node(

 42,
 Tree.Node(0, Tree.Empty, Tree.Empty),
 Tree.Empty

) </syntaxhighlight>

Standard ML

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

<syntaxhighlight lang="sml"> datatype tree =

   EMPTY
 | NODE of int * tree * tree

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="sml"> val myTree = NODE (42, NODE (0, EMPTY, EMPTY), EMPTY) </syntaxhighlight>

Swift

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

<syntaxhighlight lang="swift"> enum Tree {

   case empty
   indirect case node(Int, Tree, Tree)

} </syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="swift"> let myTree: Tree = .node(42, .node(0, .empty, .empty), .empty) </syntaxhighlight>

TypeScript

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

<syntaxhighlight lang="typescript"> type Tree =

 | { kind: "empty" }
 | { kind: "node"; value: number; left: Tree; right: Tree };

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="typescript"> const myTree: Tree = {

 kind: "node",
 value: 42,
 left: {
   kind: "node",
   value: 0,
   left: { kind: "empty" },
   right: { kind: "empty" },
 },
 right: { kind: "empty" },

}; </syntaxhighlight>

Visual Prolog

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

<syntaxhighlight lang="visualprolog"> domains

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

</syntaxhighlight>

And instantiated as:

<syntaxhighlight lang="visualprolog"> constants

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

</syntaxhighlight>

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. 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
^ "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.

[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. 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] "2 Beginning Typed Racket". docs.racket-lang.org. Retrieved 2021-12-04.

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

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

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

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

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

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

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

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

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