Jump to content

Functor (functional programming)

Edit links
From Wikipedia, the free encyclopedia
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
This article is about the design pattern for mapping functions over a generic type. For the term "functor" as used in C++, see function object.
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

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

References

  1. ^ Yorgey, Brent. "Functor > Laws". HaskellWiki. Retrieved 17 June 2023.
  2. ^ "Functors". Functional Pearls. University of Maryland. Retrieved 12 December 2022.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Functor_(functional_programming)&oldid=1283290520"