Hubbry Logo
Functor (functional programming)Functor (functional programming)Main
Open search
Functor (functional programming)
Community hub
Functor (functional programming)
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Functor (functional programming)
Functor (functional programming)
Functor (functional programming)
View on Wikipedia
from Wikipedia
Applying fmap (+1) to a binary tree of integers increments each integer in the tree by one.

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: 

class Functor f where
  fmap :: (a -> b) -> f a -> f b

This declaration says that any instance of Functor must support a method fmap, which maps a function over the elements of the instance.

Functors in Haskell should also obey the so-called functor laws,[1] which state that the mapping operation preserves the identity function and composition of functions: 

fmap id = id
fmap (g . h) = (fmap g) . (fmap h)

where . stands for function composition.

In Scala a trait can instead be used: 

trait Functor[F[_]] {
  def map[A,B](a: F[A])(f: A => B): F[B]
}

Functors form a base for more complex abstractions like applicative functors, monads, and comonads, all of which build atop a canonical functor structure. Functors are useful in modeling functional effects by values of parameterized data types. Modifiable computations are modeled by allowing a pure function to be applied to values of the "inner" type, thus creating the new overall value which represents the modified computation (which may have yet to run).

Examples

[edit]

In Haskell, lists are a simple example of a functor. We may implement fmap as 

fmap f []     = []
fmap f (x:xs) = (f x) : fmap f xs

A binary tree may similarly be described as a functor: 

data Tree a = Leaf | Node a (Tree a) (Tree a)
instance Functor Tree where
   fmap f Leaf         = Leaf
   fmap f (Node x l r) = Node (f x) (fmap f l) (fmap f r)

If we have a binary tree tr :: Tree a and a function f :: a -> b, the function fmap f tr will apply f to every element of tr. For example, if a is Int, adding 1 to each element of tr can be expressed as fmap (+ 1) tr.[2]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Functor (functional programming)

View on Grokipedia
from Grokipedia
In functional programming, a is a f that supports the application of a function to the values it contains, without modifying the structure of f itself, enabling generic transformations over wrapped data or computations. This concept is an adaptation of the from , where a is a mapping between categories that sends objects to objects and morphisms to morphisms while preserving composition and identities. In programming languages like Haskell, the is formalized as a type class with the core method fmap :: (a -> b) -> f a -> f b, which lifts a function from type a to b into one that operates on the functorial structure f. The defining laws for a functor ensure consistent behavior: the identity law states that fmap id == id, meaning applying the identity function leaves the structure unchanged; the composition law requires fmap (f . g) == fmap f . fmap g, preserving the order of function applications. These laws make functors composable and predictable, forming the foundation for higher abstractions like applicative functors and monads in functional programming paradigms. Common instances include the list type [], where fmap behaves like the standard map function to transform each element; the Maybe type, which applies functions only if a value is present (i.e., not Nothing); and effectful types like IO, allowing pure functions to interact with side effects in a structured way. Functors promote abstraction by decoupling data representation from operations on it, facilitating reusable code across diverse contexts such as , handling, and asynchronous computations. This pattern appears in languages beyond , including Scala (via libraries like Cats) and even (through functional libraries), underscoring its role in enhancing modularity and expressiveness in modern .

Definition and Motivation

Definition

In functional programming, a functor is a type class or interface defined for a type constructor FF, providing a single operation, typically named fmap, with the type signature fmap::(a→b)→F a→F b\text{fmap} :: (a \to b) \to F\, a \to F\, b. This operation applies a pure function from type aa to type bb to each value wrapped within the structure F aF\, a, yielding a new structure F bF\, b that retains the original structure of FF. A type constructor FF is a higher-kinded type that accepts a to form a new type, enabling the parameterization of structures such as those representing computations or around values. The role of fmap is to lift such pure functions, allowing them to transform the inner values without directly manipulating the surrounding provided by FF. From a categorical perspective, the functors used in programming are endofunctors, which are functors from a category to itself—in this case, the category of types and total functions, where FF maps types to types and functions to lifted functions preserving composition and identities. Notation for this mapping operation varies by language: Haskell standardizes on fmap, while some languages use map or provide it as a method like F.map in type class-based systems. Instances of the functor type class must satisfy certain laws that constrain the behavior of this operation to ensure predictability and composability.

