A functor is a thing that can be mapped over. For example:

    map abs [-1, 2, 3] => [1, 2, 3]

Arrays are the simplest example, but it looks like an iterable. However functors retain shape whereas iterables don't. For example if we had a tree (represented visually):

    oak = -1
          / \
         2   3

If we used oak as an iterable, we would lose the structure of the tree:

    map abs iter(oak) => [1, 2, 3]

However if tree belongs to the functor typeclass (i.e. implements functor interface), then:

    map abs oak => 1
                  / \
                 2   3

The alternatives to functors are:

1. mutate the existing data structure

2. copy a new one and then mutate (two passes)

3. create a new one while mutating (one pass, increased complexity / bugs)

>However functors retain shape whereas iterables don't.

Wow. Such a simple sentence yet this is the first time I have read it, and it makes the concept much more clear than hundreds of articles before did. Thank you!

I wish all FP features would be explained so simply.

You can build a bit of mathematical intuition for the concept now that you get the basic idea. Try and work out from the functor laws why functors preserve shape. The laws are very straightforward:

    map id c = id c

(Mapping the identity function is the same as simply applying the identity function -- or with a little more category theory, the functor maps the identity function in the base category to the identity function in the functor's category)

    map f (map g c) = map (f . g) c

The second law is also simple -- mapping one function over the container then mapping another function is exactly the same as mapping the composition of the functions over the container. This one is the basis of stream fusion, a very important optimization, that allows you take two traversals of a container and turn them automatically into just one traversal.

The preservation of structure follows from just these two laws and parametricity (The element type of the containers is generic and therefore unknown, this greatly restricts what operations are available on the elements of the container. You can't, for example, conjure up a new value of the element type to insert.). I strongly recommend trying to figure out how.

Though if you take this intuition too far it tends to break down, for instance IO and ST both define functor instances but it doesn't really make sense to talk about a functor over IO preserving shape.

I get it now, thank you for this great explanation, and all the other explanations as well. I think it warrants its own wikipedia page.

The name "Functor" can be confusing; it's a thing you apply a function to, not a function itself.

A Functor is a type t parameterized by some other type a, such that if you have a function from type a to type b, you can apply that function to a t of a and get a t of b.

Most commonly, a functor will be a container of values of type a, and the mapping consists of applying the function to each value, resulting in a container of values of type b.

Other common functors include a computation that returns type a (use composition to apply the function to the result to get a computation that returns type b), or a possibly null pointer to type a (map null to null, map pointer to a to pointer to b).

In an alternate universe where functional programming was invented by programmers rather than mathematicians, map would probably be called something like convertWith and a functor would probably be called something like a convertible.

If you think of a function as being a way of converting from one kind of thing to another, then a functor is an object which has a number of things which you can convert to some other kind (a number which may be one or zero), using a method of your choice, and map is the name of the method you use to do that.

In Java we would call it "Mappable". A Mappable interface would have one method: map(). It hasn't been all that useful until recently due to lack of closures, but perhaps it would make sense in Java 8?

"Functor" is a terrible name that only a mathematician could like.

Just be thankful they didn't name it "Carnap" after the guy who introduced the idea. At least "functor" is moderately descriptive.

Remind me: can you declare a Java interface with a method signature that returns the same type as the class that eventually implements the interface? You wouldn't want the map method on mappable to simply return another Mappable, because that could be any other Mappable (i.e. a CustomList could implement map to return a CustomTree, when the functor concept requires it to return another CustomList).

You can't do it directly, but there is a standard idiom for doing something like that - define the interface like this:

  interface Functor<A, R extends Functor<A, R>>

And then in the implementing class, bind R to the implementing class:

  class Option<A> implements Functor<A, Option<A>>

However, this doesn't let you write an actual functor. Try to write the map method on it:

    class Option<A> implements Functor<A, Option<A>> {
        private final A value;
    
        public Option(A value) { this.value = value; }
    
        @Override
        public <B> Option<A> map(Function<A, B> fn) {
            // er, i want to return an Option<B>, not an Option<A>
        }
    }

The problem is that you don't want to return an instance of the type of the receiver, you want to return an instance of a similar type with a different type parameter (Option<B> rather than Option<A>).

You would be absolutely fine if your functions were functions from values of some type to other values of that type (eg functions from integers to integers), because then A = B and you can get away with this. But there's no way to extend this hack to let you return an Option<B> from map.

The closest you can get in Java is probably this:

    interface Functor<A, R extends Functor<?, R>>

    class Option<A> implements Functor<A, Option<?>> {
        private final A value;
    
        public Option(A value) { this.value = value; }
    
        @Override
        public <B> Option<?> map(Function<A, B> fn) {
            return new Option<B>(value != null ? fn.apply(value) : null);
        }
    }

There, you leave the element type of the returned functor undefined, as a wildcard, which lets you slip an Option<B> out as a return value.

The problem with that is that it's useless. Given:

        Option<String> x;
        Function<String, Integer> fn;

Then mapping the function over the option gives you:

        Option<?> y = x.map(fn);

An Option<?>. Which is no use to man or beast, because it's lost the type information.

What you really want to be able to write is:

  class Option<A> implements Functor<A, Option<_>>

Where the underscore is borrowed from Scala to mean "nothing to see here, move along please", and leaves that reference to Option in its unbound form. And then have a way of binding it right in the definition of the map function. But that's higher-kinded types, and Java doesn't have that.

If you were absolutely desperate to do this in Java, like if terrorists burst in and put a gun to your head and told you to do it, you could restore the type information by pebble-dashing the functor with some simple reflection:

    interface Functor<A, R extends Functor<?, R>> {
        <B> R map(Function<A, B> fn);
        <B> Functor<B, R> as(Class<B> b);
    }

    class Option<A> implements Functor<A, Option<?>> {
        // other stuff as above
    
        @Override
        public <B> Option<B> as(Class<B> b) {
            return new Option<B>(b.cast(value));
        }
    }

Which, given the above definitions of x and fn, lets you write:

        Option<Integer> y = x.map(fn).as(Integer.class);

And even the same thing but typed as functors, to show you there's nothing up my sleeve:

        Functor<String, Option<?>> fx = x;
        Functor<Integer, Option<?>> fy = fx.map(fn).as(Integer.class);

And as a separate function which contains no mention of the concrete functor class anywhere (although it does still need a type token for the result functor's parameter):

    private <A, B, F extends Functor<?, F>> Functor<B, F> applyAbstractly(Functor<A, F> fx, Function<A, B> fn, Class<B> b) {
        return fx.map(fn).as(b);
    }

But to be honest, all of this is a bit like trying to carve a fine wooden sculpture with a chainsaw. If you want to do this, don't use Java. If you want to use Java, don't do this.

You can do that partially. Because of the sub-classing and covariant return-types, I think you cannot prevent a CustomCollection from returning a CustomList. The definition would be:

  public interface Mappable<T extends Mappable<T>> {
      T map();
  }

I would bail on type checking and use an assertion. It's not reasonable to try to statically check everything in Java that you could in some other languages.

What discipline did the word "map" come from? ;) Is "map" even descriptive? In a programming concept, the first time I heard it I thought it was referring to the data structure of the same name, which is pretty different.

Yes, good point. I suppose replaceEach() would be a more descriptive name, so the interface might be HasReplaceEach. It's not as easy to talk about, though. Still better than "functor".

(The function being passed in to map() is an alternate way to represent a very large map, in a mathematical sense.)

Exactly. We'd only call the interface 'Mappable' if the method was called 'map', and that's something that's come from mathematical terminology.

(I'd probably have called the 'Map' class 'Dictionary', if that hadn't already been taken!)

I'd avoid 'replaceEach', because it sounds like it mutates the receiver. Maybe 'withEachReplaced'? Way clunky. In Smalltalk, this method is called 'collect', which is better than 'map', to my eyes, but still not all that obvious [1].

[1] Smalltalk has the names collect, inject, select, and reject for its map, foreach, filter, and complementary filter methods, because of a song: http://smalltalkzen.wordpress.com/2011/02/02/arlo-guthrie-an...

The Smalltalk version of foreach() is called #do:. #inject: is like reduce().

That blog post inspired a fun discussion in the Smalltalk community on what the semantics of #infect: and #neglect: should be!

Mathematicians prefer obscure technical terms to misleading and restrictive metaphors, because obscure terms force you to refer solely to (and eventually internalise) a precise and abstract definition.

I think this is the case for functors, because I've yet to see a metaphor for them which isn't misleading or restrictive. "replaceEach", for instance, would confuse me. I like working with parser combinators, where parsers are functors. If I replaceEach a parser, what have I replaced? The results of the parse? The parser hasn't been run on an input yet. Maybe it never will.

If I replaceEach a promise, what am I replacing? The result of the promise? Maybe the promise will be forever blocked, or maybe I'll cancel it.

If I replaceEach a continuation, what am I replacing?

> because obscure terms force you to refer solely to (and eventually internalise) a precise and abstract definition.

Unless some C++ people decide that “functor” is a wonderful name for a stateful function-like thing which somewhat resembles closures/lambdas but has nothing whatsoever to do with the functors from functional programming.

Well, yes, mathematicians like to be very precise about exactly what a very general abstraction entails, to the point where you are being very precise about how two almost entirely different concepts have almost but not quite nothing in common.

These fine distinctions don't belong in code meant for a general audience. Instead, don't try to generalize so much. It's not important (and in fact it's confusing) that replaceEach can be generalized to work with a parser. Parsers can have a different function with its own name and nobody needs to know that it's sort of the same concept.

/wow

More please !

Also guys, please check this new submission.

https://news.ycombinator.com/item?id=7895901

Alice and Bob play a cryptographic tetris game. Some french phd bloke has written it.

Would you please stop putting "/word" at the top of your comments? Gimmicks like that don't work here.

/love

It is a pattern, yes. Let me show you a pattern that I have observed in Hacker News and forums since the demise of USENET.

USENET had an elegant way of ignoring without hellbanning, which the negative karma has done to me now.

Would you please study the history of Stalinism ?

Let me summarise it for you.

Ideology -- pg.

Yeah, Marx is a good guy too.

It is made of dictators and the inner ring -- Admins and Karma users like you. These people have special "powers" of punishment.

Admins have far greater powers of purging and renaming things.

Then the party cadre -- people who submit and actually keep the things in motion. They are usually not aware of the "inner ring", users like you. They want to help the lay people.

In fact no one even knows who is in the inner ring. The inner ring is clueless of the Admins.

Then there are lay users like me, who lurk around and want to help but are generally punished.

If you think I am shitting you consider the rate of new users becoming high karma users in HN over the years.

You can use d3 and it will go the top of HN.

Your pedantry is just arbitrary. There is nothing really substantial in it. Rather than judging on the basis of content, you are judging me on the "words" I use.

Gimmick: An ingenious or novel device, scheme, or stratagem, especially one designed to attract attention or increase appeal.

Why thank you, it is novel :)

