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

Ceylon

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

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

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

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

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

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#

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*

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

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

type
  TTreeKind = (tkEmpty, tkNode);

  PTree = ^TTree;

  TTree = record
    case FKind: TTreeKind of
      tkEmpty: ();
      tkNode: (
        FValue: Integer;
        FLeft, FRight: PTree;
      );
  end;

And instantiated as:

var
  MyTree: PTree;

begin
  new(MyTree);
  MyTree^.FKind := tkNode;
  MyTree^.FValue := 42;
  new(MyTree^.FLeft);
  MyTree^.FLeft^.FKind := tkNode;
  MyTree^.FLeft^.FValue := 0;
  new(MyTree^.FLeft^.FLeft);
  MyTree^.FLeft^.FLeft^.FKind := tkEmpty;
  new(MyTree^.FLeft^.FRight);
  MyTree^.FLeft^.FRight^.FKind := tkEmpty;
  new(MyTree^.FRight);
  MyTree^.FRight^.FKind := tkEmpty;
end.

Haskell

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

data Tree
    = Empty
    | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Haxe

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

enum Tree {
	Empty;
	Node(value:Int, left:Tree, right:Tree);
}

And instantiated as:

var myTree = Node(42, Node(0, Empty, Empty), Empty);

Hope

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

data tree == empty
          ++ node (num # tree # tree);

And instantiated as:

dec mytree : tree;
--- mytree <= node (42, node (0, empty, empty), empty);

Idris

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

data Tree
    = Empty
    | Node Nat Tree Tree

And instantiated as:

myTree : Tree
myTree = Node 42 (Node 0 Empty Empty) Empty

Java

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

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

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

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

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

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

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

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

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

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

And instantiated as:

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

Miranda

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

tree ::=
    Empty
    | Node num tree tree

And instantiated as:

my_tree = Node 42 (Node 0 Empty Empty) Empty

Nemerle

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

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

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

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

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

type tree =
  | Empty
  | Node of int * tree * tree

And instantiated as:

let my_tree = Node (42, Node (0, Empty, Empty), Empty)

Opa

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

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

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

PureScript

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

data Tree
  = Empty
  | Node Int Tree Tree

And instantiated as:

myTree = Node 42 (Node 0 Empty Empty) Empty

Python

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

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

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

(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

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

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

And instantiated as:

let myTree = Node(42, Node(0, Empty, Empty), Empty);

ReScript

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

type rec Tree =
  | Empty
  | Node(int, Tree, Tree)

And instantiated as:

let myTree = Node(42, Node(0, Empty, Empty), Empty)

Rust

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

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

Scala 2

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

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

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

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

datatype tree =
    EMPTY
  | NODE of int * tree * tree

And instantiated as:

val myTree = NODE (42, NODE (0, EMPTY, EMPTY), EMPTY)

Swift

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

enum Tree {
    case empty
    indirect case node(Int, Tree, Tree)
}

And instantiated as:

let myTree: Tree = .node(42, .node(0, .empty, .empty), .empty)

TypeScript

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

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

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

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

And instantiated as:

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

References

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Comparison of programming languages (algebraic data type). Read more

[1] "Eclipse Ceylon: Union, intersection, and enumerated types". https://ceylon-lang.org/documentation/1.3/tour/types/#enumerated_types.

[2] "Clean 2.2 Ref Man". https://clean.cs.ru.nl/download/html_report/CleanRep.2.2_7.htm#_Toc311798039.

[3] "Inductive types and recursive functions — Coq 8.14.1 documentation". https://coq.inria.fr/refman/language/core/inductive.html.

[4] "std::variant - cppreference.com". https://en.cppreference.com/w/cpp/utility/variant.

[5] "Patterns" (in en). https://dart.dev/language/patterns#algebraic-data-types.

[6] "Custom Types · An Introduction to Elm". https://guide.elm-lang.org/types/custom_types.html.

[7] rtermp. "Discriminated Unions - F#" (in en-us). https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/discriminated-unions.

[8] "Inductive types and pattern matching — Proof-Oriented Programming in F* documentation". https://www.fstar-lang.org/tutorial/book/part1/part1_inductives.html.

[9] "Record types". https://www.freepascal.org/docs-html/current/ref/refsu15.html.

[10] "4 Declarations and Bindings". https://www.haskell.org/onlinereport/haskell2010/haskellch4.html#x10-690004.2.1.

[11] "Enum Instance". https://haxe.org/manual/types-enum-instance.html.

[12] "Defining your own data types". 2011-08-10. http://www.soi.city.ac.uk/~ross/Hope/hope_tut/node18.html.

[13] "Types and Functions — Idris2 0.0 documentation". https://idris2.readthedocs.io/en/latest/tutorial/typesfuns.html#data-types.

[14] "JEP 409: Sealed Classes". https://openjdk.java.net/jeps/409.

[15] "Types · The Julia Language". https://docs.julialang.org/en/v1/manual/types/#Type-Unions.

[16] "Sealed classes | Kotlin" (in en-US). https://kotlinlang.org/docs/sealed-classes.html.

[17] Stanley-Marbell, Phillip (2003) (in English). Inferno Programming with Limbo. Wiley. pp. 67–71. ISBN 978-0470843529.

[18] "The Mercury Language Reference Manual: Discriminated unions". https://www.mercurylang.org/information/doc-release/mercury_ref/Discriminated-unions.html.

[19] "An Overview of Miranda". https://www.cs.kent.ac.uk/people/staff/dat/miranda/Overview.html#User.

[20] "Basic Variants · rsdn/nemerle Wiki" (in en). https://github.com/rsdn/nemerle/wiki/Basic-Variants/4fcecdfa79c0751f70bff83225e125f40425d1f4.

[21] "Nim Manual". https://nim-lang.org/docs/manual.html#types-object-variants.

[22] "OCaml - The OCaml language". https://ocaml.org/manual/typedecl.html.

[23] "The type system · MLstate/opalang Wiki" (in en). https://github.com/MLstate/opalang/wiki/The-type-system/aacaf2c26b1e20189e01923cf1f9a813f355b592#sum-1.

[24] "Type constructor - OpenCog". https://wiki.opencog.org/w/Type_constructor.

[25] purescript/documentation, PureScript, 2021-11-24, https://github.com/purescript/documentation/blob/7295b335dfbda17015e68f4c74b81e91007f79b8/language/Types.md#tagged-unions, retrieved 2021-11-30

[26] PEP 484 – Type Hints, Python, https://peps.python.org/pep-0484/#union-types

[27] "2 Beginning Typed Racket". https://docs.racket-lang.org/ts-guide/beginning.html#(part._.Datatypes_and_.Unions).

[28] "Variants · Reason" (in en). https://reasonml.github.io/docs/en/variant.

[29] "Variant | ReScript Language Manual". https://rescript-lang.org/docs/manual/latest/variant.

[30] "enum - Rust". https://doc.rust-lang.org/std/keyword.enum.html.

[31] "Algebraic Data Types". https://docs.scala-lang.org/scala3/reference/enums/adts.html.

[32] "Defining datatypes". https://homepages.inf.ed.ac.uk/stg/NOTES/node41.html.

[33] "Enumerations — The Swift Programming Language (Swift 5.5)". https://docs.swift.org/swift-book/LanguageGuide/Enumerations.html.

[34] "Documentation - TypeScript for Functional Programmers" (in en). https://www.typescriptlang.org/docs/handbook/typescript-in-5-minutes-func.html#discriminated-unions.

[35] "Language Reference/Domains - wiki.visual-prolog.com". https://wiki.visual-prolog.com/index.php?title=Language_Reference/Domains#Compound_Domains.

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

Anonymous

Search

Comparison of programming languages (algebraic data type)

Examples of algebraic data types

Ceylon

Clean

Coq

C++

Dart

Elm

F#

F*

Free Pascal

Haskell

Haxe

Hope

Idris

Java

Julia

Kotlin

Limbo

Mercury

Miranda

Nemerle

Nim

OCaml

Opa

OpenCog

PureScript

Python

Racket

Reason

Reason

ReScript

Rust

Scala

Scala 2

Scala 3

Standard ML

Swift

TypeScript

Visual Prolog

References

Navigation

Wiki tools

Page tools

Other projects

Categories