In Functional Programming, what is a functor?
I've come across the term 'Functor' a few times while reading various articles on functional programming, but the authors typically assume the reader already understands the term. Looking around on the web has provided either excessively technical descriptions (see the Wikipedia article) or incredibly vague descriptions (see the section on Functors at this ocaml-tutorial website).
Can someone kindly define the term, explain its use, and perhaps provide an example of how Functors are created and used?
Edit : While I am interested in the theory behind the term, I am less interested in the theory than I am in the implementation and practical use of the concept.
Edit 2 : Looks like there is some cross-terminoligy going on: I'm specifically referring to the Functors of functional programming, not the function objects of C++.
The word "functor" comes from category theory, which is a very general, very abstract branch of mathematics. It has been borrowed by designers of functional languages in at least two different ways.
In the ML family of languages, a functor is a module that takes one or more other modules as a parameter. It's considered an advanced feature, and most beginning programmers have difficulty with it.
As an example of implementation and practical use, you could define your favorite form of balanced binary search tree once and for all as a functor, and it would take as a parameter a module that provides:
The type of key to be used in the binary tree
A total-ordering function on keys
Once you've done this, you can use the same balanced binary tree implementation forever. (The type of value stored in the tree is usually left polymorphic—the tree doesn't need to look at values other than to copy them around, whereas the tree definitely needs to be able to compare keys, and it gets the comparison function from the functor's parameter.)
Another application of ML functors is layered network protocols. The link is to a really terrific paper by the CMU Fox group; it shows how to use functors to build more complex protocol layers (like TCP) on type of simpler layers (like IP or even directly over Ethernet). Each layer is implemented as a functor that takes as a parameter the layer below it. The structure of the software actually reflects the way people think about the problem, as opposed to the layers existing only in the mind of the programmer. In 1994 when this work was published, it was a big deal.
For a wild example of ML functors in action, you could see the paper ML Module Mania, which contains a publishable (ie, scary) example of functors at work. For a brilliant, clear, pellucid explanation of the ML modules system (with comparisons to other kinds of modules), read the first few pages of Xavier Leroy's brilliant 1994 POPL paper Manifest Types, Modules, and Separate Compilation.
In Haskell, and in some related pure functional language, Functor is a type class. A type belongs to a type class (or more technically, the type "is an instance of" the type class) when the type provides certain operations with certain expected behavior. A type T can belong to class Functor if it has certain collection-like behavior:
The type T is parameterized over another type, which you should think of as the element type of the collection. The type of the full collection is then something like T Int , T String , T Bool , if you are containing integers, strings, or Booleans respectively. If the element type is unknown, it is written as a type parameter a , as in T a .
Examples include lists (zero or more elements of type a ), the Maybe type (zero or one elements of type a ), sets of elements of type a , arrays of elements of type a , all kinds of search trees containing values of type a , and lots of others you can think of.
The other property that T has to satisfy is that if you have a function of type a -> b (a function on elements), then you have to be able to take that function and product a related function on collections. You do this with the operator fmap , which is shared by every type in the Functor type class. The operator is actually overloaded, so if you have a function even with type Int -> Bool , then
fmap even
is an overloaded function that can do many wonderful things:
Convert a list of integers to a list of Booleans
Convert a tree of integers to a tree of Booleans
Convert Nothing to Nothing and Just 7 to Just False
In Haskell, this property is expressed by giving the type of fmap :
fmap :: (Functor t) => (a -> b) -> t a -> t b
where we now have a small t , which means "any type in the Functor class."
To make a long story short, in Haskell a functor is a kind of collection for which if you are given a function on elements, fmap will give you back a function on collections . As you can imagine, this is an idea that can be widely reused, which is why it is blessed as part of Haskell's standard library.
As usual, people continue to invent new, useful abstractions, and you may want to look into applicative functors, for which the best reference may be a paper called Applicative Programming with Effects by Conor McBride and Ross Paterson.
Other answers here are complete, but I'll try another explanation of the FP use of functor. Take this as analogy:
A functor is a container of type a that, when subjected to a function that maps from a→b, yields a container of type b.
Unlike the abstracted-function-pointer use in C++, here the functor is not the function; rather, it's something that behaves consistently when subjected to a function.
There are three different meanings, not much related!
In Ocaml it is a parametrized module. See manual. I think the best way to grok them is by example: (written quickly, might be buggy)
module type Order = sig
type t
val compare: t -> t -> bool
end;;
module Integers = struct
type t = int
let compare x y = x > y
end;;
module ReverseOrder = functor (X: Order) -> struct
type t = X.t
let compare x y = X.compare y x
end;;
(* We can order reversely *)
module K = ReverseOrder (Integers);;
Integers.compare 3 4;; (* this is false *)
K.compare 3 4;; (* this is true *)
module LexicographicOrder = functor (X: Order) ->
functor (Y: Order) -> struct
type t = X.t * Y.t
let compare (a,b) (c,d) = if X.compare a c then true
else if X.compare c a then false
else Y.compare b d
end;;
(* compare lexicographically *)
module X = LexicographicOrder (Integers) (Integers);;
X.compare (2,3) (4,5);;
module LinearSearch = functor (X: Order) -> struct
type t = X.t array
let find x k = 0 (* some boring code *)
end;;
module BinarySearch = functor (X: Order) -> struct
type t = X.t array
let find x k = 0 (* some boring code *)
end;;
(* linear search over arrays of integers *)
module LS = LinearSearch (Integers);;
LS.find [|1;2;3] 2;;
(* binary search over arrays of pairs of integers,
sorted lexicographically *)
module BS = BinarySearch (LexicographicOrder (Integers) (Integers));;
BS.find [|(2,3);(4,5)|] (2,3);;
You can now add quickly many possible orders, ways to form new orders, do a binary or linear search easily over them. Generic programming FTW.
In functional programming languages like Haskell, it means some type constructors (parametrized types like lists, sets) that can be "mapped". To be precise, a functor f is equipped with (a -> b) -> (fa -> fb) . This has origins in category theory. The Wikipedia article you linked to is this usage.
class Functor f where
fmap :: (a -> b) -> (f a -> f b)
instance Functor [] where -- lists are a functor
fmap = map
instance Functor Maybe where -- Maybe is option in Haskell
fmap f (Just x) = Just (f x)
fmap f Nothing = Nothing
fmap (+1) [2,3,4] -- this is [3,4,5]
fmap (+1) (Just 5) -- this is Just 6
fmap (+1) Nothing -- this is Nothing
So, this is a special kind of a type constructors, and has little to do with functors in Ocaml!
上一篇: 为什么没有功能性编程呢？
下一篇: 在函数式编程中，什么是函子？