Please understand the democratic roots of the word "forum" and take it seriously.

More precisely it is an endofunctor in the category whose objects are Swift types and morphisms are functions between Swift types. All this really means is that given a Swift type, say Int or String, there are Arrays of Int or String, and given a function like showInt(a : Int) : String, a functor gives you a function from an Array of Int to an Array of String (in this case it would just apply showInt to each element of the Array and the result would be the Array of String) in such a way that if you have two functions (to keep with the example, say toUppercase(s : String) : String, the function you get by applying the functor to the composition (toUppercase . showInt) is the same as the composition of functions gotten from the application of the functor to the individual functions. In addition it is required that the identity function is mapped to the identity function.

Thank you for this. I find explanations that eschew category theory bizarre, this really cleared things up for me (having spent a lot of time with functors mathematically, and almost no time with them in a programming context).

I appreciate orbifold taking the time to reply but I couldn't understand his answer at all, even after perfectly understanding what others have said. There are 3 sentences in that paragraph the second of which is very large and difficult to parse and missing an end parenthesis somewhere.

Why do you get a composition of functions by applying a functor to individual functions? It seems like a functor is just something you can map over. When a functor is mapped over the end result is another functor. Not a function nor a composition of functions.

I was unsure what notation to use, so I used english instead. In Haskell a Functor f is characterized by a higher order function fmap :: (a -> b) -> (f a -> f b), which is required to satisfy the laws

fmap (g . f) = (fmap g) . (fmap f)

and

fmap id = id

where (.) :: (b -> c) -> (a -> b) -> (a -> c) is the function composition operator and id :: a -> a the identity function. Those are the laws the last two sentences try to phrase in english. In mathematics a functor F between categories C and D maps objects in C to objects in D and any morphism f: X -> Y in C to a morphism F f : F X -> F Y in D, in such a way that for morphisms f : X -> Y and g : Y -> Z in C one has F (g . f) = F g . F f and F id_X = id_{F X}. So you see Haskell and math notation are almost identical, although you can express the laws only as compiler rules in Haskell.

I think it gets worlds better with diagrams. I'll try to revisit this and provide some, when I've a bit more time.

> Why do you get a composition of functions by applying a functor to individual functions? It seems like a functor is just something you can map over. When a functor is mapped over the end result is another functor. Not a function nor a composition of functions.

A function is a Functor. ;)

