Functor (functional programming)

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 for a generic type to apply a function inside without changing the structure of the generic type.

This idea is encoded in Haskell using type class

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

with conditions called functor laws,

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

In Scala higher kinded types are 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, Monad, and Comonad, all of which contain a canonical functor structure. Functors are useful in modeling functional effects to apply a function to computations that did not yet finish.

In C++, the name functor is commonly used to refer to a function object, even though the ISO/IEC 14882 standard specification itself exclusively uses the latter term.

Examples

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

fmap f []     = []
fmap f (x:xs) = (f x) : map 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, we may use fmap f tr to apply f to all elements of tr. For example, if a is Int, we can add one to each element of tr using fmap (+1) tr.

External links

• Section about Functor in Haskell Typeclassopedia
• Chapter 11 Functors, Applicative Functors and Monoids in Learn You a Haskell for Great Good!
• Documentation for Functor in Cats library
• Section about Functor in lemastero/scala_typeclassopedia