[Haskell-beginners] Who discovered map reduce?
Nick Vanderweit
nick.vanderweit at gmail.com
Tue Sep 11 03:58:11 CEST 2012
I can't tell you the history of the map higher-order function, but the
underlying concept of a functor has its roots in category theory, which is
quite old (dating back to the 1940s). Here's a brief explanation of the
mathematics.
A category is basically a digraph, whose vertices we call "objects" and whose
edges we call "arrows." For each object there is an identity arrow id_a : a ->
a, and for each pair of arrows f : a -> b and g : b -> c, there is a composite
arrow g . f : a -> c. The identity arrow for some object has to actually be an
identity under composition (that is, on the left and on the right), and the
composition has to be associative. The category we're really concerned with in
Haskell is Hask, the category of Haskell functions, whose objects are Haskell
types and whose arrows (AKA morphisms) are functions between these types, f ::
a -> b. The identity arrow at a given type A is id :: A -> A, and composition
is the (.) operator.
We have a structure, so the next natural thing (for the algebraically-
inclined, anyway) is to think about a structure-preserving map (a
homomorphism). A homomorphism of categories is called a "functor." Let T be a
functor from C to B, written T : C -> B. Then T assigns each object in C an
object in B, and each arrow in C an arrow in B. In order to be structure-
preserving, they have to satisfy the following property: that composing in C
and then applying the functor to get to B is the same as applying the functor
to the objects in C and then composing in B, and that identities are sent to
identities.
If we look at the Haskell functor class:
class Functor f where
fmap :: (a -> b) -> f a -> f b
We can pick out the "object function" and "arrow function." For some Functor
f, f is the object function. For instance, Maybe sends Int to Maybe Int.
For our arrow function, we have fmap, which sends arrows (a -> b) in Hask to
arrows (f a -> f b), also in Hask (a functor mapping from a category to itself
is called an endofunctor). It satisfies the following properties:
fmap g . fmap f = fmap (g . f)
fmap id = id
Which are precisely the "structure-preserving" properties for functors stated
above. So you may be used to thinking of "map f xs" as "map f over the list
xs." But a deeper way of thinking about it is that map takes a function f on
Haskell types, and turns it into a function on lists parameterized over those
types. And this, as it turns out, is a pretty old idea.
Nick
On Monday, September 10, 2012 04:19:47 PM Bryce wrote:
> In the same vein as the "who discovered the fold operation" thread from
> last week, I would like to know the same answer for "map".
>
> I tried looking it up on wikipedia, but the best line I could find from
> it is this:
> "The map function originated in functional programming languages but is
> today supported (or may be defined) in many procedural, object oriented,
> and multi-paradigm languages as well: In C++'s Standard Template
> Library, it is called transform, in C# (3.0)'s LINQ library, it is
> provided as an extension method called Select."
>
> Does anyone have an answer or idea on where I could look?
>
> Thanks in advance and sorry if it it's a redundant question.
>
> Bryce
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
More information about the Beginners
mailing list