fmap and "flat map" in Haskell

Question

All this time, when any Haskell lecture spoke of "flat map", usually in relation to Monads, I thought it was called "flat" for a reason, i.e. it flattens out the container. So

[[1,2],[3,4]]

would be processed just as if it were

[1,2,3,4]

But now I discover that fmap and map are basically the same thing, the only difference being the application of one for functors and the other for just lists. And that was only done, in the end, to avoid confusing error messages when using map.

Is that true? And if so why did f in fmap come to mean "flat", why not "functor map"?

• Lee: The f in fmap doesn't mean flat. The equivalent of flatMap in Haskell is (>>=). The map function for lists was defined first so another name was needed for the more general fmap function.
• chepner: Rather, fmap is the generalization of map to other functors besides the list functor. Whoever told you that fmap was short for flat map was mistaken.
• sepp2k: Are you sure that the lecture you allude to was referring to fmap when saying "flat map"? It'd make more sense if it had been referring to concatMap (aka >>=), which is often called flatMap in other languages and behaves in the way you expected.
• duplode: @trans [1,2,3] >>= \x -> [x,x]
• chi: The flattening is performed last, not first. In [[1,2],[3,4]] >>= \x -> [x] we take every element of the list and bind it to x (hence x=[1,2] and x=[3,4]), then we apply the function \x->[x] to each x, obtaining the result list [ [[1,2]], [[3,4]] ]. Finally, we flatten the last list to the result: [[1,2],[3,4]].

Answer 1

And if so, why did f in fmap come to mean "flat", why not "functor map"?

Your intuition is right: the f in fmap does stand for "functor map", not "flat map" at all. In fact, in newer, similar languages, such as PureScript, the name is just map. The Haskell map was defined first for lists, though, so coming up with a new name was difficult. Using the F from Functor was an easy, if not particularly creative, choice.

It is more likely that the lecturer was referring to the monadic bind function, >>=. Due to x >>= f’s equivalence to join (fmap f x), bind is also sometimes called flatMap in other languages. It has the behavior you expect on lists, for example:

> [1,2,3] >>= \x -> [x,x]
[1,1,2,2,3,3]

It’s important to keep in mind, though, that this "flat map" does not recursively flatten to an arbitrary depth. In fact, writing such a function isn’t really possible in Haskell without some complicated typeclass trickery. Try it yourself: what would the type signature for a flatten function look like, even one that operates directly on lists?

flatten :: ??? -> [a]

The >>= function is very simple in comparison: it is like fmap, but every output element must be wrapped in the functor, and >>= shallowly "flattens" the results into a single wrapper. This operation is the essence of what a monad is, which is why the >>= function lives in the Monad typeclass, but fmap is in Functor.

_{This answer is taken from some of the comments on the original question, so I have marked it community wiki. Edits and improvements are welcome.}

• trans: It's not just numbers though, even a list when there are different depths, [[[1,2]],[3],[4]] >>= \x -> x only produces :: (Num [t], Num t) => [[t]], not [[1,2],3,4].
• Alexis King: @trans Note that [[[1,2]],[3],[4]] is not a valid Haskell value. It does not have a type—it is neither Num t => [[t]] nor Num t => [[[t]]] because the depth is not consistent.
• Alexis King: The reason you get that type is because of the way Num works, so it infers a type of Num t => [[t]] where it expects [1, 2] to have a Num instance. Of course, it does not. Try with non-numbers to get clearer results.
• Benjamin Hodgson: "Writing such a function isn't really possible in Haskell without some complicated typeclass trickery" - I disagree. data Nested f a = Flat a | Nested (f (Nested f a)) deriving Foldable is a pretty simple type for arbitrarily nested Foldables
• Alexis King: @BenjaminHodgson I meant using only the built-in [] type. It’s obviously pretty easy if you use your own wrapper.

Answer 2

Here are some explicit equivalent examples of how to do flatMap in Haskell.

Prelude> map (replicate 3) [1..4]
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]
Prelude> fmap (replicate 3) [1..4]
[[1,1,1],[2,2,2],[3,3,3],[4,4,4]]
Prelude> concat [[1,2],[3,4]]
[1,2,3,4]
Prelude> concat (map (replicate 3) [1..4])
[1,1,1,2,2,2,3,3,3,4,4,4]
Prelude> concat $ map (replicate 3) [1..4]
[1,1,1,2,2,2,3,3,3,4,4,4]
Prelude> concatMap (replicate 3) [1..4]
[1,1,1,2,2,2,3,3,3,4,4,4]
Prelude> replicate 3 `concatMap` [1..4]
[1,1,1,2,2,2,3,3,3,4,4,4]
Prelude> [1..4] >>= replicate 3
[1,1,1,2,2,2,3,3,3,4,4,4]

It should be clear that flatMap is map first and then flat, you flatten the output of the map, as opposed to flattening the input list you are about to process (this isn't flatMap, this has no name, it is just a flat and then map).