[Haskell-beginners] Who discovered map reduce?

[Nick Vanderweit]

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