Motivation

Functors in functional programming arise from the need to abstract common mapping operations across diverse data structures, thereby avoiding the proliferation of ad-hoc implementations for each type. In languages like Haskell, where type classes enable polymorphic behavior, this abstraction unifies operations such as applying a function to elements within lists, trees, or optional values, promoting code reuse and maintainability without duplicating logic for every structure. This approach also facilitates uniform handling of computations that involve contextual effects, such as operations prone to errors or asynchronous results, by allowing functions to be lifted into these contexts without manually unwrapping and rewrapping values each time. The key method, fmap, enables this lifting in a consistent manner across types, streamlining the integration of pure functions into effectful contexts. By emphasizing such abstractions, functors enhance and compositionality inherent to functional paradigms, minimizing required for repetitive transformations and traversals in pure functional programs. This reduces the risk of errors in large-scale developments and supports . Historically, the concept draws from , where functors were introduced as structure-preserving mappings between categories, simplified for programming to emphasize polymorphism over varied structures rather than mathematical rigor.

Functor Laws

Identity Law

The identity law constitutes one of the two fundamental constraints defining lawful functor instances in . It stipulates that mapping the over a functorial value yields the original value unaltered, formally \fmap\id≡\id\fmap \id \equiv \id, where \id\id denotes the and \fmap\fmap is the functor's mapping operation. This equation holds for all values of the functor type, ensuring structural invariance under trivial transformations. This law underscores that \fmap\fmap applies functions purely to the contents of the functor without extraneous modifications to the enclosing structure, thereby upholding the principle that functors serve as transparent contexts for computation. By mandating this behavior, the identity law reinforces the reliability of \fmap\fmap in preserving the semantics of pure functions, preventing implementations from introducing hidden state changes or distortions during mapping. From a category-theoretic perspective, the identity law embodies the requirement that a functor preserves identity morphisms in the category. For an endofunctor FF on the category Hask (the category of Haskell types and functions), this translates to F(\idA)=\idF(A)F(\id_A) = \id_{F(A)} for every type AA, where \idA:A→A\id_A : A \to A is the identity morphism on AA. This preservation property arises because \fmap\fmap induces a natural transformation between the identity bifunctor and the functor FF, with the identity law ensuring the component at \id\id is itself an identity morphism; a proof follows directly from the naturality square commuting for the identity case, where the vertical arrows are identities and horizontals are FF-applied identities, yielding equality by diagram chasing. The identity law carries practical implications for program development and verification in functional languages. It enables equational reasoning by allowing developers to substitute \fmap\id\fmap \id with \id\id confidently, which aids in debugging \fmap\fmap implementations—any deviation signals non-functorial behavior or side effects. Furthermore, this law assures programmers that mapping the identity incurs no computational overhead or observable differences, fostering trust in the functor abstraction for composing transformations without risking unintended mutations.

Composition Law

The composition law for functors states that applying the composition of two functions to a functorial value is equivalent to composing the applications of those functions individually:
fmap (f⋅g)≡fmap f⋅fmap g\mathtt{fmap}\ (f \cdot g) \equiv \mathtt{fmap}\ f \cdot \mathtt{fmap}\ g
where ⋅\cdot denotes and fmap\mathtt{fmap} is the functor's mapping operation. This law ensures that fmap\mathtt{fmap} distributes over , meaning a sequence of transformations on wrapped data can be equivalently expressed as a single composed transformation applied once, without altering the underlying structure. In , this corresponds to the requirement that a FF preserves composition of morphisms: for composable arrows f:X→Yf: X \to Y and g:Y→Zg: Y \to Z in the source category, F(g∘f)=F(g)∘F(f)F(g \circ f) = F(g) \circ F(f) in the target category, ensuring the maps categorical structure faithfully. A proof outline follows directly from the axioms: since FF is defined to act on objects and morphisms while respecting the category's composition operation, the preservation holds by construction, with naturality squares commuting to verify compatibility. In programming contexts like , verification uses equational reasoning: assuming the identity law fmap id≡id\mathtt{fmap}\ \mathtt{id} \equiv \mathtt{id}, the composition law derives from the parametricity (free theorem) of fmap\mathtt{fmap}, which guarantees behavior invariant under type-respecting relabelings, thus only requiring empirical checks for identity in implementations. This law benefits by enabling the composition of pure functions prior to application over structures, which optimizes execution (e.g., fusing multiple maps into one) and improves code readability through predictable chaining of transformations.

