# A Glossary of Functional Programming

I’ve taught functional programming for years now, each time experimenting with different ways of teaching core concepts. Over time, I’ve collected and converged on simple (but reasonably precise) pedagogical definitions for a range of functional concepts.

In this post, I’ll share those definitions with you, in my first ever, *Glossary of Functional Programming*. Enjoy!

## Glossary

**Abstraction**. An *abstraction* is a precise description of the ways in which different data types share common structure. Abstraction allows different data types to participate in *generic programming*. In functional programming, abstractions are defined by *algebraic structure*, and are usually encoded in a programming language using *type classes*. Common examples of abstractions include monoids, functors, and monads.

**Ad Hoc Polymorphism**. *Ad hoc polymorphism* is any language feature that allows overloading functions and operators (providing multiple implementations for the same symbol) in such a fashion that the compiler or runtime can automatically select which implementation to call based on the types involved in the function application. Examples of ad hoc polymorphism include method overloading and *type classes*.

**Algebra**. An *algebra* is a set of *elements* together with a set of *operations* on the elements. The operations of an algebra are defined by *algebraic laws*, which give the operations meaning by relating them to each other. For example, addition on integers forms a very simple algebra, where the elements are integers, and the sole operation is addition, which satisfies assocative and commutative laws.

**Algebraic Data Type (ADT)**. An *algebraic data type* is any data type composed from *product types* (records) and *sum types* (enumerations). In functional programming, algebraic data types are used for *data modeling*.

**Algebraic Law**. An *algebraic law* is a *universally quantified* statement that asserts a relationship between the *operations* of an *algebra*. For example, an algebraic law for addition could assert that `(a + b) + c`

is equal to `a + (b + c)`

(*associativity*). In mainstream programming languages, algebraic laws are usually tested using *property-based testing*.

**Algebraic Structure**. *Algebraic structure* is any *structure* that is defined using an *algebra*.

**Applicative**. An `Applicative`

Functor is an `Apply`

Functor that allows taking a value and converting it into a *functional effect* that succeeds with the specified value. Under the view of functors as DSLs, `Applicative`

adds a “pure return” statement to the DSL.

**Apply**. An `Apply`

Functor is a Functor that allows zipping two *functional effects* together, to get a tuple of their successes. Under the view of functors as DSLs, `Apply`

adds a way to combine two programs together into one program, and preserve both successes.

**Associativity**. An *associative* operator is a binary operator that, when applied to three values, always results in the same value, regardless of the order in which pairwise values are combined. For example, addition on numbers is associative, because for all numbers `a`

, `b`

, and `c`

, `(a + b) + c`

is equal to `a + (b + c)`

.

**Category Theory**. *Category theory* is a branch of mathematics that defines mathematical structure using directed labeled graphs (*categories*). An alternative to algebraically-defined structure, category theory is a powerful and precise pattern language for mathematics, computer science, and functional programming. Knowledge of category theory is helpful but not necessary for mastery of applied functional programming.

**Commutativity**. A *commutative* operator is a binary operator that produces the same result no matter the order of the operands. For example, addition is commutative because `a + b`

is equal to `b + a`

, for all numbers `a`

and `b`

.

**Composable**. An operator is *composable* if it can be applied to its own return value. For example, the addition operator is composable with respect to integers, because it returns another integer, which can then be added to other integers. Similarly, the boolean negation operator is composable, because it is possible to negate a boolean value that has itself been negated. Composability allows a small number of operators (which can be reasoned about simply) to have immense expressive power.

**Contravariant Functor**. A `Contravariant`

Functor is a type class that allows transforming the input type to some *functional effect* using a function. Contravariant functors are often formed by polymorphic types that accept input (such as functions, or stages in a pipeline).

**Data Modeling**. *Data modeling* is the act of constructing a data model of domain objects (such as people, products, schedules, etc.). A goal of data modeling in statically-typed functional programming is to construct a data model so precise, it is impossible to construct bad data, a process sometimes called, *making illegal states unrepresentable*.

