It's interesting how the term "functor" means completely different things in various programming languages. Take C++ for example. Everyone who has mastered C++ knows that you call a class that implements operator() a functor. Now take Standard ML. In ML functors are mappings from structures to structures. Now Haskell. In Haskell functors are just homomorphisms over containers. And in Prolog functor means the atom at the start of a structure. They all are different. Let's take a closer look at each one.

Functors in C++

Functors in C++ are short for "function objects." Function objects are instances of C++ classes that have the operator() defined. If you define operator() on C++ classes you get objects that act like functions but can also store state. Here is an 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();  // prints "Oh, hello, catonmat"
}

Notice how I was able to call sf() in the main function, even though sf was an object? That's because I defined operator() in SimpleFunctor's class.

Most often functors in C++ are used as predicates, fake closures or comparison functions in STL algorithms. Here is another example. Suppose you have a list of integers and you wish to find the sum of all even ones, and the sum of all odd ones. Perfect job for a functor and for_each algorithm.

#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 << "Sum of evens: " << evenodd.even_sum() << "\n";
    std::cout << "Sum of odds: " << evenodd.odd_sum() << std::endl;

    // output:
    // Sum of evens: 30
    // Sum of odds: 25
}

Here an instance of an EvenOddFunctor gets passed to for_each algorithm. The for_each algorithm iterates over each element in my_list and calls the functor. After it's done, it returns a copy of evenodd functor that contains the sum of evens and odds.

Functors in Standard ML

Vaguely talking in object-oriented terms, functors in ML are generic implementations of interfaces. In ML terms, functors are part of ML module system and they allow to compose structures.

Here is an example, suppose you want to write a plugin system and you wish all the plugins to implement the required interface, which, for simplicity, includes only the perform function. In ML you can first define a signature for plugins,

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

Now that we have defined an interface (signature) for plugins, we can implement two Plugins, let's say LoudPlugin and SilentPlugin. The implementation is done via structures,

structure LoudPlugin :> Plugin =
struct
    fun perform () = print "DOING JOB LOUDLY!\n"
end;

And the SilentPlugin,

structure SilentPlugin :> Plugin =
struct
    fun perform () = print "doing job silently\n"
end;

Now we get to functors. Remember functors in ML take structures as their arguments, so we can write one that takes Plugin as its argument,

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

This functor takes Plugin as P argument, and uses it in the job function, that calls P plugin's perform function.

Now let's use the Performer functor. Remember that a functor returns a structure,

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

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

This outputs,

DOING JOB LOUDLY!
doing job silently

This is probably the simplest possible example of Standard ML functors.

Functors in Haskell

Functors in Haskell is what real functors are supposed to be. Haskell functors resemble mathematical functors from category theory. In category theory a functor F is a mapping between two categories such that the structure of the category being mapped over is preserved, in other words, it's 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 at ML example, a type class in Haskell is like a signature, except it's defined on types. It defines what operations a type has to implement to be an instance of this class. In this case, however, the Functor is not defined over types but over type constructors f. It says, a Functor is something that implements the fmap function that takes a function from type a to type b, and a value of type f a (a type constructed from type constructor f applied to type a) and returns a value of type f b.

To understand what it does, think of fmap as a function that applies an operation to each element in some kind of a container.

The simplest example of functors is regular lists and the map function that maps 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's fmap function is just map and type constructor f is [] - the list type constructor. Therefore the Functor instance for lists is defined as

instance Functor [] where
  fmap = map

Let's see if it really is true by using fmap instead of map in the previous example,

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

But notice that Functor definition does not say anything about preserving the structure! Therefore any sensible functor must satisfy the functor laws, which are part of the definition of the mathematical functor, implicitly. There are two rules on fmap:

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

The first rule says that mapping the identity function over every element in a container has no effect. The second rule says that a composition of two functions over every item in a container is the same as first mapping one function, and then mapping the other.

Another example of Functors that illustrate them the most vividly is operations over trees. Think of a tree as a container, then fmap maps a function over tree values, while preserving the tree's structure.

Let's define a Tree first,

data Tree a = Node (Tree a) (Tree a)
            | Leaf a
              deriving Show

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

Now we can define a Functor over Trees,

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 function g over a Leaf with value v is just a Leaf of g applied to v. And fmap of g over a Node with left l and right r branches is just a Node of fmap applied to the values of left and right branches.

Now let's illustrate how fmap works on trees. Let's construct a tree with String leaves and map the length function over them to find out the length of each leaf.

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

Here I constructed the following tree,

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

And mapped length function over it, producing,

           *
          / \
         /   \
        *     4
       / \     
      /   \
     /     \
    /       \
   5         3

Another way of saying what fmap does is that is lifts a function from the "normal world" into the "f world."

In fact Functor is the most fundamental type class in Haskell because Monads, Applicatives and Arrows are all Functors. As I like to say it, Haskell starts where the functors start.

If you wish to learn more about Haskell type classes, start with the excellent article Typeclassopedia (starts at page 17).