Common Functor Instances

Container Types

Container types in functional programming represent data structures that encapsulate multiple values, such as collections or hierarchies, and serve as functors by providing a way to map functions over their contents while preserving the underlying structure. These functors emphasize structure-preserving transformations, where the fmap operation (or equivalent) applies a function to each element without altering the container's shape, size, or order. Common examples include , trees, and arrays, each implementing the interface to enable uniform processing across diverse data structures. Lists are quintessential container functors, where fmap applies a given function to every element in the sequence, maintaining the list's length and order. For instance, applying the function that increments integers to the [1, 2, 3] yields [2, 3, 4], demonstrating how the transformation affects only the values while the sequential remains intact. This behavior aligns with the general for linear containers, allowing operations like filtering or transforming data streams without disrupting their positional relationships. Tree functors extend this mapping to hierarchical structures, recursively applying the function to all nodes while preserving the tree's topology, such as branching patterns and depths. In a binary tree, for example, fmap would transform the value at each node and propagate the operation to subtrees, ensuring the overall shape—defined by parent-child connections—stays unchanged. Arrays, as fixed-size linear containers, function similarly to lists but with bounded capacity, where mapping adjusts elements in place without modifying the array's dimensions or indices. These container functors satisfy the two fundamental functor laws, ensuring predictable and composable behavior. The identity law holds because applying the via fmap leaves the container unchanged; for like [1, 2, 3], fmap id [1, 2, 3] returns [1, 2, 3], with analogous results for trees and arrays where structure and elements remain unaltered. The composition law is upheld as mapping a composed function f . g equals applying g followed by f; in , fmap (f . g) xs = fmap f (fmap g xs), and this chains transformations recursively in trees or across array elements without altering semantics. These laws verify that functors operate as pure mappings, enabling reliable abstraction over container varieties.

Computational Types

Computational types in functional programming represent structures that encapsulate single values or computations with potential effects, such as absence, errors, or side effects, rather than collections of multiple values. These types can be made into functors by defining a mapping operation that transforms the contained value or result while preserving the computational , allowing pure functions to be lifted over the effects without triggering sequencing or additional computations. The Maybe type, also known as Option in languages like Scala and , is a quintessential example of a computational functor for handling optional values. It consists of two constructors: Just (or Some) containing a value, and (or None) indicating absence. The functor mapping, often called fmap, applies a function to the value if present, yielding Just of the transformed value, while returning unchanged if absent. For instance, applying the function that increments by 1 to Just 5 results in Just 6, demonstrating how fmap isolates the transformation to the successful case. Similarly, the Either type, sometimes called Result in , serves as a for error-handling computations, typically biased toward the right (success) side. It has Left for errors and Right for successful values; fmap operates only on the Right value, applying the function to produce a new Right, while propagating Left values unchanged to maintain error information. This right-biased design ensures that transformations chain over successful paths without altering failure modes, as seen when mapping a length function over Right "hello" yields Right 5, but Left "error" remains Left "error". Types like in or in Scala represent effectful computations, such as input/output operations or asynchronous promises, and form functors by lifting s to act on their eventual results. For , fmap composes a with an IO action to produce a new action that applies the function post-execution, without introducing sequencing between effects. In Scala's , the method similarly transforms the future value upon completion, enabling deferred application of pure logic to asynchronous results. This approach allows effectful types to integrate seamlessly with pure functional transformations. These computational functors satisfy the standard functor laws, ensuring predictable behavior. The identity law holds such that mapping the over the structure yields the original unchanged, preserving presence in Maybe, success in Either, or the effect in IO without alteration. The composition law ensures that mapping a composed function equals composing the mappings of individual functions, allowing successful transformations to chain reliably while respecting absences, errors, or deferred executions.