If you have a function f and a function g, fmap f g = h, and h is a function. A more common way to write this is function composition of f and g, which can be written: f . g. The dot (.) is function composition. Which means that fmap f g = f . g, which means that fmap = (.).

> When a functor is mapped over the end result is another functor. Not a function nor a composition of functions.

But they was describing the case when the Functor in question is a function.

If something is Iterable, it's a Functor, but not the other way around. Iterable implies there's an order to the elements, for instance. It also implies that you could get ahold of the elements if you chose.

Types which are Functors may have orders and may provide access to the elements, but the Functor interface does not provide those means. This allows you to instantitate more restrictive types. For instance (in Haskell notation)

    data Pretend a = Pretend

is a data type with only one element (`Pretend`) that pretends to be a container. Consider the two types

    Array Int
    Pretend Int

You can still consider Pretend to be a Functor (the mapping function is just a no-op) but it certainly isn't iterable.

In Haskell, Iterable is called Foldable and effectively is the following interface

    instance Foldable c where
      toList :: c a -> [a]

but `Foldable` is used because typically instead of converting it to a list you want to fold over the elements

      fold :: Foldable c => (a -> b -> b) -> b -> c a -> b

The term "functor" is badly overloaded in general -- almost every language that uses the term has its own definition. In C++, it's an object that can be called as a function (by virtue of defining 'operator()') [0]. In Prolog, it's the head and arity of a term [1]. In ML, it's a function from structures to structures [2].

