Functors in programming languages

Interestingly, the term " functor " means completely different things in different programming languages. Take, for example, C ++ . Anyone who has mastered C ++ mastery knows that the class that implements operator() is called a functor. Now take the Standard ML . In ML, functors map structures to structures. Now Haskell . In Haskell, functors are simply a homomorphism over categories. And in Prolog, a functor means an atom at the beginning of a structure. They all differ. Let's take a closer look at each of them.

Functors in C ++

Functors in C ++ are short for " functional objects ". The functional object is an instance of the class C ++, in which operator() defined. If you define an operator() for a C ++ class, then you get an object that acts as a function, but can also store a state. For example,

 #include <iostream> #include <string> class SimpleFunctor { std::string name_; public: SimpleFunctor(const char *name) : name_(name) {} void operator()() { std::cout << "Oh, hello, " << name_ << endl; } }; int main() { SimpleFunctor sf("catonmat"); sf(); //  "Oh, hello, catonmat" } 

Note that we can call sf() in the function main , although sf is an object. This is because operator() defined for it in the SimpleFunctor class.

Most often, functors in C ++ are used as predicates, pseudocolinks, or comparison functions in STL algorithms. Here is another example. Suppose you have a list of integers and you want to find the sum of all even numbers and the sum of all odd numbers. The ideal problem for the functor and for_each .
')

 #include <algorithm> #include <iostream> #include <list> class EvenOddFunctor { int even_; int odd_; public: EvenOddFunctor() : even_(0), odd_(0) {} void operator()(int x) { if (x%2 == 0) even_ += x; else odd_ += x; } int even_sum() const { return even_; } int odd_sum() const { return odd_; } }; int main() { EvenOddFunctor evenodd; int my_list[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; evenodd = std::for_each(my_list, my_list+sizeof(my_list)/sizeof(my_list[0]), evenodd); std::cout << " : " << evenodd.even_sum() << "\n"; std::cout << " : " << evenodd.odd_sum() << std::endl; // : //  : 30 //  : 25 } 

Here, an EvenOddFunctor instance EvenOddFunctor passed to for_each . for_each is iterated over each element in my_list and calls a functor. After that, it returns a copy of the evenodd functor, which contains the sum of even and odd elements.

Functors in Standart ML

It is difficult to formulate in terms of OOP: functors in ML are common implementations of interfaces. In terms of ML, functors are part of a system of ML modules and they allow to assemble structures.

For example, suppose you want to write a plug-in system, and you want all plug-ins to implement the necessary interface, which, for simplicity, includes only the function perform . In ML, you must first set the signature for the plugins,

signature Plugin =
sig
val perform : unit -> unit
end ;

Now that we have defined the interface (signature) for plug-ins, we can implement two plug-ins, say, LoudPlugin and SilentPlugin . Implementation is done through structures

structure LoudPlugin :> Plugin =
struct
fun perform ( ) = print "PERFORM A JOB VOLUME! \ n"
end ;

And SilentPlugin,

structure SilentPlugin :> Plugin =
struct
fun perform ( ) = print "do the task quietly \ n"
end ;

Now we are closer to the functors. Functors in ML take structures as arguments, so we can write that Plugin is required as an argument,

functor Performer ( P : Plugin ) =
struct
fun job ( ) = P. perform ( )
end ;

This functor takes a Plugin as an argument P and uses it for the job function, which calls the perform function on the plugin P
Now let's try using the Performer functor. Remember that the functor returns a structure,

structure LoudPerformer = Performer ( LoudPlugin ) ;
structure SilentPerformer = Performer ( SilentPlugin ) ;

LoudPerformer . job ( ) ;
SilentPerformer . job ( ) ;

Will be displayed

  We carry out the task is loud!
 perform the task quietly 

This is most likely the simplest example of Standard ML functors.

Functors in Haskell

Functors in Haskell are what real functors should be. Haskell functors are very similar to the math functors from category theory. In category theory, the functor F is a mapping between categories, such that the structure of a category is preserved or, in other words, it is a homomorphism between two categories.

