wiki:FunctionalProgramming/Functors

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.

Last modified 3 years ago Last modified on Jan 2, 2018, 8:47:22 AM
Note: See TracWiki for help on using the wiki.