Comparison of programming languages (algebraic data type)

Last updated

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.

Contents

Examples of algebraic data types

ATS

In ATS, an ADT may be defined with: [1] [2] 

datatypetree=|Emptyof()|Nodeof(int,tree,tree)

And instantiated as:

valmy_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 *)dataviewtypeint_or_string_vt(bool)=|String_vt(true)ofstring|Int_vt(false)ofint(* Alternatively one can use the vtypedef keyword *)viewtypedefInt_or_String_vt=[b:bool]int_or_string_vtbfnprint_int_or_string(i_or_s:Int_or_String_vt):void=case+i_or_sof(* ~ 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;endimplementmain0():void=letvalstring_hello_world=String_vt"Hello, world!"valint_0=Int_vt0inprint_int_or_stringstring_hello_world;print_int_or_stringint_0;(* which prints: Hello, world! 0 *)end

Ceylon

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

abstractclassTree()ofempty|Node{}objectemptyextendsTree(){}finalclassNode(sharedIntegerval,sharedTreeleft,sharedTreeright)extendsTree(){}

And instantiated as:

valuemyTree=Node(42,Node(0,empty,empty),empty);

Clean

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

::Tree=Empty|NodeIntTreeTree

And instantiated as:

myTree=Node42(Node0EmptyEmpty)Empty

C++

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

structEmptyfinal{};structNodefinal{intvalue;std::unique_ptr<std::variant<Empty,Node>>left;std::unique_ptr<std::variant<Empty,Node>>right;};usingTree=std::variant<Empty,Node>;

And instantiated as:

TreemyTree{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: [7] 

sealedclassTree{}finalclassEmptyextendsTree{}finalclassNodeextendsTree{finalintvalue;finalTreeleft,right;Node(this.value,this.left,this.right);}

And instantiated as:

finalmyTree=Node(42,Node(0,Empty(),Empty()),Empty());

Elm

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

typeTree=Empty|NodeIntTreeTree

And instantiated as:

myTree=Node42(Node0EmptyEmpty)Empty

F#

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

typeTree=|Empty|Nodeofint*Tree*Tree

And instantiated as:

letmyTree=Node(42,Node(0,Empty,Empty),Empty)

F*

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

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

And instantiated as:

letmy_tree=Node42(Node0EmptyEmpty)Empty

Free Pascal

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

{$mode ISO}programMakeTree;typeTreeKind=(Empty,Node);PTree=^Tree;Tree=recordcaseKind:TreeKindofEmpty:();Node:(Value:Integer;Left,Right:PTree;);end;

And instantiated as:

varMyTree:PTree;beginnew(MyTree,Node);withMyTree^dobeginValue:=42;new(Left,Node);withLeft^dobeginValue:=0;new(Left,Empty);new(Right,Empty);end;new(Right,Empty);end;end.

Haskell

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

dataTree=Empty|NodeIntTreeTree

And instantiated as:

myTree=Node42(Node0EmptyEmpty)Empty

Haxe

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

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

And instantiated as:

varmyTree=Node(42,Node(0,Empty,Empty),Empty);

Hope

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

datatree==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: [16] 

dataTree=Empty|NodeNatTreeTree

And instantiated as:

myTree:Tree myTree=Node42(Node0EmptyEmpty)Empty

Java

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

sealedinterfaceTree{recordEmpty()implementsTree{}recordNode(intvalue,Treeleft,Treeright)implementsTree{}}

And instantiated as:

varmyTree=newTree.Node(42,newTree.Node(0,newTree.Empty(),newTree.Empty()),newTree.Empty());

Julia

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

structEmptyendstructNodevalue::Intleft::Union{Empty,Node}right::Union{Empty,Node}endconstTree=Union{Empty,Node}

And instantiated as:

mytree=Node(42,Node(0,Empty(),Empty()),Empty())

Kotlin

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

sealedclassTree{objectEmpty:Tree()dataclassNode(valvalue:Int,valleft:Tree,valright:Tree):Tree()}

And instantiated as:

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

Limbo

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

Tree:adt{pick{Empty=>Node=>value:int;left:refTree;right:refTree;}};

And instantiated as:

myTree:=refTree.Node(42,refTree.Node(0,refTree.Empty(),refTree.Empty()),refTree.Empty());

Mercury

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

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

tree::=Empty|Nodenumtreetree

And instantiated as:

my_tree=Node42(Node0EmptyEmpty)Empty

Nemerle

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

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

And instantiated as:

defmyTree=Tree.Node(42,Tree.Node(0,Tree.Empty(),Tree.Empty()),Tree.Empty(),);

Nim

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

typeTreeKind=enumtkEmptytkNodeTree=refTreeObjTreeObj=objectcasekind:TreeKindoftkEmpty:discardoftkNode:value:intleft,right:Tree

And instantiated as:

letmyTree=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: [25] 

typetree=|Empty|Nodeofint*tree*tree

And instantiated as:

letmy_tree=Node(42,Node(0,Empty,Empty),Empty)

Opa

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

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

PureScript

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

dataTree=Empty|NodeIntTreeTree

And instantiated as:

myTree=Node42(Node0EmptyEmpty)Empty

Python

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

from__future__importannotationsfromdataclassesimportdataclass@dataclassclassEmpty:pass@dataclassclassNode:value:intleft:Treeright:TreeTree=Empty|Node

And instantiated as:

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

Racket

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

(structEmpty())(structNode([value:Integer][left:Tree][right:Tree]))(define-typeTree(UEmptyNode))

And instantiated as:

(definemy-tree(Node42(Node0(Empty)(Empty))(Empty)))

Reason

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

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

And instantiated as:

letmyTree=Node(42,Node(0,Empty,Empty),Empty);

ReScript

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

typerecTree=|Empty|Node(int,Tree,Tree)

And instantiated as:

letmyTree=Node(42,Node(0,Empty,Empty),Empty)

Rocq

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

Inductivetree:Type:=|empty:tree|node:nat->tree->tree->tree.

And instantiated as:

Definitionmy_tree:=node42(node0emptyempty)empty.

Rust

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

enumTree{Empty,Node(i32,Box<Tree>,Box<Tree>),}

And instantiated as:

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

sealedabstractclassTreeextendsProductwithSerializableobjectTree{finalcaseobjectEmptyextendsTreefinalcaseclassNode(value:Int,left:Tree,right:Tree)extendsTree}

And instantiated as:

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

Scala 3

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

enumTree:caseEmptycaseNode(value:Int,left:Tree,right:Tree)

And instantiated as:

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

Standard ML

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

datatypetree=EMPTY|NODEofint*tree*tree

And instantiated as:

valmyTree=NODE(42,NODE(0,EMPTY,EMPTY),EMPTY)

Swift

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

enumTree{caseemptyindirectcasenode(Int,Tree,Tree)}

And instantiated as:

letmyTree:Tree=.node(42,.node(0,.empty,.empty),.empty)

TypeScript

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

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

And instantiated as:

constmyTree: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: [40] 

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

And instantiated as:

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

Zig

In Zig, an ADT may be defined with: [41] 

constTree=union(enum){empty,node:struct{value:i32,left:*constTree,right:*constTree,},};

And instantiated as:

constmy_tree:Tree=.{.node=.{.value=42,.left=&.{.node=.{.value=0,.left=&.empty,.right=&.empty,}},.right=&.empty,}};

References

  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. ↑ "std::variant - cppreference.com". en.cppreference.com. Retrieved 2021-12-04.
  7. ↑ "Patterns". dart.dev. Retrieved 2023-09-28.
  8. ↑ "Custom Types · An Introduction to Elm". guide.elm-lang.org. Retrieved 2021-11-29.
  9. ↑ cartermp. "Discriminated Unions - F#". docs.microsoft.com. Retrieved 2021-11-29.
  10. ↑ "Inductive types and pattern matching — Proof-Oriented Programming in F* documentation". www.fstar-lang.org. Retrieved 2021-12-06.
  11. ↑ "Mode iso". wiki.freepascal.org. Retrieved 2024-05-26.
  12. ↑ "Record types". www.freepascal.org. Retrieved 2021-12-05.
  13. ↑ "4 Declarations and Bindings". www.haskell.org. Retrieved 2021-12-07.
  14. ↑ "Enum Instance". Haxe - The Cross-platform Toolkit. Retrieved 2021-11-29.
  15. ↑ "Defining your own data types". 2011-08-10. Archived from the original on 2011-08-10. Retrieved 2021-12-03.
  16. ↑ "Types and Functions — Idris2 0.0 documentation". idris2.readthedocs.io. Retrieved 2021-11-30.
  17. ↑ "JEP 409: Sealed Classes". openjdk.java.net. Retrieved 2021-12-05.
  18. ↑ "Types · The Julia Language". docs.julialang.org. Retrieved 2021-12-03.
  19. ↑ "Sealed classes | Kotlin". Kotlin Help. Retrieved 2021-11-29.
  20. ↑ Stanley-Marbell, Phillip (2003). Inferno Programming with Limbo. Wiley. pp. 67–71. ISBN   978-0470843529.
  21. ↑ "The Mercury Language Reference Manual: Discriminated unions". www.mercurylang.org. Retrieved 2021-12-07.
  22. ↑ "An Overview of Miranda". www.cs.kent.ac.uk. Archived from the original on 2021-12-04. Retrieved 2021-12-04.
  23. ↑ "Basic Variants · rsdn/nemerle Wiki". GitHub. Retrieved 2021-12-03.
  24. ↑ "Nim Manual". nim-lang.org. Retrieved 2021-11-29.
  25. ↑ "OCaml - The OCaml language". ocaml.org. Retrieved 2021-12-07.
  26. ↑ "The type system · MLstate/opalang Wiki". GitHub. Retrieved 2021-12-07.
  27. ↑ "Type constructor - OpenCog". wiki.opencog.org. Retrieved 2021-12-07.
  28. ↑ purescript/documentation, PureScript, 2021-11-24, retrieved 2021-11-30
  29. ↑ PEP 484 – Type Hints, Python
  30. ↑ "PEP 604 – Allow writing union types as X | Y | peps.python.org". Python Enhancement Proposals (PEPs). Retrieved 2024-11-05.
  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 2025-12-21.
  34. ↑ "Inductive types and recursive functions – Rocq 8.14.1 documentation". Rocq-prover.org. Retrieved 2021-11-30.
  35. ↑ "enum - Rust". doc.rust-lang.org. Retrieved 2021-11-29.
  36. ↑ "Algebraic Data Types". Scala Documentation. Retrieved 2021-11-29.
  37. ↑ "Defining datatypes". homepages.inf.ed.ac.uk. Retrieved 2021-12-01.
  38. ↑ "Enumerations — The Swift Programming Language (Swift 5.5)". docs.swift.org. Retrieved 2021-11-29.
  39. ↑ "Documentation - TypeScript for Functional Programmers". www.typescriptlang.org. Retrieved 2021-11-29.
  40. ↑ "Language Reference/Domains - wiki.visual-prolog.com". wiki.visual-prolog.com. Retrieved 2021-12-07.
  41. ↑ "Documentation - The Zig Programming Language". ziglang.org. Retrieved 2024-12-16.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.