**Declarative Programming**. *Declarative programming* is a style of programming in which solutions are constructed by specifying goals, rather than specifying the sequential steps necessary to achieve these goals (*what* instead of *how*). Declarative programming is the opposite of imperative programming. Some languages, such as SQL and Datalog, are inherently declarative; but declarative programming can be practiced in any programming language, typically by defining declarative DSLs atop imperative implementations.

**Dependency Injection**. *Dependency injection* refers to a framework, library, language feature, or architectural pattern that facilitates threading dependencies throughout an application, and wiring up those dependencies for different scenarios. Dependency injection is one of the primary architectural needs of large-scale, complex applications.

**Dependent Typing**. *Dependent typing* is a method of defining types that permits types to depend on values. For example, in dependently typed programming languages, one can define the type of vectors whose length is equal to some value. Examples of dependently typed programming languages include Idris, Coq, and Agda. Dependently typed programming languages allow proving more properties about programs at compile-time, albeit at increased development cost.

**Deterministic**. A *deterministic* procedure returns the same output for the same input.

**Domain-Specific Language (DSL)**. A *domain-specific language* (DSL) is a “mini-language” that is designed to solve a certain subproblem in an application. In functional programming, DSLs are generally *embedded*, which means users of these DSL use data types and operators, defined in the host language, to construct programs in the DSL.

**Effect Rotation**. *Effect rotation* refers to the construction of highly polymorphic data types (typically *indexed monads*) that simultaneously support multiple *functional effects*. Each effect supported by the data type is represented with a different type parameter, and each effect may be introduced or eliminated using certain operations. Effect rotation provides much of the benefit of monad transformers, but with substantially improved performance, and in some languages like Scala, significantly better type inference.

**Existential Quantification**. *Existential quantification* asserts that a statement holds for some choice of a given variable. For example, the value `list: List[_]`

is existentially quantified over the `List`

type parameter, asserting that there exists some (unknown) type that describes the type of elements in the list, without specifying what this type is.

**Existential Type**. An *existential type* is a specific, definite type, which is unknown to code interacting with the type. In programming languages, existential types are used to “forget” information that need not be carried around in type parameters. In Scala, abstract type members are always existential types.

**Expression**. An *expression* is a value constructed from the application of functions or operators to other values. The parameters to the functions or operators are called the *terms* of the expression. For example, `a + b`

is an expression, which computes the result of adding the term `a`

to the term `b`

.

**F-Algebra**. An F-algebra is a generalization of algebraic structure that comes from category theory, which makes it possible to represent algebraic laws without universal quantification, using only morphisms. In functional programming, F-algebras appear more directly as interpreters for both tagless-final and free monadic programs (*natural transformations*), and as algebras and coalgebras in recursion schemes.

**First-Class**. *First-class* constructs are those which can be created, manipulated, and abstracted over using the most powerful machinery a language exposes for these tasks. For most programming language, *first-class* means the construct is a *value*. First-class constructs give programmers much more power than second-class constructs. Some constructs which are not first-class can nonetheless be *reified* to obtain some of the benefits of being first-class.

**Flow analysis**. Type-directed *flow analysis* is a process whereby the flow of information in the declaration of a data type or a function is analyzed using type information alone. Performing flow analysis can yield useful information about the implementation of polymorphic declarations. For example, for a function `def foo[A](a: A): A`

(`foo :: a -> a`

), one can tell using flow analysis that the output of the function must have come from its single input parameter, because there is no other way for the function to return a value of the polymorphic type.

**Free Structure**. A *free structure* is a data structure that *reifies* operations of some algebra into a tree-like data structure. Later, the data structure can be traversed, and the operations applied to concrete values—a process called *interpretation* of the free structure. An example free structure is `List`

(`[]`

), which is a free monoid for any type `A`

; that is, for any type `A`

, `List[A]`

(`[a]`

) provides both a neutral value (the empty list) and an append operation (list concatenation). Another example is `Free`