Language-Specific Implementations

Haskell

In , the Functor type class is defined in the Data.Functor module as class Functor f where fmap :: (a -> b) -> f a -> f b, where fmap applies a function to the values contained within a structure of type f, preserving the structure itself. The minimal complete definition requires only fmap, though an additional method (<$) :: a -> f b -> f a is often provided, which replaces all values in the structure with a constant value a. Standard instances of Functor in Haskell's base library include common types such as ([]), the Maybe type for optional values, Either e for error-handling computations, and IO for input/output actions. For newtypes wrapping existing functors, instances can be automatically derived using the GeneralizedNewtypeDeriving language extension, allowing fmap to be lifted through the wrapper without manual implementation. Syntactic conveniences enhance usability: for lists, fmap is aliased as the familiar map function in the Prelude, enabling direct application to collections. Historically, functions like liftM from Control.Monad provided monadic lifting of functions, serving as aliases for fmap in monadic contexts, though they are now considered deprecated in favor of the more general Functor and Applicative interfaces. Haskell emphasizes equational reasoning for verifying that Functor instances satisfy the identity and composition laws, relying on the language's purity to enable such proofs and testing frameworks like QuickCheck for property-based validation.

Scala

In Scala, functors are implemented through a combination of built-in methods in the and type class abstractions in external libraries, reflecting the language's hybrid functional and object-oriented . Unlike Haskell's purely functional type classes, Scala's approach leverages implicits to enable ad-hoc polymorphism, allowing seamless integration of functorial operations into object-oriented codebases. Scala's provides native map methods for common container types, enabling functor-like behavior without additional dependencies. For instance, List[A] supports def map[B](f: A => B): List[B], allowing transformations such as List(1, 2, 3).map(_ + 1) to yield List(2, 3, 4). Similarly, Option[A] defines def map[B](f: A => B): Option[B], preserving the optional structure; Either[L, A] offers a right-biased def map[B](f: A => B): Either[L, B] for handling disjunctions; and Future[T] includes def map[S](f: T => S)(implicit executor: ExecutionContext): Future[S] for asynchronous computations. These methods adhere to functor principles by applying functions within their contexts while maintaining the original structure. For more advanced and extensible functor support, the Cats library defines a type class trait Functor[F[_]] that abstracts over mappable type constructors. The core method is def map[A, B](fa: F[A])(f: A => B): F[B], which lifts a pure function into the context F. An example instance for Option is:

implicit val optionFunctor: Functor[Option] = new Functor[Option] { def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f) }

implicit val optionFunctor: Functor[Option] = new Functor[Option] { def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa.map(f) }

This allows generic code to operate uniformly across types like List, Option, and Future via implicit resolution. Cats employs Scala's implicit parameters to facilitate ad-hoc polymorphism, permitting users to define instances for custom types and have them automatically resolved in generic functions. For a custom wrapper [Box](/page/Box)[A], one can provide:

implicit val boxFunctor: [Functor](/page/Functor)[Box] = new [Functor](/page/Functor)[Box] { def map[A, B](fa: Box[A])(f: A => B): [Box](/page/Box)[B] = [Box](/page/Box)(fa.value.map(f)) }

implicit val boxFunctor: [Functor](/page/Functor)[Box] = new [Functor](/page/Functor)[Box] { def map[A, B](fa: Box[A])(f: A => B): [Box](/page/Box)[B] = [Box](/page/Box)(fa.value.map(f)) }

Functions expecting a Functor[F] then work transparently, such as Functor[F].map(fa)(f), enhancing in mixed paradigms. To ensure functor instances comply with the identity and composition laws, Cats integrates with testing frameworks via the cats-laws module and Discipline library, which uses ScalaCheck for property-based testing. Developers extend FunSuiteDiscipline from ScalaTest and invoke checkAll("FunctorLaws", FunctorTests[F].functor[A, B, C]) to verify laws like fa.map(identity) == fa and fa.map(f.andThen(g)) == fa.map(f).map(g) against generated inputs. This setup confirms law adherence for both standard and custom instances.

