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"?

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.}