[0] http://www.stanford.edu/class/cs106l/course-reader/Ch13_Func...

[1] http://www.swi-prolog.org/pldoc/man?predicate=functor/3

[2] http://en.wikipedia.org/wiki/Standard_ML#Module_system

Let's begin with the array. Imagine I have an array of characters:

var a = ['a', 'b', 'c']

I'd like instead to have the index of their position in the alphabet. That's another array of the same length that would look like this:

var i = [0, 1, 2]

To each element in a, there corresponds an element i, at the same index. And the operation we use is the same for each element:

f('a') = 0

f('b') = 1

f('c') = 2

But we could also want an array that gives us the next letter in the alphabet, like so:

var n = ['b', 'c', 'd']

Here the function is:

g('a') = 'b'

g('b') = 'c'

g('c') = 'd'

But we're very much doing the same thing. We call it mapping. So Arrays in Swift have a map function defined that works like this:

var i2 = a.map(f)

We're passing the function to apply to each member, and we get an array back, of the same length, with the result of doing so.

A functor is a generalization of that concept. It takes a type parametrized by another type, say Box<V> and a function from the parametrized type to another type, say f:V -> W. Then, according to rules that are specific to Box, if you map f over Box<V>, you'll get a Box<W> out.

The key is that exactly how a Box<V> becomes a Box<W> is up to Box.

> Why is that called a functor instead of an iterable or enumerable though?

Probably because 1) it is inspired by category theory rather than some interface/signature from another programming language 2) "Iterable"/"Enumerable" might be misleading.

2): It might make sense for things like arrays, where you can think of the function (fmap) as enumerating/iterating over the array and then, for each value in the array, uses the supplied function on it. But Functors aren't just things that you can iterate over; functions themselves are functors, and function composition is fmap. But how does the iteration-intuition make sense in this case? Other functors are more a kind of "box" than a collection that can be iterated over (for example: the Option/Maybe type). Sure, you can say that you can implement fmap on Maybe by iterating over the data that it holds, namely the single data that it holds, but that doesn't really say much.