You’d naturally write flatMap yourself if asked the question
Many people struggle to understand those fluffy things called Monads and why they are important. I’m not going to attempt to alleviate this to a large degree, but I have had a recent success with a friend in having them attempt to write a familiar Scala function as a method. That is, the List.flatten function, which simply takes a List of List of some type A and returns a List[A]. It does this by concatenating all the lists together. I think most people are familiar with this function and have a good mental model of how it works. If this is the case and you are less confident about List.flatMap, then I hope to bring a point to your attention that might help you bring it home.
If you take a look at List.sort, you see it takes a function (A, A) => Boolean. This is because the type parameter to List is ‘just any A’. It would be nice if it was ‘any A, so long as it has defined order’. That way, you can just call list.sort and be done with it. This would require the creation of a new class with a more restricted type parameter; for example, you might pass the function at list creation time, like you do with a TreeMap.
Imagine writing List.flatten on the List[A] class as a method using the same technique. You wouldn’t be able to, since the method belongs on a List[List[A]]. You’d need to write the method such that it takes an argument: A => List[A] before you could then call flatten. When you have a List[List[A]], you’d just call this method with the identity function x => x to obtain your resulting List[A]. Here is how the method would look:
def flatten(f: A => List[A]): List[A] = ...
Guess what?! This method is flatMap! Let’s ignore the fact that the Scala API is significantly broken, including the List.flatMap method using Iterable in place of List here. Notice though, that flatMap is actually generalised by taking another type parameter, so we have just invented an unnecessarily specialised version of flatMap. Let’s fix it:
def flatten[B](f: A => List[B]): List[B] = ...
Woot woot! In other words, flatten(list) is equivalent to list flatMap (x => x). Furthermore, this should hold for more than just list, but for other type constructors too (sadly, Option is missing a flatten function: Option[Option[A]] => Option[A]). This is a special relationship that all monads have (join is a synonym for flatten and bind is a synonym for flatMap):
join = bind id
We can express this using Reductio (the Scala API of course!):
val prop_flat = prop((t: List[List[Int]]) => List.flatten(t) == t.flatMap(x => x)) // OK passed 100 tests.
I hope this helps. If it doesn’t, ask a question or ignore my ranting 
June 26th, 2008 at 2:27 am
I’m not sure I agree that Scala’s collections API is *completely* broken.
Granted, methods like flatMap and similar are a little inefficient when applied to general Iterable containers, but the methods are not final. For example, List overrides map, fold*, flatMap, etc covariantly to return of type List. I haven’t looked at the actual implementation, but I assume that it’s a fairly efficient design.
To what specific breakage were you referring?
June 26th, 2008 at 5:42 am
You lost me at “A => A => Boolean”, I don’t get what that means. Could you explain that, assuming a reader with no actual experience in functional programming?
June 26th, 2008 at 5:49 am
Daniel, I agree. Change “completely” to “almost completely” or “mostly”. The fact that List[A].flatMap takes a forall B. (B => Iterable[B]) as an argument instead of a (A => List[B]) is completely absurd. Granted, it may have been written at a time when higher kinds did not exist in the language, but it is so fundamentally broken, it should be repaired. The fact that these methods are not final offers no resolve. To observe a correction, take a look at the Monad trait in Scalaz.
Jörn, sorry if that caused confusion. The method that takes that argument is called a Higher-Order Function (HOF) because that argument is itself, a function. It is a function takes two arguments of type A and returns a Boolean.
To represent similar in Java, you’d have to use an interface:
interface Whatever { <A> boolean whatever(A a1, A a2); }Then you would substitute A => A => Boolean with Whatever<A> in the method signature. It is simply the strategy for resolving the order of the element types of the List or specifically, whether the first argument is less than the second.
I hope this helps.
June 26th, 2008 at 9:04 am
To further elaborate on the A => A => Boolean issue, that’s not *actually* the signature of the function value. The given signature represents the curried form of (A, A) => Boolean, which is the type that the API actually accepts.
I do prefer the curried form in most languages, but Scala is forced to impose a bit more syntactic overhead on curried functions than pure-functional languages like ML or Haskell. I guess it depends on your needs, which is better in Scala. Neither is really more capable than the other since a) you can easily convert between the forms, and b) partially-applied functions are fairly easy in Scala even with uncurried methods.
June 26th, 2008 at 9:08 am
Oh, with regards to the API being broken: yeah, I’ll agree with that. It is a little absurd that with a type system as powerful as Scala’s, we’re still left working with super-defined methods of non-specific type. I wonder if flatMap actually casts the return result of the function value so that it can return the specific type of List[A]. Quite nasty.
June 26th, 2008 at 10:47 am
Gah woops, that error in transcribing the type signature is potentially confusing, so I will repair it. The danger is of course, that this discussion now looks a little absurd.
Nevertheless, I think my mistake must be corrected in the main article.
Thanks for bringing it to my attention Daniel.
June 26th, 2008 at 5:55 pm
Thanks guys for the explanation. (A, A) => Boolean makes more sense to me, that was the missing link. I guess you prefer the curried signature because you can drop the parentheses.
June 26th, 2008 at 11:59 pm
Actually, Scala’s syntax for currying doesn’t let you drop the parentheses. In ML, you can do something like:
fun add a b = a + b
…and then invoke:
add 1 2
But unfortunately, Scala’s grammar does not allow this. The real advantage to currying is partially-applied functions. So you can define your add function as above, and then define a new function value which *specifically* adds a value to 10:
val addTen = add 10
Now you can invoke:
addTen 5
And the result is 15. This isn’t so useful in the trivial example, but once you start using it for larger things, you’ll never go back.
As mentioned above though, Scala allows partial application even for non-curried functions:
def add(a: Int, b: Int) = a + b
val addTen = add(10, _: Int)
Not really so clean as the curried alternative, but it still works. The curried form would be as follows:
def add(a: Int)(b: Int) = a + b
val addTen = add(10)
June 27th, 2008 at 7:09 pm
Hmm, I don’t quite understand. I think part of my confusion is that identity function. How does (foo:List[A]).flatten(x=>x) make sense if flatten takes an argument of type A=>List[A]? Unless I’m missing something basic, the types just don’t work.
July 20th, 2008 at 7:31 am
That’s because just before this flatten was generalised to take a function of type A => List[B] instead, so in our case (x => x) is of type (List[X] => List[X]) where X is a single type, A is List[X] and B is X.
Then it all works out ! ^^