What is an Algebraic Data Type (ADT)?

11
votes

I have heard people talking a lot about Algebraic Data Types (not to be confused with "Abstract Data Types") in functional programming. All I know is that ADT refers to some kind of composite (often recursive) data types like trees or math expressions.

In Wikipedia, it's only said that:

an algebraic data type is a kind of composite type, i.e., a type formed by combining other types. Two common classes of algebraic types are product types (i.e., tuples and records) and sum types (i.e. tagged or disjoint unions, or variant types).

But no formal definition is given.

So I am wondering what exactly is the definition of ADT? As per Wikipedia, product types and sum types are two examples of ADT, but are product and sum the only valid operations for defining ADT? Are there other operations which are also allowed?

2
functional-programmingalgebraic-data-types
They are data types which obey an algebra, i.e. a set of operations to combine them and a set of laws which those operations obey. That Wikipedia definition mentions two such operations: the product type and the sum type. – 4castle
@4castle, thank you for your explaination. Actually what I am asking for is exactly the formal definition of ADT, which includes the "set of laws" that defines ADT, could you please provide more information? In wikipedia, it only talks about "sum" and "product" as examples of algebraic operations, but are there any others algebraic operations that are also valid for constructing ADT? – Lifu Huang
Related: Abusing the algebra of algebraic data types - why does this work? – 4castle
Yes, there's more operations. For example, functions represent exponentiation, and zippers correspond to derivatives. The laws are just like the ones you learned in high school algebra. Associativity, commutativity, the distributive property, etc. – 4castle
General algebraic data types are named such since they correspond to an initial algebra. With a less mathematical background (like mine), you may find the blog post The Algebra of Algebraic Data Types helpful. – user6445533

2 Answers

8
votes

The Algebraic Data Types are composite types, that is, a type formed by the combination of other types and are commonly classified in two: sums and products.

For example:

Currency = USD + EUR + GBP
Money = Amount * Currency

The way to read this is to translate sums by OR and products by AND.

Product

A product is a type that can normally be created in any programming language, whether functional or not, such as classes in Kotlin, Java, C #, Struct in Swift or C # etc.

The parts of which they are composed are read with AND.

Money = Amount * Currency

They are known as products because the number of possible values they can have is the product of the number of possible values of the component parts.

Sum

A sum type is a type of algebraic data, also known as discriminated union or disjoint union, which traditionally had only direct support in languages such as Scala or Haskell.

The parts of which a sum type is composed are read as OR because the value of the result object can only contain one of the options.

Currency = USD + EUR + GBP

In this case, the currency value can only be USD or EUR or GBP.

They are known as sum because the number of possible values that can have is: the sum of the number of possible values of the parts that compose it.

This is a link to my blog (spanish), where I have a more complete article with kotlin examples: http://xurxodev.com/tipos-de-datos-algebraicos/

4
votes

Scala 3 will have better support for Algebraic Data Types. See this slide deck: https://www.slideshare.net/pjschwarz/scala-3-by-example-algebraic-data-types-for-domain-driven-design-part-1 (download for flawless image quality).

enter image description here enter image description here enter image description here