, which provides a free monad for any type constructor `F[_]`

(`f : * -> *`

).

**Function**. A mathematical *function* `f : A => B`

(`f :: a -> b`

) associates every value in a set `A`

(called the *domain*) with a single value in a set `B`

(called the *codomain*). For a given function, this mapping is static (it does not change). In programming languages, the domains and codomains of value-level functions are types, and all such functions are *total* (they map every input to some output), *deterministic* (they map the same input to the same output), and *pure* (they only map inputs to outputs).

**Functional Effect**. A *functional effect* is an immutable data type that describes (or *models*) the computation of one or more values, where the computation may require an additional feature like optionality, logging, access to context (like configuration), errors, state, or input/output. Using effect-specific operations, functional effects can be transformed and composed to model solutions to complex problems out of solutions to smaller problems. The ways of constructing a functional effect, together with the operations on effects of that type, form a DSL, whose capabilities are dictated by the constructors and operations. Frequently, functional effects are *run* or *interpreted* into plain values or into other functional effects. Common functional effects include `Option`

(`Maybe`

), which models missing values; `Either`

, which models failure; and `ZIO`

(`IO`

), which models side-effects, including asynchronous side-effects.

**Functional Programming**. *Functional programming* is a style of programming in which solutions are constructed by defining and applying (mathematical) *functions*. Many programs are not “purely” functional, but contain parts that are written in a functional style, as well as parts that are written in a procedural style. Functional programming can be practiced in statically-typed as well as untyped programming languages.

**Functional-Imperative**. *Functional-imperative* is a hybrid style of programming that uses higher-order functions to embed an imperative model of computation inside functional code. Functional-imperative style relies on *monads* or an equally powerful abstraction to represent the stateful sequentiality of imperative computations.

**Functor**. A `Functor`

is a type class that allows *mapping* the success value of some *functional effect* using a function. Every functor can be regarded as a type of DSL, where the terms in the functor sum type correspond to different instructions in the DSL. Under this view of functors as DSLs, `Functor`

provides a way to change the success value of a DSL “program” into some other success value, by applying a specified function.

**Generalized Algebraic Data Type (GADTs)**. *Generalized algebraic data types* are polymorphic ADTs whose component types may introduce existential types or impose type equality constraints on specific type parameters. GADTs enable easier modeling and use of type-safe DSLs.

**Generic Programming**. *Generic programming* is a style of programming that uses *polymorphism* to “forget” irrelevant details about data types, which allows code to be used across many different data types that share common structure. Generic programming can be thought of as defining a “template” that is then specialized to concrete types.

**Global Reasoning**. *Global reasoning* is a property of some code wherein the correctness of the code cannot be inferred without considering prior application state or all possible inputs.

**Higher-Kinded Types**. *Higher-kinded types*, more precisely called *higher-kinded generics*, is a language feature in which type parameters may have a kind higher than `*`

. The two most mainstream languages with higher-kinded types are *Scala* and *Haskell*.

**Higher-Order**. *Higher-order* refers to higher-order functions, which are functions that accept functions as input, or return functions as output. For example, `map`

on a list is a higher-order function, because it accepts a function as one of its parameters; similarly, the `Monad`

type class is a higher-order type class, because the kind of its type parameter is `(* => *) => *`

, which is a higher-order type-level function.

**Homomorphism**. *Homomorphisms* are a special type of function `f : A => B`

that preserve a given *algebraic structure*. For example, the square function (which returns its input multiplied by itself) is a semigroup homomorphism, because it preserves, for example, the multiplicative semigroup.

**Imperative Programming**. *Imperative programming* is a style of programming in which solutions are constructed from step-by-step instructions, where later instructions can depend on the result of previous instructions. In procedural programming, imperative programming is typically done with side-effecting statements, whereas in functional programming, imperative programming is typically done with *monads*.

**Indexed Monad**. An *indexed monad* is a generalization of `Monad`

