Where does the word "flatMap" originate from?

Question

Nowdays flatMap is the most widely used name for correspondent operation on monad-like objects. But I can't find where it has appeared for the first time and what has popularized it.

The oldest appearance I know about is in Scala. In Haskell it is called bind. In category theory Greek notation is used.

Betook

The list version is called concatMap in Haskell because it's concat . map. In Scala (among others) concat is called flatten, so flatMap makes sense. – Atmo

@Atmo thanks for you response. I understand the meaning of this term. I'm interested in historical overview here. – Betook

If you replace flatMap with map you get a list of lists back. If you flatten the result you get the result from flatMap. map existed in Lisp in the 60s and a variation, maplist in the original lisp paper from 58. In CL flatMap is called mapcan and the CLHS explains it's the same as (apply #'nconc (mapcar f x1 ... xn)). Thus the use of flatten or concat in the name just indicates the users perspective on one thinks of the list as data or arguments. – Phile

@Phile on an unrelated tangent, I once tried (mapcon #'(lambda (x) x) (list 1 2 3)). can you tell what it does, without trying? /just for fun/ – Carper

@WillNess After the first iteration you have (1 2 3) and after the second it's (1 . #1=(2 3 . #1#)) and that stays for a while while its trying to get to the last pair to apply the next :-p Btw I think I was slightly fast by saying mapcan is flatMap since flatMap is probably not destructive by nature. – Phile

@Phile yeah. IOW a very nasty surprise. :) – Carper

Answer 1

Partial answer, which hopefully provides some useful "seed nodes" to start more thorough search. My best guess:

• 1958 for map used for list processing,
• 1988 for flatten used in context of monads,
• 2004 for flatMap used as important method backing for-comprehensions in Scala.

---

The function / method name flatMap seems to be a portmanteau word composed from flatten and map. This makes sense, because whenever M is some monad, A,B some types, and a: M[A], f: A => M[B] a value and a function, then the implementations of map, flatMap and flatten should satisfy

a.flatMap(f) = a.map(f).flatten

(in Scala-syntax).

Let's first consider the both components map and flatten separately.

Map

The map-function seems to have been used to map over lists since time immemorial. My best guess would be that it came from Lisp (around 1958), and then spread to all other languages that had anything resembling higher-order functions.

Flatten

Given how many things are represented by lists in Lisp, I assume that flatten has also been used there for list processing.

The usage of flatten in context of monads must be much more recent, because the monads themselves have been introduced in programming quite a bit later. If we are looking for the usage of word "flatten" in the context of monadic computations, we probably should at least check the papers by Eugenio Moggi. Indeed, in "Computational Lambda-Calculus and Monads" from 1988, he uses the formulation:

Remark 2.2: Intuitively eta_A: A -> TA gives the inclusion of values into computations, while mu_A: T^2 A -> TA flatten a computation of a computation into a computation.

(typesetting changed by me, emphasis mine, text in italic as in original). I think it's interesting that Moggi talks about flattening computations, and not just lists.

Math notation / "Greek"

On the Greek used in mathematical notation: in category theory, the more common way to introduce monads is through the natural transformations that correspond to pure and flatten, the morphisms corresponding to flatMap are deemphasized. However, nobody calls it "flatten". For example, Maclane calls the natural transformation corresponding to method pure "unit" (not to be confused with method unit), and flatten is usually called "multiplication", in analogy with Monoids. One might investigate further whether it was different when the "triple"-terminology was more prevalent.

flatMap

To find the origins of the flatMap portmanteau word, I'd propose to start with the most prominent popularizer today, and then try to backtrack from there. Apparently, flatMap is a Scala meme, so it seems reasonable to start from Scala. One might check the standard libraries (especially the List data structure) of the usual suspects: the languages that influenced Scala. These "roots" are named in Chapter 1, section 1.4 in Odersky's "Programming in Scala":

• C, C++ and C# are probably not where it came from.
• In Java it was the other way around: the flatMap came from Scala into version 1.8 of Java.
• I can't say anything about Smalltalk
• Ruby definitely has flat_map on Enumerable, but I don't know anything about Ruby, and I don't want to dig into the source code to find out when it was introduced.
• Algol and Simula: definitely not.
• Strangely enough ML (SML) seems to get by without flatMap, it only has concat (which is essentially the same as flatten). OCaml's lists also seem to have flatten, but no flatMap.
• As you've already mentioned, Haskell had all this long ago, but in Haskell it is called bind and written as an operator
• Erlang has flatmap on lists, but I'm not sure whether this is the origin, or whether it was introduced later. The problem with Erlang is that it is from 1986, back then there was no github.
• I can't say anything about Iswim, Beta and gbeta.

I think it would be fair to say that flatMap has been popularized by Scala, for two reasons:

• The flatMap took a prominent role in the design of Scala's collection library, and few years later it turned out to generalize nicely to huge distributed collections (Apache Spark and similar tools)
• The flatMap became the favorite toy of everyone who decided to do functional programming on the JVM properly (Scalaz and libraries inspired by Scalaz, like Scala Cats)

---

To sum it up: the "flatten" terminology has been used in the context of monads since the very beginning. Later, it was combined with map into flatMap, and popularized by Scala, or more specifically by frameworks such as Apache Spark and Scalaz.

Dulciedulcify

just reading... SML has List.concat : 'a list list -> 'a list – Audun

Thanks @D.BenKnoble, fixed. – Dulciedulcify

Answer 2

flatmap was introduced in Section 2.2.3 Sequences as Conventional Interfaces in "Structure and Interpretation of Computer Programs" as

(define (flatmap proc seq)
  (accumulate append nil (map proc seq)))

The first edition of the book appeared in 1985.

Proudman

as is noted in the book, "This approach to nested mappings was shown to [SICP's authors] by David Turner, whose languages KRC and Miranda provide elegant formalisms for dealing with these constructs. The examples in this section (see also exercise 2.42) are adapted from Turner 1981." that is a 1981 KRC paper. – Carper

(contd.) which talks of solving the backtracking problem with "ZF expressions" (i.e. list comprehensions) with nested generators -- which means concatMapping. – Carper