# Functors

What is a `List`? List is a notion of an ordered sequence of elements. It could be empty, it could be a singleton. It is common to refer to a list as an instance of a general collection, an ordered one.

Even more generally, a list is a different (higher) level of abstraction over its elements. A collection or a container are only names, analogues, metaphors. Nevertheless, a List is a generalization of a different kind or level - an aggregate, a composition. It the real, physical world is a generalization of a `Structure`. It is a structure. Data-structure.

Mapping is the notion initially unrelated to Lists. First it has been used to generalize a mathematical function, which maps its argument to a value. A certain transformation on numbers. Same input, same output. Always. This is what a mathematical function is - a transformation, a mapping.

The notion of mapping over a List is about applying a function to each element in a list without altering the structure itself. The applied function does not even know that it is being applied to any structure, if you wish. The `map` "enzyme" which does application do.

In CS `map` as a function on lists, so it knows about List structure. Its level of abstraction is List structures and functions on elements. Its domain is lists and its range is lists.

```map (+1) []
map (+1) [1]
map (+1) [1,2]
```

This notion has been generalized from Lists to any structures which could be mapped-over. The thing which could be mapped over something is a being called a Functor. An abstract entity.

The `map` function must know how to apply a given function `f` to elements of a structure. So it must be defined (specialized) for each kind of possible structure (an aggregate). The whole notion is generalized as a type-class of Functors.

Traditionally `map` is a function of arity 2. It takes a function and an aggregate (data-structure). But if we partially apply `map` to a function we could get a function on aggregates.

```Prelude> :t map (+1)
map (+1) :: Num b => [b] -> [b]
```

So, `(map f)` is called a Functor over a certain type, while `f` is a function on values.

In Haskell currying is implicit, so every function has exactly one argument. Explicit application of a curried function looks like this

```(map (+1)) [1,2]
```

There are laws or constraints, which ensure that mapping of a function as an operation is consistent. The first law states that application of identity does not alter the aggregate.

```map id = id
```

and ideed

```Prelude> map id [1,2,3] == id [1,2,3]
```

The law second states that applying a function composition (a pipeline) is the same as applying these functions separately in the same order. Enzymes on DNA behave in this way.

```map (g . f) = map g . map f
```

Together these constraints enforce consistency of mapping as a process (a single operation).

Return and join are parts of a type-class interface.

```return :: a -> M a
```
```join :: M M a -> M a
```

Notice that domain and range of Functors are different from the domain and range of functions on elements. Functor could be seen as a wrapper over a function, or an adapter for a particular aggregate or a structure.

Implementation of this is a so-called type-class. A higher-level type abstraction over types. Instances of a type-class are specialized types for each particular aggregate or a structure.

So, to apply a function on element to a whole aggregate, promote it into a corresponding functor and apply a functor to an aggregate to produce a new transformed one of the same kind.

This is a useful generalization on the level of types.