Functors in Prolog

Finally, functors in Prolog. Functors in Prolog are the simplest of all. They refer to two things. The first is the atom at the start of the structure. Here is an example, given an expression,

?- likes(mary, pizza)

the functor is the first atom - likes.

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

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

That's it for functors in Prolog.

Conclusion

This article demonstrated how a simple term like "functor" can refer to completely different things in various programming languages. Therefore when you hear a the term "functor", it's important to know the context it's being mentioned in.

Comments

May 17, 2010, 13:59

Very nice article! It's sad that other popular languages doesn't implement operator()-like

Keep up good work Pete!

assd Permalink
August 06, 2011, 16:21

why? I think it's good thing, using () only produces mess in code. When I see bomb.explode() I now I should expect the object bomb to explode. But bomb() doesn't say me anything. Worst thing, the requirements for () changes, old comment stays and i can find something like:
// this operator explodes the bomb
operator()() { /* explode() */ save_the_world(); }

AP2 Permalink
August 06, 2011, 23:24

Python does - you just need to implement the __call__ method:

class MyClass:
    def __call__(self):
        print "hello"

obj = MyClass()
obj() #prints "hello"
August 08, 2011, 15:05

All functions in Javascript are implicitly C++-functors, but defined in a reverse order.

function foo() {
    foo.abc++;
    alert(foo.abc);
}
foo.abc = 0;

Each run will increment the value and print the new version, but you can also alter that property however and whenever you like, so in Javascript you tend to use real closures for holding state, instead:

var foo = (function() {
    var abc = 0;
    return function() {
        abc++;
        alert(abc);
    };
})();

or you can define objects to instantiate if you need more than one:

function Foo() {
    var abc = 0;
    return function() {
        abc++;
        alert(abc);
    };
}
var foo = new Foo();
robinst Permalink
August 09, 2011, 22:10

Scala also has "()":

class Foo {
  def apply(name: String) {
    println("Hello " + name)
  }
}

val foo = new Foo
foo("Jan")  // prints Hello Jan
May 17, 2010, 14:56

C++ function explanation was very clear.

wheaties Permalink
May 17, 2010, 15:15

You should put down accumulate instead of for_each in your C++ example as for_each is not required to pass the previous functor's state to the next call. That is, you could wind up with even == 0 and odd == 1 instead of 25 and 30.

Roman Permalink
May 17, 2010, 18:09

How would it lose the state? The doc clearly states that for_each(first, last, f) applies f to the result of dereferencing every iterator in the range [first, last).

May 18, 2010, 18:15

The standard just requires a copy of f to be returned. This means that, for instance, the following implementation is perfectly legal:

template< typename InputIterator, typename Function >
Function
for_each( InputIterator first, InputIterator last, Function f )
{
    if ( first != last ) {
        f( *first ) ;
        for_each( first + 1, last, f ) ;
    }
    return f ;
}

This is a typical gotcha for C++ beginners.

(There are also other small oversights in the code, but this is the main one.)

PS: Also, I think that standard-wise the only occurrence of the term "functor" I've seen is in the draft specification for unique_ptr (but I'd have to check if it's still there; if so it ought probably be replaced by "function object"). But of course it's a term in common usage, sometimes referring to classes, sometimes to objects (instances).

May 19, 2010, 00:04

Oops, I forgot to stick to input iterators, sorry. It should of course be:

template< typename InputIterator, typename Function >
Function
for_each( InputIterator first, InputIterator last, Function f )
{
    if ( first != last ) {
        f( *first ) ;
        ++ first ;
        for_each( first, last, f ) ;
    }
    return f ;
}
May 17, 2010, 15:17

Thanks for your explanation. I've recently been programming a lot in Ruby, where you have Procs, Blocks and lambda closures and while working with C++ I really missed the dynamics of these concepts. I think the biggest lack of C++ is that it does not support anonymous function objects. You always have to define a class and override the operator().

C++'s functors are, in my opinion, also not powerful enough for full object oriented use. It is not easy to create a functor for a method call on an object. In Ruby this is solved using Method Objects:

method_object = Person.method(:name)
...
name = method_object.call
Chris Permalink
May 17, 2010, 16:25

Jan, Python, at least, implements this with the __call__(self,*args) method on objects.

roy_hu Permalink
May 17, 2010, 18:50

See also http://stackoverflow.com/questions/2030863/in-functional-programming-what-is-a-functor/2031421#2031421

nizam Permalink
May 17, 2010, 22:07

Nice post. I think the concept of functor originated in mathematics and it would be appropriate for this article to make mention of it. Functors in math: http://en.wikipedia.org/wiki/Functor

Ben Permalink
November 11, 2010, 15:22

The Haskell approach pretty much is the mathematical approach. And the nice thing about Haskell is that while it's extremely faithful to the pure math, but it's also a very powerful programming language, easily as powerful as C++.

I'd recommend the classic intro to Haskell to start with, or Real World Haskell if you prefer something more practical. Once you've got a few working programs under your belt, here's a pretty readable intro to category theory.