for highly polymorphic data types having multiple type parameters, which form ordinary `Monad`

instances for any possible choice of the extra type parameters. Indexed monads allow increased type precision, and allow operations that cannot be expressed with non-indexed monads. Examples of indexed monads included indexed state and `RIO`

(in Haskell), and `ZIO`

(in Scala).

**Indirection**. *Indirection* is any programming language feature (interfaces, type classes, records of functions, module definitions) that allows multiple implementations of some required functionality to be defined and provided to code that requires these capabilities. Indirection facilitates testability, code reuse, and modularity, both in functional programming, and in other paradigms.

**Isomorphism**. An *isomorphism* is an equivalence between two data types that have the same information. An isomorphism is defined by two functions: one to translate from the first data type to the second; and one to translate from the second data type to the first. These functions must satisfy “roundtrip” laws in order for them to form an isomorphism, which demonstrate the two representations contain the same information. In functional programming, many things are considered equal *up to isomorphism*. For example, `(A, Unit)`

and `A`

are *equal up to isomorphism*, meaning these two different types have the same information.

**Kind**. A *kind* describes the structure of a type or type constructor. Monomorphic types like `Float`

and `Boolean`

, which take no type parameters, belong to the set of all types, which is denoted `*`

(“star”). Type constructors like `List`

(`[]`

) and `Option`

(`Maybe`

) belong to the set of all type constructors that take one type and return one type, which is denoted `* => *`

(“star to star”). All kinds higher than `*`

are type-level functions, which accept types (or type constructors) and return types. For example, if you give the `List`

type constructor the type `Boolean`

, then you get back the type representing lists of boolean values. The terminology and notation of kinds allow us to talk about the ways in which different types and type constructors are similar or distinct.

**Lambda**. A *lambda* is an anonymous function, which is a function value that has no name. Because lambdas are values, lambdas may be passed to functions, and returned from functions. All languages that support functional programming provide a way to encode lambdas.

**Lambda Calculus**. The *lambda calculus* is a way of expressing arbitrary computation using only *lambdas*. The lambda calculus is an alternative to Turing machines and other calculi of computation, and gives meaning to the term *functional programming*. There are many different formulations of the lambda calculus, not just one.

**Lenses**. *Lenses* are *optics* that allow getting and setting terms in *product types*. For example, a lens could allow getting and setting the *name* field inside objects of type `Person`

. In the functional context, *setting* a term in a product means creating a new modified product, given the new value for the term, and the old product value.

**Liskov Substitution Principle**. The *Liskov substitution principle* says that if a function accepts an input of type `A`

, then it should be valid to pass the function any subtype of `A`

, without altering the correctness of the function. Similarly, for a function returning an output of type `B`

, it should be valid for the function to return a subtype of `B`

. The Liskov substitution principle enables principled reasoning about subtyping.

**Local Reasoning**. *Local reasoning* is a property of some code wherein the correctness of the code can be inferred locally under specified assumptions, without considering prior application state or all possible inputs.

**Map**. To *map* over a polymorphic data type is to change one type parameter into another type, by specifying a way to transform values of that type. For example, a list of integers can be mapped into a list of strings, by specifying a way to transform an integer into a string. To be well-defined, and to constitute a valid `Functor`

, mapping over any polymorphic data type with an identity function must yield something that is equal to the original value.

**Minimal**. A set of operators is *minimal* if there exist no smaller set of orthogonal operators that has the same expressive power.

**Modular**. A factoring of a solution to a problem is *modular* when it has been divided into independent concerns called *modules*, such that each module knows no more than necessary about other modules. Modularity helps tame the complexity of large-scale software development.

**Monad**. A `Monad`

is an `Applicative`

Functor that allows combining a first *functional effect*, together with a function that takes the success value of the first effect and returns a second effect (*continuation*). Monads represent the essence of imperative programming: do a first thing, and then do this second thing, which depends on the value computed by the first thing. Under the view of functors as DSLs, `Monad`

adds sequential “statements”, where subsequent statements depend on previous ones.

