Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

fmap and "flat map" in Haskell

Tags:

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

like image 534
trans Avatar asked Oct 13 '16 15:10

trans


People also ask

What is Fmap in Haskell?

You can think of fmap as either a function that takes a function and a functor and then maps that function over the functor, or you can think of it as a function that takes a function and lifts that function so that it operates on functors. Both views are correct and in Haskell, equivalent.

What is flatMap in Haskell?

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


1 Answers

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.

like image 116
Alexis King Avatar answered Sep 19 '22 21:09

Alexis King