# 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 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 type of Functor must support a method `fmap`, which maps a function over the element(s) of the Functor.

Functors in Haskell should also obey functor laws, 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 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 Functor, Monad, and Comonad, 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 might yet to be 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`.