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@haskell.org http://www.haskell.org/mailman/listinfo/beginners