Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Some higher-order functions for operating on lists or arrays have been repeatedly adopted or reinvented. The functions map, fold[l|r], and filter are found together in several programming languages, such as Scheme, ML, and Python, that don't seem to have a common ancestor. I'm going with these three names to keep the question focused.

To show that the names are not universal, here is a sampling of names for equivalent functionality in other languages. C++ has transform instead of map and remove_if instead of filter (reversing the meaning of the predicate). Lisp has mapcar instead of map, remove-if-not instead of filter, and reduce instead of fold (Some modern Lisp variants have map but this appears to be a derived form.) C# uses Select instead of map and Where instead of filter. C#'s names came from SQL via LINQ, and despite the name changes, their functionality was influenced by Haskell, which was itself influenced by ML.

The names map, fold, and filter are widespread, but not universal. This suggests that they were borrowed from an influential source into other contemporary languages. Where did these function names come from?

share|improve this question
10  
map would come from mathematical set theory, which describes set transformations as "mappings" from the input domain to the output range. –  Aidan Cully Jul 1 '13 at 22:41
2  
Lisp's mapcar is a map, on the car (rather than the cdr). –  MichaelT Jul 2 '13 at 1:24
    
fold got it's name because in set theory it's called catamorphism but that's just absolutely ridiculous. Also foldl is Aggregate in LINQ, again from SQL terminology. –  Jimmy Hoffa Jul 2 '13 at 3:12
1  
Also note that while those languages don't have common ancestors officially, there absolutely has been a lot of influence, back and forth. Guido van Rossum had done his homework when he started designing Python, and Scheme, Common Lisp, Perl and (IIRC) Haskell and ML were already around at the time. –  tdammers Jul 2 '13 at 8:16
1  
filter does exactly that - it filters the data. Seems pretty obvious. –  Dukeling Jul 2 '13 at 18:57

1 Answer 1

The only universal word in your list is map and it already appears in the original paper on Lisp in 1960 (under the guise of maplist). The paper also has search (AKA filter, AKA remove-if-not).

I think the reason map endured while the others have variants is that map comes from relatively ancient, established, common & elementary math while catamorphism (AKA reduce AKA fold &c) is a relatively advanced concept, from a relatively obscure recently developed (more or less simultaneously with CS) domain, and it was introduced (in the late 1980-ies) when reduce was available in Lisp for over a decade.

Others (filter AKA remove-if-not) are even more ad hoc in CS/programming, so people felt even more comfortable picking their own name for them.

share|improve this answer
1  
Don't vaguely refer to Category theory as "an obscure recently developed domain" also it is about as "recently developed" as Lambda calculus. –  Dan D. Aug 15 '13 at 17:19
    
@DanD.: the key word is relatively –  sds Aug 15 '13 at 17:20
    
Even then, they all got buggered in .NET so that they would be similar to SQL. (map -> Select; filter -> Where; fold -> Aggregate) –  Steve Evers Aug 15 '13 at 18:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.