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

Coq

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

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

And instantiated as:

Definitionmy_tree:=node42(node0emptyempty)empty.

C++

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

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

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

typeTree=Empty|NodeIntTreeTree

And instantiated as:

myTree=Node42(Node0EmptyEmpty)Empty

F#

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

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

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 [12] ), an ADT may be defined with variant records: [13] 

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

dataTree=Empty|NodeIntTreeTree

And instantiated as:

myTree=Node42(Node0EmptyEmpty)Empty

Haxe

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

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

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

dataTree=Empty|NodeNatTreeTree

And instantiated as:

myTree:Tree myTree=Node42(Node0EmptyEmpty)Empty

Java

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

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

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

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

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

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

tree::=Empty|Nodenumtreetree

And instantiated as:

my_tree=Node42(Node0EmptyEmpty)Empty

Nemerle

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

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

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

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

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

PureScript

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

dataTree=Empty|NodeIntTreeTree

And instantiated as:

myTree=Node42(Node0EmptyEmpty)Empty

Python

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

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

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

And instantiated as:

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

Reason

Reason

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

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

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

And instantiated as:

letmyTree=Node(42,Node(0,Empty,Empty),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,}};

Related Research Articles

Templates are a feature of the C++ programming language that allows functions and classes to operate with generic types. This allows a function or class declaration to reference via a generic variable another different class without creating full declaration for each of these different classes.

In computer programming, lazy initialization is the tactic of delaying the creation of an object, the calculation of a value, or some other expensive process until the first time it is needed. It is a kind of lazy evaluation that refers specifically to the instantiation of objects or other resources.

In object-oriented (OO) and functional programming, an immutable object is an object whose state cannot be modified after it is created. This is in contrast to a mutable object, which can be modified after it is created. In some cases, an object is considered immutable even if some internally used attributes change, but the object's state appears unchanging from an external point of view. For example, an object that uses memoization to cache the results of expensive computations could still be considered an immutable object.

Template metaprogramming (TMP) is a metaprogramming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. The output of these templates can include compile-time constants, data structures, and complete functions. The use of templates can be thought of as compile-time polymorphism. The technique is used by a number of languages, the best-known being C++, but also Curl, D, Nim, and XL.

In computer science, a tagged union, also called a variant, variant record, choice type, discriminated union, disjoint union, sum type, or coproduct, is a data structure used to hold a value that could take on several different, but fixed, types. Only one of the types can be in use at any one time, and a tag field explicitly indicates which type is in use. It can be thought of as a type that has several "cases", each of which should be handled correctly when that type is manipulated. This is critical in defining recursive datatypes, in which some component of a value may have the same type as that value, for example in defining a type for representing trees, where it is necessary to distinguish multi-node subtrees and leaves. Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type, since only one is in use at a time.

<span class="mw-page-title-main">C syntax</span> Set of rules defining correctly structured programs

The syntax of the C programming language is the set of rules governing writing of software in C. It is designed to allow for programs that are extremely terse, have a close relationship with the resulting object code, and yet provide relatively high-level data abstraction. C was the first widely successful high-level language for portable operating-system development.

In computer science, a union is a value that may have any of multiple representations or formats within the same area of memory; that consists of a variable that may hold such a data structure. Some programming languages support a union type for such a data type. In other words, a union type specifies the permitted types that may be stored in its instances, e.g., float and integer. In contrast with a record, which could be defined to contain both a float and an integer; a union would hold only one at a time.

In computer programming, a function object is a construct allowing an object to be invoked or called as if it were an ordinary function, usually with the same syntax. In some languages, particularly C++, function objects are often called functors.

In computer science, object composition and object aggregation are closely related ways to combine objects or data types into more complex ones. In conversation, the distinction between composition and aggregation is often ignored. Common kinds of compositions are objects used in object-oriented programming, tagged unions, sets, sequences, and various graph structures. Object compositions relate to, but are not the same as, data structures.

typedef is a reserved keyword in the programming languages C, C++, and Objective-C. It is used to create an additional name (alias) for another data type, but does not create a new type, except in the obscure case of a qualified typedef of an array type where the typedef qualifiers are transferred to the array element type. As such, it is often used to simplify the syntax of declaring complex data structures consisting of struct and union types, although it is also commonly used to provide specific descriptive type names for integer data types of varying sizes.

In computer programming, a sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. This type of node does not hold or reference any data managed by the data structure.

A class in C++ is a user-defined type or data structure declared with any of the keywords class, struct or union that has data and functions as its members whose access is governed by the three access specifiers private, protected or public. By default access to members of a C++ class declared with the keyword class is private. The private members are not accessible outside the class; they can be accessed only through member functions of the class. The public members form an interface to the class and are accessible outside the class.

In computer programming, an enumerated type is a data type consisting of a set of named values called elements, members, enumeral, or enumerators of the type. The enumerator names are usually identifiers that behave as constants in the language. An enumerated type can be seen as a degenerate tagged union of unit type. A variable that has been declared as having an enumerated type can be assigned any of the enumerators as a value. In other words, an enumerated type has values that are different from each other, and that can be compared and assigned, but are not specified by the programmer as having any particular concrete representation in the computer's memory; compilers and interpreters can represent them arbitrarily.

C++11 is a version of a joint technical standard, ISO/IEC 14882, by the International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC), for the C++ programming language. C++11 replaced the prior version of the C++ standard, named C++03, and was later replaced by C++14. The name follows the tradition of naming language versions by the publication year of the specification, though it was formerly named C++0x because it was expected to be published before 2010.

In computer science, a type punning is any programming technique that subverts or circumvents the type system of a programming language in order to achieve an effect that would be difficult or impossible to achieve within the bounds of the formal language.

In object-oriented computer programming, a null object is an object with no referenced value or with defined neutral (null) behavior. The null object design pattern, which describes the uses of such objects and their behavior, was first published as "Void Value" and later in the Pattern Languages of Program Design book series as "Null Object".

In computing, compile-time function execution is the ability of a compiler, that would normally compile a function to machine code and execute it at run time, to execute the function at compile time. This is possible if the arguments to the function are known at compile time, and the function does not make any reference to or attempt to modify any global state.

This article describes the syntax of the C# programming language. The features described are compatible with .NET Framework and Mono.

In computer programming, variadic templates are templates that take a variable number of arguments.

In programming languages and type theory, an option type or maybe type is a polymorphic type that represents encapsulation of an optional value; e.g., it is used as the return type of functions which may or may not return a meaningful value when they are applied. It consists of a constructor which either is empty, or which encapsulates the original data type A.

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. ↑ "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. ↑ cartermp. "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. Archived from the original on 2021-12-04. 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. ↑ "PEP 604 – Allow writing union types as X | Y | peps.python.org". Python Enhancement Proposals (PEPs). Retrieved 2024-11-05.
  32. ↑ "2 Beginning Typed Racket". docs.racket-lang.org. Retrieved 2021-12-04.
  33. ↑ "Variants · Reason". reasonml.github.io. Retrieved 2021-11-30.
  34. ↑ "Variant | ReScript Language Manual". ReScript Documentation. 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.