Other Languages

In languages beyond those with strong functional programming roots, functor-like operations appear as built-in methods or functions that enable mapping over data structures, though often without the polymorphic abstraction provided by type classes. Java's Stream API, part of the java.util.stream package since Java 8, offers a map method that applies a Function to each element in a stream, yielding a new stream of transformed elements. This supports functorial transformation for collections and sequences in a declarative style, but Java's type system relies on generics without higher-kinded types, preventing a unified functor interface across disparate types like Optional or streams. JavaScript provides similar functionality through Array.prototype.map, which iterates over an array's elements, applies a callback function to each, and returns a new array containing the results, preserving the array's length and structure. For asynchronous contexts, Promise.prototype.then allows chaining transformations on resolved values, treating promises as containers for future results in a way that resembles functor mapping. These methods draw inspiration from functional paradigms but operate within JavaScript's prototype-based and dynamic typing, lacking formal type-level enforcement. Python's built-in function takes an iterable and a function, applying the latter to each item to produce an of results, which can be consumed lazily. The functools module complements this with higher-order utilities like partial for , enabling chained mappings, though Python's dynamic nature and absence of type classes mean functors remain rather than parametrically polymorphic. In Rust, the standard library's trait includes a map method that adapts an existing by applying a closure to its items, producing a std::iter::Map wrapper that implements for the transformed sequence. This provides functor-like behavior for traversal and transformation, but Rust's current does not support higher-kinded types, restricting generic functor definitions to workarounds like trait bounds or associated types rather than direct abstraction over type constructors.

Relation to Other Concepts

Applicative Functors

Applicative functors extend the abstraction by providing mechanisms to introduce pure values into a computational context and to apply functions embedded within that context to arguments in the same context, enabling effectful computations while preserving structural independence. Formally, an applicative functor for a type constructor FF includes the operations pure :: a -> F a, which lifts a value into the functorial structure without effects, and (<*>) :: F (a -> b) -> F a -> F b (often denoted as ~ in theoretical discussions), which sequences two effectful computations by applying the function from the first to the value from the second. This builds directly on the 's fmap by deriving it as fmap f u = pure f <*> u, allowing applicative functors to inherit functorial mapping while adding applicative structure for more expressive combinations. The applicative interface facilitates the construction of compound effects where the structure of the computation remains fixed and independent, contrasting with more flexible but potentially more complex sequencing. For instance, <*> combines effects in a context-preserving manner, enabling parallel or non-dependent application of operations within the , such as validating multiple inputs simultaneously without one influencing the choice of another. This independence makes applicatives suitable for scenarios like or validation where effects are uniform and non-sequential, promoting composable and predictable code. A key distinction lies in handling effects: applicatives support s with fixed, non-dependent structures, whereas monads permit the result of one to dynamically influence subsequent ones. Common instances illustrate this ; for the Maybe , which models optional values and , pure yields Just x, and <*> propagates Nothing if either argument is Nothing, effectively short-circuiting on while applying successful functions otherwise. For lists, representing non-determinism or collections, pure yields [x], a singleton list, and <*> computes the by applying each function in the first list to each argument in the second, enabling vectorized operations like generating all combinations.

Monads

A monad in is a structure that extends a by providing two additional operations: return :: a -> m a, which injects a pure value into the monadic , and >>= :: m a -> (a -> m b) -> m b (), which sequences a monadic with a function that produces another monadic value, allowing computations to be chained while preserving . This enables the composition of effectful operations in a pure functional setting, where the monadic type m encapsulates effects such as state or without violating . Every monad is a , with the functorial fmap derivable as fmap f m = m >>= return . f, but monads go further by enforcing an order on effects through , which functors alone cannot achieve since they only support independent mapping over contained values. The bind operation thus introduces sequencing, permitting dependent computations where the output of one step influences the input to the next within the monadic context. Monads are particularly useful for simulating imperative-style programming in functional languages. For instance, the state monad, defined as newtype State s a = State { runState :: s -> (a, s) }, threads an implicit state s through computations using operations like get :: State s s to retrieve the state and put :: s -> State s () to update it, allowing sequences of stateful actions via bind without explicit state passing. A simple example computes the sum of numbers while tracking a counter:

