How to create functors?

[Paul Rubin]

Steven D'Aprano <steven at REMOVE.THIS.cybersource.com.au> writes:
> As near as I can tell, a functor is just an object which is 
> callable like a function without actually being implemented as a 
> function, e.g.:

No it's not anything like that either, at least as I'm used to the
term in programming or in mathematics.  Maybe it's used other ways
though.  As I'm used to it, it's a feature of certain static type
systems.  The notion isn't that useful in Python but you could
translate it something like this: imagine that the "list" datatype has
a couple extra operations:

   # lift_value turns a normal value from a base type to a 1-element list
   list.lift_value(x) = [x]

   # lift_function turns a function on a base type to a higher order
   # function that operates on a whole list
   list.lift_function(f) = partial(map, f)
   
Then given a function like

   def square(x): return x*x

you could say

   lifted_square = list.lifted_function(square)
   print lifted_square([1,2,3,4,5])

and get [1,4,9,16,25].  Similarly if you had some other type (like a
tree data structure), that type could also support a map-like
operation so you could lift functions to it (lifting a function and
applying it to a tree like [1,[2,3],4] would result in [1,[4,9],16] or
whatever).

If I remember properly, for type t to be a functor it needs the above
two lifting operations, with the property that for a given function f,

   t.lifted_value(f(x)) = (t.lifted_function(f))(t.lifted_value(x))

I guess this explanation isn't going that well but basically in a
statically typed language you'd use functors to convert the signatures
of functions to versions that operate on higher types.  The idea comes
from ML and is used explicitly in Haskell, and I think some of the C++
standard template library can be explained in terms of functors.

For the mathematical concept of functors and how they relate to
programming (at least Haskell's version), see:

   http://en.wikibooks.org/Haskell/Category_theory