Mattias Permalink
May 18, 2010, 14:40

Just to add a bit: C++ functors would typically inherit from std::unary_function or std::binary_function.
In the example in the article it doesn't matter much, but for other cases it does.
It is explained a bit more here:
Benefits of letting functors inherit from std::unary_function...

May 19, 2010, 17:18

In Python any object with a __call__() method may be called using function-call syntax. So any function are objects, just like strings, numbers, lists, and so on is a functor.

August 06, 2011, 23:10

So what you did was show the idioms for implementing functors in three languages, and how c++'s mutability makes it possible to break the mathematical contract and still do useful things.

I don't think you're correct when you say "functors" aren't equivalent in all three languages.

For Prolog though, you really need to think in a different vocabulary. You show the functor predicate unifying F and A with a term. I'm sure there's an idiom for functor usage on par with ML, but I'm not enough of a Prolog wizard to know what it is:)

Dave Phillips Permalink
August 07, 2011, 02:24

Very interesting read. Thanks.

A brief comment on your section on Prolog functors:

You say that functors in Prolog "refer to two things". This is a bit weird to say. Clearly, the second thing is just a convenience predicate that Prolog provides for analyzing structures/terms.

This convenience predicate isn't some separate notion of a functor any more than the =.. operator is. The fact that the predicate is called 'functor' shouldn't be taken too seriously. It could just as well have been called 'analyze'.

A functor in Prolog is the atom at the beginning of a structure. It is defined by its name and its arity.

(BTW, the =.. operator is used to decompose structures into lists. e.g. f(1, 2) =.. [f, 1, 2]. is a true statement.)

God Permalink
August 07, 2011, 02:51

@Will: No.

"Functor" means so many different things i thought it strange to base an article
on the word.

August 07, 2011, 04:24

No what?

No there's not a way to use functors in Prolog that is comparable to their usage in ML? That would be sad.

No functors aren't equivalent in all three mentioned programming languages, ignoring mutability concerns? Well, maybe Haskell enforces some extra constraints, but there's no reason you couldn't conform if you actually needed the mathematical properties that entails.

December 27, 2011, 19:25

I think you've misunderstood.

Peteris's post was about how four different languages have things they call 'functor' that are completely different. He then went on to explain them. None of the things called 'functor' in the post are related except in that they share the same name. 'Functor' is one of these things that, in computing has radically different meanings depending on context.

Back to Prolog though. Prolog has things called 'atom', essentially symbolic identifiers. Prolog allows you to specify the relationship between various atoms, thus the term 'foo(bar, baz)' states that atoms 'bar' and 'baz' have a relationship symbolised by the atom 'foo'. Prolog calls the atom in a term that symbolises the relationship between its arguments the 'functor', though something like 'predicate' would likely have been a less confusing choice.

ben Permalink
August 08, 2011, 04:12

you should consider to get rid of Egyptian brackets. the code will be better to read. and those one.liner are even worst.
don't want to annoy you, just a remark from a random programmer who admires your work!

a random asshole Permalink
August 08, 2011, 12:08

How about you worry about how to write, since you are apparently unable to spell very simple words.

rajiv Permalink
January 16, 2012, 18:13

>> fmap id = id

I think the above identity is not quite right. It has different types on either side of the "=" sign. And I think that's a consequence of the fact that a functor maps the identity of the morphisms of one category to that of another - the two identities belong to different categories, not the same as the above identity indicates.

In the case of lists probably the right identity is
map id = [id]. If I check the types for the list identity

map id :: [b] -> [b]
[id] :: [a -> a]

I'm not quite sure if this makes sense, but it feels right. (I'm a Haskell novice.)

And I have no idea how to express this for general functors.

January 16, 2012, 19:32

It is correct.

Hugs> fmap id [1,2,3]
[1,2,3]
Hugs> id [1,2,3]
[1,2,3]
Hugs> fmap id [1,2,3] == id [1,2,3]
True
October 08, 2012, 13:17

Nice discourse on the C++ functors, which I am currently getting back up to speed on, particularly on retaining functor states. A lot of useful things on this site, so thanks for posting.

March 05, 2013, 14:23

Thanks a lot for your useful script regarding to C++. I´m a fan of C++ since I took part in a C++ Workshop. Therefore I like to learn new things about it.

So thanks again.

November 08, 2013, 12:32

Nice information, many thanks to the author. It is incomprehensible to me now, but in general, the usefulness and significance is overwhelming. Thanks again and good luck!games online

September 10, 2014, 10:16

nice tutorial.

November 13, 2014, 17:49

Priceideas - Find price of Mobiles, Laptops, Cameras, TVs, Appliances and more.

Leave a new comment

(why do I need your e-mail?)

(Your twitter name, if you have one. (I'm @pkrumins, btw.))

Type the word "0day": (just to make sure you're a human)

Please preview the comment before submitting to make sure it's OK.

Advertisements