In Haskell, this definition is implemented as a simple type class,

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

Looking back, for example, on ML, the Haskell type class is similar to the signature, except that it is defined for the type. It determines which operations the type must implement to be an instance of this class. In this case, however, the Functor defined not on types, but on a constructor of type f . This means Functor is what implements the fmap function, which accepts a function (accepting type a and returning type b ) and a value of type fa (type constructed from a constructor of type f , applied to type a ) and returns a value of type fb .

To understand what he is doing, think of fmap as a function that applies an operation to every element in a container.

The simplest example of functors is ordinary lists and the map function, which applies a function to each element in the list.

Prelude> map (+1) [1,2,3,4,5]
[2,3,4,5,6]

In this simple example, the Functor function of fmap is just a map and the constructor of type f is [] - the constructor of the list type. Therefore, Functor , for example, for lists is defined as

instance functor [ ] where
fmap = map

Let's see what's really true, using fmap instead of map ,

Prelude> fmap (+1) [1,2,3,4,5]
[2,3,4,5,6]

But notice that the definition of Functor says nothing about preserving the structure! Therefore, any normal functor must implicitly satisfy the laws of functors, which are part of the definition of mathematical functors. There are two fmap rules:

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

The first rule states that the mapping of the identical function to each element in the container has no effect. The second rule says that the composition of two functions on each element in the container is the same as the display of the first function, and then the display of the second.

Another example of functors that illustrates them most clearly is tree operations. Think of the tree as a container, and then apply the fmap function to the tree values, keeping the tree structure.

Let's first define a tree

data Tree a = Node ( Tree a ) ( Tree a )
| Leafa
deriving show

This definition says that the type of a Tree (tree) is either a Node (branch) of two Tree (left and right branches) or Leaf (leaf). The deriving Show expression allows us to inspect the tree through the show function.

Now we can define Functor above Tree

instance functor tree where
fmap g ( Leaf v ) = Leaf ( g v )
fmap g ( Node l r ) = Node ( fmap g l ) ( fmap g r )

This definition says that fmap of g over Leaf with a value of v is just Leaf of g applied to v . And fmap from g over Node with the left branch l and right r is just the Node from fmap applied to the values ​​of the left and right branch.

Now let's illustrate how fmap works with trees. Construct a tree with string ( String ) leaves and apply the length function above them to find out the length of each sheet.

Prelude> let tree = (Node (Node (Leaf "hello") (Leaf "foo")) (Leaf "baar"))
Prelude> fmap length tree
Node (Node (Leaf 5) (Leaf 3)) (Leaf 4)

Here we have built the following tree

  *
           / \
          / \
         * "baar"
        / \
       / \
      / \
     / \
  "hello" "foo" 

And the length mapping above it gives us

  *
           / \
          / \
         * four
        / \     
       / \
      / \
     / \
    5 3 

Another way to say that fmap does - displays (in the original - raises ) a function from the “normal world” to the “ f world”.

In fact, the functor is a fundamental type class in Haskell, since Monads, applicative functors and arrows are all functors. I would say that Haskell starts where the functors start.

If you want to learn more about Haskell type classes, start with the excellent Typeclassopedia article (starting on page 17).

Functors in Prolog

Finally, functors in Prolog. Functors in Prolog are the simplest of all. Two examples can be considered. The first is the atom at the beginning of the structure. For example, take the expression

? - likes ( mary , pizza )

the functor is the first atom - likes .

The second is a built-in predicate called functor . It returns the arity and structure functor. For example,

? - functor ( likes ( mary , pizza ) , Functor , Arity ) .
Functor = likes
Arity = 2

Here you have functors in Prolog.

Conclusion

This article shows how such a simple term as a “functor” can refer to completely different things in different programming languages. Therefore, when you hear the term “functor,” it is important to know the context in which it is used.

Original article: www.catonmat.net/blog/on-functors

And there is such a thing ... I was told here that, it turns out, the person whose article I translated is on Habré =)
And they say that part by Prolog in the article is erroneous .