haskell

import Control.Monad.State sumWithCounter :: [Int] -> State Int Int sumWithCounter xs = do foldM (\acc x -> do modify (+1) -- increment counter return (acc + x)) 0 xs -- Usage: runState (sumWithCounter [1,2,3]) 0 == (6, 3)

import Control.Monad.State sumWithCounter :: [Int] -> State Int Int sumWithCounter xs = do foldM (\acc x -> do modify (+1) -- increment counter return (acc + x)) 0 xs -- Usage: runState (sumWithCounter [1,2,3]) 0 == (6, 3)

This yields the sum 6 and final counter 3, demonstrating how bind chains state updates. Similarly, the IO monad handles side effects like input and output by sequencing actions that interact with the external world, ensuring effects occur in a predictable order. Its bind operation composes IO actions, such as reading input and producing output, which functors cannot sequence due to the non-pure nature of effects. A basic example echoes a character:

haskell

main :: IO () main = do c <- getChar putChar c

main :: IO () main = do c <- getChar putChar c

Here, bind ensures the putChar follows getChar exactly, isolating side effects from pure code. Monad instances must satisfy three laws that extend the functor laws by ensuring consistent sequencing: left identity (return a >>= k ≡ k a), right identity (m >>= return ≡ m), and associativity ((m >>= k) >>= l ≡ m >>= (\x -> k x >>= l)). These laws, which build on functor identity and composition by incorporating the monadic context, guarantee that monadic compositions behave as expected, facilitating modular and composable effectful programs.

References

  1. https://hackage.haskell.org/package/base/docs/Data-Functor.html
  2. https://ncatlab.org/nlab/show/functor
  3. https://www.baeldung.com/scala/functors-functional-programming
  4. https://github.com/fantasyland/fantasy-land
  5. https://ncatlab.org/nlab/show/endofunctor
  6. https://typelevel.org/cats/typeclasses/functor.html
  7. https://dl.acm.org/doi/10.1145/75277.75283
  8. https://pages.cs.wisc.edu/~jcyphert/categoryTheoryNotes/basics/2_Functors.pdf
  9. https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Functor.html
  10. https://www.haskell.org/wikiupload/e/e9/Typeclassopedia.pdf
  11. https://bartoszmilewski.com/2015/01/20/functors/
  12. https://cs.princeton.edu/~dpw/cos441-11/notes/slides09-functors.pdf
  13. https://cs.stackexchange.com/questions/119777/functor-laws-and-natural-transformations-in-haskell
  14. https://wiki.haskell.org/Typeclassopedia
  15. https://learnyouahaskell.com/functors-applicative-functors-and-monoids
  16. https://blog.ploeh.dk/2018/08/06/a-tree-functor/
  17. https://www.haskell.org/haskellwiki/Functor
  18. https://ghc.gitlab.haskell.org/ghc/doc/users_guide/exts/newtype_deriving.html
  19. https://www.haskell.org/haskellwiki/equational_reasoning_examples
  20. https://typelevel.org/cats/typeclasses.html
  21. https://docs.scala-lang.org/overviews/core/futures.html
  22. https://typelevel.org/cats/typeclasses/lawtesting.html
  23. https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html
  24. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/map
  25. https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Promise/then
  26. https://docs.python.org/3/library/functions.html#map
  27. https://doc.rust-lang.org/std/iter/struct.Map.html
  28. https://users.rust-lang.org/t/does-rust-really-need-higher-kinded-types/5531
  29. https://hackage.haskell.org/package/base/docs/Control-Applicative.html
  30. https://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf
  31. https://www.haskell.org/haskellwiki/Monad
  32. https://wiki.haskell.org/State_Monad
  33. https://www.haskell.org/tutorial/io.html
  34. https://wiki.haskell.org/Monad_laws
Add your contribution
Related Hubs
User Avatar
No comments yet.