**Monad Transformer**. A *monad transformer* is a data type that adds one functional effect atop any other functional effect. For example, the `OptionT`

(`MaybeT`

) monad transformer adds the effect of optionality to any other functional effect. A monad transformer, when “stacked” atop a monad, itself forms a monad, which allows building up large stacks of monad transformers, each layer adding some desired functional effect. Monad transformers have significant performance overhead in languages like Scala. An alternative to monad transformers is *effect rotation*.

**Monoid**. A monoid is a semigroup equipped with a *neutral element* (often called *zero*), such that appending the neutral element to any other element (on either side) returns that same element unchanged.

**Monomorphic**. *Monomorphic* is the opposite of *polymorphic*, and refers to a function that takes no type parameters (instead, all of its inputs are concrete types), or a data type that takes no type parameters (rather, it defined entirely with concrete types).

**Natural Transformation**. A *natural transformation* is any polymorphic function between *Functors*.

**Nominal Typing**. *Nominal typing* is a method of defining types solely based on their names. Two nominal types are equal if and only if they have the same fully-qualified name. Nominal typing stands in contrast to *structural typing*, in which two types that have different names but the same structure are regarded as the same.

**Onion Architecture**. *Onion architecture* is a method of architecting programs that involves gradually translating business logic into lower-layer levels, until at the edges of the application, logic is translated into system calls. Applications written in the onion architecture bear similarities with multi-staged compilers, where every layer of the onion contains DSLs that are “compiled” into other DSLs.

**Optics**. *Optics* are *values* that allow getting and setting smaller parts of a larger data structure, in a purely functional way. In the functional context, *setting* means to produce a new copy from an old copy, with some modification applied. Optics allow zooming into small parts of very large structures, and making pinpoint modifications, without having to deal with all the boilerplate involved in deconstructing and reconstructing every level of the data structure.

**Orthogonal**. Roughly speaking, a set of operators is *orthogonal* when no operator performs the function of any other operator. This is the functional programming analogue of *Single Responsibility Principle* (SRP). More precisely, a set of operators `S`

is *orthogonal* if there exists no other factoring of the operators `S1`

such that any operator in `S`

can be expressed as a composition of two or more operators in `S1`

.

**Parametric Polymorphism**. Sometimes called *generics*, *parametric polymorphism* is a feature of some programming languages that allows *universally quantifying* a function or a data type over one or more type parameters. Such *polymorphic functions* and *polymorphic data types* are said to be *parameterized* by their type parameters. Parametric polymorphism allows the creation of generic code, which works across many different data types, and generic data types, like collections. Parametrically polymorphic code must behave uniformly across all choice of type parameters, which allows a powerful way of reasoning about such code called *parametric reasoning*.

**Parametric Reasoning**. *Parametric reasoning* is a type of reasoning that enables one to state facts about an implementation of a polymorphic function or polymorphic data type based only on type signatures. Parametric reasoning is typically accomplished using *flow analysis* on polymorphic declarations.

**Partial Function**. A *partial function* is a function that is only defined for a subset of its domain. Partial functions can be modeled as total functions by expanding the codomain to include at least one new value, which indicates the function does not handle some input.

**Polymorphism**. *Polymorphism* is a feature of programming languages that allows a variable or function to take on many different forms. Common types of polymorphism include *parametric polymorphism*, *subtype polymorphism*, and *ad hoc polymorphism*.

**Prisms**. *Prisms* are *optics* that allow getting and setting terms in *sum types*. For example, a prism could allow getting and setting the `Left`

term inside objects of type `Either[A, B]`

(`Either a b`

). In the functional context, *setting* a term in a sum means creating a new sum, given the new value for the term.

**Procedures**. In programming languages, *procedures* are named entities that contain ordered sets of instructions for a machine to perform. Usually called *functions*, *procedures*, or *subroutines* in common parlance, procedures are not necessarily *functions* in the mathematical sense of the word, although all mathematical functions on values constitute valid procedures.

