Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Algebraic data type
Summary
In computer programming, especially functional programming and type theory, an algebraic data type (ADT) 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, coproduct types or variant types).
The values of a product type typically contain several values, called fields. All values of that type have the same combination of field types. The set of all possible values of a product type is the set-theoretic product, i.e., the Cartesian product, of the sets of all possible values of its field types.
The values of a sum type are typically grouped into several classes, called variants. A value of a variant type is usually created with a quasi-functional entity called a constructor. Each variant has its own constructor, which takes a specified number of arguments with specified types. The set of all possible values of a sum type is the set-theoretic sum, i.e., the disjoint union, of the sets of all possible values of its variants. Enumerated types are a special case of sum types in which the constructors take no arguments, as exactly one value is defined for each constructor.
Values of algebraic types are analyzed with pattern matching, which identifies a value by its constructor or field names and extracts the data it contains.
Algebraic data types were introduced in Hope, a small functional programming language developed in the 1970s at the University of Edinburgh.
One of the most common examples of an algebraic data type is the singly linked list. A list type is a sum type with two variants, Nil for an empty list and Cons x xs for the combination of a new element x with a list xs to create a new list. Here is an example of how a singly linked list would be declared in Haskell:
data List a = Nil | Cons a (List a)
or
data [] a = [] | a : [a]
Cons is an abbreviation of construct. Many languages have special syntax for lists defined in this way.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related courses (32)
BIOENG-601: Python Bootcamp
An intensive, hands-on, pragmatic introduction to computer programming. Students learn basic concepts like data types, control structures, string processing, functions, input/output. They perform simu
CS-214: Software construction
Learn how to design and implement reliable, maintainable, and efficient software using a mix of programming skills (declarative style, higher-order functions, inductive types, parallelism) and
fundam
EE-320: Analog IC design
Introduction to the design of analog CMOS integrated circuits at the transistor level. Understanding and design of basic structures.
Related lectures (172)
Differential Amplifier Design
Covers the design of a differential amplifier with key parameters like gain and bias current.
Stabilizer Formalism: Quantum Error Correction
Covers the stabilizer formalism in quantum error correction codes.
Advanced C Data Types
Covers advanced data types and memory management in C programming, emphasizing type consistency and dynamic array allocation.
Related publications (221)
When Subtyping Constraints Liberate A Novel Type Inference Approach for First-Class Polymorphism
Lionel Emile Vincent Parreaux, Aleksander Slawomir Boruch-Gruszecki
Type inference in the presence of first-class or "impredicative" second-order polymorphism a la System F has been an active research area for several decades, with original works dating back to the end of the 80s. Yet, until now many basic problems remain ...
Assoc Computing Machinery2024MultiModN- Multimodal, Multi-Task, Interpretable Modular Networks
Martin Jaggi, Mary-Anne Hartley, Vinitra Swamy, Jibril Albachir Frej, Thierry Bossy, Thijs Vogels, Malika Satayeva
Predicting multiple real-world tasks in a single model often requires a particularly diverse feature space. Multimodal (MM) models aim to extract the synergistic predictive potential of multiple data types to create a shared feature space with aligned sema ...
2023Who was afraid of Yuri Mikhailovich and why? (peculiarities of the reception of the Tartu version of structuralism after the 1960s)
The paper discussed different types of reactions to the emergence of Yuri Lotman's structuralism in the Soviet Union after 1960 ...
2023Related people (32)
Related units (4)
Related concepts (24)
Scala (programming language)
Scala (ˈskɑːlə ) is a strong statically typed high-level general-purpose programming language that supports both object-oriented programming and functional programming. Designed to be concise, many of Scala's design decisions are aimed to address criticisms of Java. Scala source code can be compiled to Java bytecode and run on a Java virtual machine (JVM). Scala can also be compiled to JavaScript to run in a browser, or directly to a native executable.
Tagged union
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 one 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.
Haskell
Haskell (ˈhæskəl) is a general-purpose, statically-typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell has pioneered a number of programming language features such as type classes, which enable type-safe operator overloading, and monadic input/output (IO). It is named after logician Haskell Curry. Haskell's main implementation is the Glasgow Haskell Compiler (GHC).
Related MOOCs (20)
Parallelism and Concurrency
(merge of parprog1, scala-reactive, scala-spark-big-data)
Functional Programming
In this course you will discover the elements of the functional programming style and learn how to apply them usefully in your daily programming tasks. You will also develop a solid foundation for rea
Functional Programming Principles in Scala [retired]
This advanced undergraduate programming course covers the principles of functional programming using Scala, including the use of functions as values, recursion, immutability, pattern matching, higher-