Well, if you're using Java, you don't have map in the JDK. You can use Guava (or write your own) to get Iterables.transform(). But then, anything you map turns into an Iterable. So often you have to iterate over the whole thing once again to get the data structure you actually need. You could write Collections.map(), Lists.map(), Sets.map(), etc, until you get tired. (Guava does not include these.)

But at this point you're still way behind Scala. What about flatMap, filter, slice, drop, scan, etc? Every collection in Scala has a huge set of methods that work on it. But they're not implemented again and again, because the type system is powerful enough to prove that the generic code that works for Set can be used for List. In contrast, every Java program is full of innumerable primitive operations expressed again and again, so you have to keep reading the steps of every for loop to determine, "oh, this one is doing forall. This one is map" rather than simply reading "forall", "map". Which is why, thanks to the above complexity, Scala can be much more readable than Java.

What about Haskell? The existing standard library is fairly weak on collections. There are not that many implementations, and there's no typeclass that quite captures the idea of a collection: you've got Foldable, Functor, Monad, and possibly some others, which all get slightly different aspects of it. Small typeclasses are nice in that they allow more instances, but often you need some functions that aren't there. There's no typeclass which captures the size() function, for instance. That's mostly a library design issue, which is more tractable than a language issue, but still pretty hard to fix.

There's one additional cool feature of Scala collections which I haven't touched on yet: transformations can result in collections that are different from the original collection type, and the most specific collection that is compatible is used. What does that mean? Say I map a TreeSet from an ordered element type to an unordered type. The result type can no longer be stored in a TreeSet, so you get a more generic Set collection instead. I'm curious what it would take to implement this in Haskell.

So ignoring Java and concentrating entirely on expressiveness & ignoring readability, maintainability, etc... It seems like Collections are the entire kitchen sink of algorithms that map across iterable content. How is that better than more precise types (functors, monoids, monads, foldables)?

For example: what is the benefit of reducing these data structures (and associated algorithms which operate on them) to more generic versions?

> There's one additional cool feature of Scala collections which I haven't touched on yet: transformations can result in collections that are different from the original collection type, and the most specific collection that is compatible is used. What does that mean? Say I map a TreeSet from an ordered element type to an unordered type. The result type can no longer be stored in a TreeSet, so you get a more generic Set collection instead. I'm curious what it would take to implement this in Haskell.

While I agree that this is "cool" that you can do that, I really don't see the use of it except when sketching out ideas when you're not sure what kind of data flow you want yet... but that seems like a problem with designing the program and should be avoided.

In Scala 2.7 the signature for map, defined in Iterable[+A], was def map[B](f : (A) => B) : Iterable[B]

That seems fairly close to the Haskell signature, although somewhat less readable. However, in Scala 2.8, things got more complicated with the addition of the implicit. Consider two functions that I might apply to a collection of integers:

Set(1,2,3,4).map{ _2 } // Set[Int] = Set(2, 4, 6, 8)

Set(1,2,3,4).map{ _.toString } // Set[String] = Set(1, 2, 3, 4)

Nothing surprising here, we provide a method A->B and use it to map from Set[A] -> Set[B] Now lets use the optimized BitSet collection, which efficiently stores integers:

BitSet(1,2,3,4).map{ _2 } // BitSet = BitSet(2, 4, 6, 8)

BitSet(1,2,3,4).map{ _.toString } // Set[String] = Set(2, 4, 3, 1)

Notice that the collection type is BitSet for the function with return type of Int, but plain Set for the function with return type of String. This functionality is brought to you through the implicit parameter.

An asterisk got eaten in your post. You should start lines of code with a couple of spaces to make HN stop doing that.

  Set(1,2,3,4).map{ _ * 2 } // Set[Int] = Set(2, 4, 6, 8)

  BitSet(1,2,3,4).map{ _ * 2 } // BitSet = BitSet(2, 4, 6, 8)