**Procedural Programming**. *Procedural programming* is a style of programming in which solutions are constructed from the construction and invocation of procedures. All procedural programming is *imperative* in nature, although not all imperative programming is *procedural*.

**Product Type**. A *product type* is the composition of `n`

types, referred to as the *terms* of the product, together into a new type, such that a value of the product type contains a value from each of its terms. Structs, classes, records, and tuples are all examples of product types. A table is also an example of a product type, because each row in a table contains a value from each of its columns.

**Profunctor**. A *profunctor* is type class defined over type constructors of two type parameters that describes polymorphic data types that form a `Functor`

in one type parameter, and a `Contravariant`

Functor in the other type parameter. Functions are examples of profunctors, which can be mapped on the output channel, and contramapped on the input channel. Profunctors can be thought of as a generalization of functions, which accept input and produce output, but most profunctors are not functions.

**Projection**. A *projection* is a “lossy” mapping from one set to another set, such that if applied again to the output of itself, returns an equivalent result. An example is pulling the *age* field out of a *Person*, in which case repeated application produces the same *age* field. All extractions of terms from product types can be regarded as projections.

**Property-based Testing**. *Property-based testing* is a method of testing *algebraic laws* by pseudo-randomly generating example values, and testing to see if the laws are satisfied. For example, property-testing could generate many integers `a`

, `b`

, and `c`

to check if `(a + b) + c`

is equal to `a + (b + c)`

. Property-based testing cannot *prove* laws, but it can disprove them, as well as ensure there are no trivial law violations.

**Pure**. A *pure* procedure combines inputs into an output, and does not interact with the world outside the function in any way that can be observed. All pure procedures are *deterministic*, but not all *deterministic* procedures are pure.

**Record**. A *record* contains `n`

fields, each accessed with some *label*, called the *name* of the field, and each with some associated type. All records are product types, although not all product types are records (for example, terms of tuples are accessed by ordinal values, not names).

**Recursive Data**. *Recursive data* is any data type that appears as a value somewhere inside the data type. Common examples of recursive data include linked-lists and trees.

**Recursive Functions**. *Recursive functions* are functions that call themselves. In functional programming, recursive functions allow iteration, like processing elements in a list or accepting socket connections.

**Recursion Schemes**. *Recursions schemes* refers to any of the many different ways to traverse recursive data types, such as folding (catamorphisms) or unfolding (anamorphisms). Typically *recursion schemes* refers to the use of fixed-point data types to factor out recursion from data types, and minimize the boilerplate involved in creating different recursion schemes for different recursive data types. However, fundamentally, any recursive data type can be constructed, deconstructed, and transformed in any of the different schemes.

**Referential Transparency**. *Referential transparency* is a property of functional programs in which any expression may be replaced by the value it computes without changing the behavior of the program. Referential transparency allows refactoring programs without changing their behavior, and is necessary (but not sufficient) for *local reasoning*.

**Reified**. A *reified* construct is some non-value construct (such as a type, a field, or a package) that has been represented as a value. For example, reified generics store the type of generic type parameters as values at runtime. Similarly, lenses are a type of reified field, which provide a way to treat a field of a record as a first-class value, which can be passed around, stored, and transformed.

**Semigroup**. A *semigroup* is a type class with a single binary operator, often called *append* or *combine*, that is *assocative*.

**Side-Effect**. A *side-effect* occurs when evaluation of an expression does anything more than computing a value. Side-effects are interactions that can be observed from outside a procedure or expression. Common side-effects include database access, file access, network access, system calls, modifying mutable memory, or calling procedures that do any of the above.

**State**. *State* refers to any data that is used to iteratively process information, either in a loop, or using recursion.

**Structural Typing**. *Structural typing* is a method of defining types solely based on their structure. Two structural types are equal if and only if they have the same structure. Structural typing stands in contrast to *nominal typing*, in which two types that have the same structure are regarded as different if they have different names.

