map function in Haskell, Scala, Clojure

(I tweeted this picture a few hours ago. It was not supposed to assert Haskell’s superiority over Scala and Clojure or anything like that, but many seem to have perceived it so. For the FUD that I inadvertently created, apologies. Here is an attempt to rectify my error, with a more nuanced and fairer analysis of the topic.)

The all too familiar map function has a staggering limitation – it works only for lists. Its type looks like this, when written in Scala notation.

def map[A, B](f: A => B, xs: List[A]): List[B]

Wouldn’t it be nice if we could “map over” other things? Like vectors, perhaps?

Various languages have explored this, and other dimensions of generalization, in a number of ways. Among those, we will specifically look at Haskell, Scala, and Clojure.

Haskell

Haskell has a type-class called Functor that allows arbitrary structures to dictate how they should be mapped over. (If this were OO-world, this type-class may have been labelled Mappable.) The function is called fmap, because map was already taken by lists.

This is what the definition looks like:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Or in Scala notation:

trait Functor[F[_]] {
  def fmap[A, B](f: A => B, x: F[A]): F[B]
}

Note my use of a very unassuming term “structure”. What I am trying to imply here is that the thing to be mapped over need not be a container. Here are a couple of examples of things that are functors, but not containers.

// Identity
type Id[A] = A

implicit val identityFunctor = new Functor[Id] {
  def fmap[A, B](f: A => B, x: Id[A]): Id[B] = f(x)
}

// Functions
trait FuncFrom[A] {
  type To[B] = A => B
}

implicit def functionFunctor[S] = new Functor[FuncFrom[S]#To] {
  def fmap[A, B](f: FuncFrom[A]#To[B], x: FuncFrom[S]#To[A]): FuncFrom[S]#To[B] = f.compose(x)
}

Sometimes it’s possible to infer a functor instance for a data type from its structure. Haskell provides multiple facilities for doing this. (DeriveFunctor, DeriveGeneric, TH etc.)

Scala

In Scala, map is typed so that it can choose the most suitable result type for the occasion. Here is what its type looks like, when seen in all its glory:

def map[A, B, That](f: A => B, coll: FilterMonadic[A, Repr])
                   (implicit bf: CanBuildFrom[Repr, B, That]): That

Here are some examples of the wonderful things it can do. (Pasted from REPL; see the types on the left.)

scala> import collection.immutable._
import collection.immutable._

scala> val b = BitSet(3, 8, 9)
b: scala.collection.immutable.BitSet = BitSet(3, 8, 9)

scala> b.map(_ + 1)
res2: scala.collection.immutable.BitSet = BitSet(4, 9, 10)

scala> b.map(_.toString)
res3: scala.collection.immutable.SortedSet[String] = TreeSet(3, 8, 9)

scala> val m = Map(3 -> "hello", 4 -> "world")
m: scala.collection.immutable.Map[Int,String] = Map(3 -> hello, 4 -> world)

scala> m.map { case (k, v) => (k, v(0)) }
res4: scala.collection.immutable.Map[Int,Char] = Map(3 -> h, 4 -> w)

scala> m.map { case (k, v) => v }
res5: scala.collection.immutable.Iterable[String] = List(hello, world)

This is achieved with a sophisticated/complex abstraction called CanBuildFrom. I highly recommend reading this document to understand the philosophy behind the architecture of Scala collections.

The best part about this framework is that it’s relatively easy for your custom collections to fit in, while needing to provide only the minimum required details. The document I linked above exemplifies this point with a custom collection class called RNA.

Now, the type signature arguably looks quite involved/scary. To address the issue, at least partially, Scala team devised something called use-case, which shows simplified/compressed signatures in the documentation.

The Scala collections framework has received an immense criticism for the complexity of its design. Some argue the extension is not quite as natural as advertised, and the implementation leaks through in many ways. Paul Philips, the man who needs no introduction in Scala circles, criticizes its very foundations, and exemplifies his points with a numerousgotchas, bugs, and extension difficulties the design has led to. He is working on a new collections framework built on simpler and more correctness-friendly foundations.

It deserves mentioning that I, and many others who’ve worked with Scala for long, do not share the same frustration, and have found that the design works well enough in practice. YMMV.

Clojure

Clojure extends map to work with arbitrary number of sequences. How does it behave for two and more arguments? Simple – it zips the given sequences and then applies the supplied function on the group!

Though Clojure is a dynamically typed language, it has an optional type system available, which is what we are going to use for the purpose of this post. This is how the type of map looks like with Typed Clojure:

(ann clojure.core/map
  (All [c a b ...]
    (Fn [[a b ... b -> c] 
         (NonEmptySeqable a) (NonEmptySeqable b) ... b -> (NonEmptyLazySeq c)]
        [[a b ... b -> c] 
         (U nil (Seqable a)) (U nil (Seqable b)) ... b -> (LazySeq c)]))

In Scala(-like) notation, that would roughly be:

def map[A, B, ..., C](xs: NonEmptySeqable[A], ys: NonEmptySeqable[B], ..., f: (A, B, ...) => C): NonEmptyLazySeq[C]

def map[A, B, ..., C](xs: Null | Seqable[A], ys: Null | Seqable[B], ..., f: (A, B, ...) => C): LazySeq[C]

(The above was taken from this blog post.)

This signature may look daunting, but being a Lisp and a dynamically typed language, variadic arity function application is a very natural operation in Clojure.

Note that Typed Clojure type here has a more expressive specification of function’s behavior, than the Scala and Haskell counterparts – such as how the function behaves differently for non-empty and empty sequences. The essence of the function lies in the second signature.

Also to be noted: This generalization isn’t Clojure’s innovation. Common Lisp’s mapcar has the same behavior.

Fairer comparison

As we saw, the three languages are trying to generalize map along very different dimensions. So a judgement like “this one’s shorter, and therefore better” would be superficial and unfair.

For fairness’ sake, let’s see how the other two languages fare in what the third tries to do.

Functor is easily expressible in Scala (and we did it above). Scalaz has it. Type-based dispatch and ergo functor is largely irrelevant in Clojure’s case.

CanBuildFrom, it turns out, is exceedingly hard in Haskell. Whether or not they think it’s the right way to go is beside the point. This technique too is irrelevant in Clojure’s case, for the same reason as before.

Clojure’s variadic arity map that subsumes various zipWith{N} operations is hard to do in typed languages. Check out the ZipWithN stuff here. Typically one’d just use applicative though, which can be thought of as a generalization of functor for variadic arity. The ZipWithN and applicative comment holds true for Scala as well.

Conclusion

The picture I tweeted is supposed to be symbolic of different strides these languages are making in similar areas.

I personally find all of the generalizations discussed to be positively interesting and useful.

I hope this post paints a fairer picture than what I tweeted in the morning.

Credits

Thank you for your many inputs, Ambrose BS, Eyal Lotem, and Edward George.