Applicative functor

Last updated

In functional programming, an applicative functor, or an applicative for short, is an intermediate structure between functors and monads. In Category Theory they are called Closed Monoidal Functors. Applicative functors allow for functorial computations to be sequenced (unlike plain functors), but don't allow using results from prior computations in the definition of subsequent ones (unlike monads). Applicative functors are the programming equivalent of lax monoidal functors with tensorial strength in category theory.

Contents

Applicative functors were introduced in 2008 by Conor McBride and Ross Paterson in their paper Applicative programming with effects. [1]

Applicative functors first appeared as a library feature in Haskell, but have since spread to other languages as well, including Idris, Agda, OCaml, Scala and F#. Glasgow Haskell, Idris, and F# offer language features designed to ease programming with applicative functors. In Haskell, applicative functors are implemented in the Applicative type class.

While in languages like Haskell monads are applicative functors, it is not always so in general settings of Category Theory - examples of monads that are not strong can be found on Math Overflow.

Definition

In Haskell, an applicative is a parameterized type that we think of as being a container for data of the parameter type plus two methods pure and <*>. The pure method for an applicative of parameterized type f has type

pure::a->fa

and can be thought of as bringing values into the applicative. The <*> method for an applicative of type f has type

(<*>)::f(a->b)->fa->fb

and can be thought of as the equivalent of function application inside the applicative. [2]

Alternatively, instead of providing <*>, one may provide a function called liftA2. These two functions may be defined in terms of each other; therefore only one is needed for a minimally complete definition. [3]

Applicatives are also required to satisfy four equational laws: [3]

Every applicative is a functor. To be explicit, given the methods pure and <*>, fmap can be implemented as [3] 

fmapgx=pureg<*>x

The commonly-used notation g<$>x is equivalent to pureg<*>x.

Examples

In Haskell, the Maybe type can be made an instance of the type class Applicative using the following definition: [2] 

instanceApplicativeMaybewhere-- pure :: a -> Maybe apurea=Justa-- (<*>) :: Maybe (a -> b) -> Maybe a -> Maybe bNothing<*>_=Nothing_<*>Nothing=Nothing(Justg)<*>(Justx)=Just(gx)

As stated in the Definition section, pure turns an a into a Maybea, and <*> applies a Maybe function to a Maybe value. Using the Maybe applicative for type a allows one to operate on values of type a with the error being handled automatically by the applicative machinery. For example, to add m::MaybeInt and n::MaybeInt, one needs only write

(+)<$>m<*>n

For the non-error case, adding m=Justi and n=Justj gives Just(i+j). If either of m or n is Nothing, then the result will be Nothing also. This example also demonstrates how applicatives allow a sort of generalized function application.

See also

Related Research Articles

In mathematics and computer science, currying is the technique of translating a function that takes multiple arguments into a sequence of families of functions, each taking a single argument.

In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.

Generic programming is a style of computer programming in which algorithms are written in terms of data types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered in the programming language ML in 1973, permits writing common functions or data types that differ only in the set of types on which they operate when used, thus reducing duplicate code.

In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs involving them. Examples of combinatorial species are graphs, permutations, trees, and so on; each of these has an associated generating function which counts how many structures there are of a certain size. One goal of species theory is to be able to analyse complicated structures by describing them in terms of transformations and combinations of simpler structures. These operations correspond to equivalent manipulations of generating functions, so producing such functions for complicated structures is much easier than with other methods. The theory was introduced, carefully elaborated and applied by Canadian researchers around André Joyal.

In category theory, a branch of mathematics, a monad is a triple consisting of a functor T from a category to itself and two natural transformations that satisfy the conditions like associativity. For example, if are functors adjoint to each other, then together with determined by the adjoint relation is a monad.

In functional programming, a monad is a structure that combines program fragments (functions) and wraps their return values in a type with additional computation. In addition to defining a wrapping monadic type, monads define two operators: one to wrap a value in the monad type, and another to compose together functions that output values of the monad type. General-purpose languages use monads to reduce boilerplate code needed for common operations. Functional languages use monads to turn complicated sequences of functions into succinct pipelines that abstract away control flow, and side-effects.

In computer science, arrows or bolts are a type class used in programming to describe computations in a pure and declarative fashion. First proposed by computer scientist John Hughes as a generalization of monads, arrows provide a referentially transparent way of expressing relationships between logical steps in a computation. Unlike monads, arrows don't limit steps to having one and only one input. As a result, they have found use in functional reactive programming, point-free programming, and parsers among other applications.

This is a glossary of properties and concepts in category theory in mathematics.

In mathematics, specifically in category theory, hom-sets give rise to important functors to the category of sets. These functors are called hom-functors and have numerous applications in category theory and other branches of mathematics.

In computer science, a type class is a type system construct that supports ad hoc polymorphism. This is achieved by adding constraints to type variables in parametrically polymorphic types. Such a constraint typically involves a type class T and a type variable a, and means that a can only be instantiated to a type whose members support the overloaded operations associated with T.

String diagrams are a formal graphical language for representing morphisms in monoidal categories, or more generally 2-cells in 2-categories. They are a prominent tool in applied category theory. When interpreted in the monoidal category of vector spaces and linear maps with the tensor product, string diagrams are called tensor networks or Penrose graphical notation. This has led to the development of categorical quantum mechanics where the axioms of quantum theory are expressed in the language of monoidal categories.

In functional programming, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra.

In many programming languages, map is a higher-order function that applies a given function to each element of a collection, e.g. a list or set, returning the results in a collection of the same type. It is often called apply-to-all when considered in functional form.

In computer programming, an anamorphism is a function that generates a sequence by repeated application of the function to its previous result. You begin with some value A and apply a function f to it to get B. Then you apply f to B to get C, and so on until some terminating condition is reached. The anamorphism is the function that generates the list of A, B, C, etc. You can think of the anamorphism as unfolding the initial value into a sequence.

In mathematics and computer science, apply is a function that applies a function to arguments. It is central to programming languages derived from lambda calculus, such as LISP and Scheme, and also in functional languages. It has a role in the study of the denotational semantics of computer programs, because it is a continuous function on complete partial orders. Apply is also a continuous function in homotopy theory, and, indeed underpins the entire theory: it allows a homotopy deformation to be viewed as a continuous path in the space of functions. Likewise, valid mutations (refactorings) of computer programs can be seen as those that are "continuous" in the Scott topology.

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.

This article describes the features in the programming language Haskell.

<span class="mw-page-title-main">Yesod (web framework)</span>

Yesod is a web framework based on the programming language Haskell for productive development of type-safe, representational state transfer (REST) model based, high performance web applications, developed by Michael Snoyman, et al. It is free and open-source software released under an MIT License.

Idris is a purely-functional programming language with dependent types, optional lazy evaluation, and features such as a totality checker. Idris may be used as a proof assistant, but is designed to be a general-purpose programming language similar to Haskell.

<span class="mw-page-title-main">Functor (functional programming)</span> Design pattern in pure functional programming

In functional programming, a functor is a design pattern inspired by the definition from category theory that allows one to apply a function to values inside a generic type without changing the structure of the generic type. In Haskell this idea can be captured in a type class:

References

  1. ↑ McBride, Conor; Paterson, Ross (2008-01-01). "Applicative programming with effects". Journal of Functional Programming. 18 (1): 1–13. CiteSeerX   10.1.1.114.1555 . doi:10.1017/S0956796807006326. ISSN   1469-7653.
  2. 1 2 Hutton, Graham (2016). Programming in Haskell (2 ed.). pp. 157–163.
  3. 1 2 3 "Control.Applicative".
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.