**Structure**. The *structure* of a data type is the set of statements we know to be true about the data type. Parametrically polymorphic types (as well as `Any`

in Scala) have *no* structure, but we can add structure by requiring these types have *instances* for one or more *type classes*.

**Subtyping**. *Subtyping* is a method of defining types that permits “subset” relations, where one type is defined to be a subset or superset of another type. For example, all dogs are animals, and a type system with subtyping can recognize the fact that a `Dog`

type is a subset of an `Animal`

type.

**Sum Type**. A *sum type* is the composition of `n`

types together in an enumeration type, where each case of the enumeration is referred to as a *term* in the sum type. A value from a sum type contains a value from exactly one of its terms. For example, a value of a `Suite`

enumeration is either `Hearts`

, `Diamonds`

, `Spades`

, or `Clubs`

. In Scala 2.x, enumerations are emulated with `sealed trait`

, where the terms of the sum type are subtypes of the `sealed trait`

.

**Tagless-Final**. *Tagless-final* refers to a way of encoding the interpretation of a DSL using parametric polymorphism. In tagless-final, code written in a DSL is polymorphic in the data type used for interpretation. This polymorphic code is interpreted in different ways by instantiating it to concrete evaluation types. In Scala, *tagless-final* refers almost exclusively to using *indirection* to provide ad hoc operations across polymorphic effect types.

**Total**. A *total* procedure returns an output for every input. Total procedures, unlike partial procedures, always terminate, and they never throw exceptions.

**Traversals**. *Traversals* are *optics* that allow getting and setting elements in collection-like data structures.

**Type**. A *type* is information that exists at compile-time, stored in the computer’s memory as the program is compiling. Types are used by the compiler to describe the structure of variables and functions, to ensure programs are well-defined and consistent. Informally, a type can be regarded as a mathematical set of values; the type `Boolean`

, for example, contains the values *true* and *false*. To ascribe a variable a type in a programming language is to assert the value is a member of the set described by the type, and the act of constructing such a value can be regarded as a proof that the assertion is correct.

**Type Class**. A *type class* is a language-level encoding of an *abstraction*. Type classes can be viewed as functions from some type to an *algebraic structure* for that type. For example, an `Ord`

type class might encode the algebraic structure of total ordering, and might allow us to access ordering operations for types that have this algebraic structure.

**Type Constructors**. A *type constructor* is a type that is itself parameterized by other types. To construct a type, the type constructor must be *fully applied* to all of its parameters, which then results in a type. For example, `List`

(`[]`

) is a type constructor. Given a type, such as `Int`

(`Integer`

), then “passing” that type to the `List`

type constructor then constructs a type: namely, the type of lists with that specified element type. The structure of a type constructor is described by its *kind*.

**Universal Quantification**. *Universal quantification* asserts that a statement holds for all possible choices of a given variable. All *parametrically polymorphic* functions and data types universally quantify over their type parameters, asserting the function or data type has an implementation for all possible choices of the type parameters. For example, the function `def empty[A]: List[A]`

(`empty :: [a]`

) universally quantifies over the type parameter `A`

, asserting that for any element type, the function can produce a list of that element type (namely, the empty list).

**Universal Type**. A *universal type* is any type variable used in *univeral quantification*. In programming languages, universal types are introduced by *parametrically polymorphic* function and data type declarations.

**Value**. A *value* is information that exists at runtime, stored in the computer’s memory as the program is executing. Values are used to hold and transmit information within a program, and across process boundaries, to the operating system, file system, network, and beyond. In programming languages, values are constructed from literals or from *expressions*.

## FAQ

*Question*: Can you define some other term that I find confusing?

*Answer*: Sure, send it on and I’ll add it to the glossary!

*Question*: Wikipedia doesn’t agree with your definitions.

*Answer*: Oh no!

*Question*: I don’t agree with your definitions.

*Answer*: Ok.

*Question*: Change your definitions to what I want!

*Answer*: Nope. But if you have ideas to improve these definitions, please share your feedback!