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.

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.

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.