Maps vs. map

In functional languages, map traditionally refers to everyone's favourite1 high-order function. C++ and Java, on the other hand, follow a common mathematical usage: a “map” is a dictionary (an associative array, if anyone still uses that term). Clojure and Scala, being of mixed parentage, have both: their map is the high-order function, and their dictionaries also have names containing Map. This is only a little bit confusing, but both concepts are so important that they ought to have unambiguous names.

I usually prefer to reserve map for the function, and dismiss the use of the same name for dictionaries because it's less familiar and it doesn't make much sense. But map doesn't make much sense as a name for the function either. You can make excuses for it (it maps old elements of the list to new ones? it maps2 the function across the list?) but they're not very compelling; you can make equally good excuses for many other functions. The name is standard, but it's not a very good one.

Meanwhile, dictionaries are a common concept in need of a good name. “Dictionary” is four syllables, and “associative array” six (and misleading). “Hash” is too specific (and also a little misleading, since it ought to mean a hash function). But “map” is short, already somewhat well-known, and if not clear then at least not actively misleading. So maybe I should give up and call them maps, and find some other name for map-the-function.

Is this outrageous?

There's no obvious better name. image might be clear to mathematicians, but it's opaque to everyone else. elementwise is too long. each is comfortable, but suggests for-each (as in Ruby) or every. Repurposed prepositions like across or through are opaque, and tend to collide with natural-language uses (consider how annoying the C++/Java this is in speech). Symbolic names are even more opaque, not to mention unpronounceable. Perhaps it acquired the name map for lack of a good alternative.

It might be possible to avoid the issue by making the function unnecessary. If scalar operations are overloaded to operate elementwise on collections, as in APL, explicit map would be much less common, so its name would be less important. It wouldn't be rare enough to ignore, though; many of its calls use operations that aren't scalar-only, or at least aren't obviously so, so they would still be written with explicit map.

Another alternative is to merge it with some other function. If collections are seen as functions, map is almost equivalent to compose (especially in a lazy language). If compose on a collection does map, then there's no need for a separate map function, especially if compose has a short name like . or . However, I have some difficulty understanding f . xs as map f xs. Composition and elementwise application may nearly coincide in meaning, but they're conceptually quite different.

1Except possibly for compose.

2This use of “map” as a verb is presumably derived from the function, so it's a poor excuse.

5 comments:

  1. I like the Smalltalk term for 'map', they call it #collect: and it's also available in Ruby (map and collect are aliases)

    The Smalltalk names are cute:

    Lisp: map, filter, reduce
    Smalltalk: #collect:, #select: and #reject:, #inject:into:

    ReplyDelete
  2. You could use the imperative 'for' or 'foreach' could you not? Sure it would return the list of transformed things, unlike the original, but then 'if' in functional programming returns a value too.

    On the other hand, the C++ STL uses 'std::transform' for the function.

    ReplyDelete
  3. Vítor De Araújo24 June 2012 at 04:44

    You can call dictionaries "tables" (which is what Lua does, I believe). Or you can call the function by its one true name: mapcar. :) [It is list-specific, though.]

    ReplyDelete
  4. On the contrary, I think the connection between the two uses of "map" is very deep. A map data structure represents a function with arbitrarily high computational complexity, where there just is no mathematical explanation for why a given key corresponds to a given value. The "map" function converts keys to values using a more ordinary function, though in principle it could be a big case statement corresponding to a map.

    In Owl Lisp, which is an implementation of the subset of R5RS that excludes mutability, there is a notion of "finite functions" which correspond to Java/C++ maps, but are immutable. The "list->ff" procedure returns a finite function from an a-list; the "put" and "del" procedures take a finite function and a key/value or key and return a larger or smaller finite function based on it. But finite functions are also invocable as ordinary functions. So given the finite function f defined as (list->ff '((a . b) (c . d) (e . f))), then (map f '(a e)) => (b d).

    (This doesn't actually work in Owl Lisp, because a finite function takes exactly two arguments, a key and a default value to return, but it's easy to see how it could be made to.)

    ReplyDelete
  5. I have heard map sometimes called 'project' as it is a projection of some data against a function. In the .NET space, there is LINQ which uses 'select' which they borrowed from SQL.

    ReplyDelete

It's OK to comment on old posts.