Types of map function in Haskell, Scala, and Clojure

(I originally shared the image below in a tweet. That tweet is gone now, but the image is preserved here. It was not meant to suggest Haskell’s superiority over Scala and Clojure, but some people understandably read it that way. This post is an attempt to correct that impression with a more nuanced and fairer analysis of the topic.)

Comparison image for the types of map in Haskell, Scala, and Clojure

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

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

Wouldn’t it be nice if we could map over other things too, vectors for instance?

Various languages have explored this and other dimensions of generalisation in different ways. Here, we will look specifically 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 the OO world, the type class might have been named Mappable. The function is called fmap, because map was already taken by lists.

This is what the definition looks like:

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

Or in Scala notation:

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

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

1
// Identity
2
type Id[A] = A
3

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

8
// Functions
9
trait FuncFrom[A] {
10
  type To[B] = A => B
11
}
12

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

Sometimes it is possible to infer a functor instance for a data type from its structure. Haskell provides multiple facilities for doing this, such as DeriveFunctor, DeriveGeneric, and Template Haskell.

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 in full:

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

Here are some examples of the things it can do. These are pasted from the REPL; see the types on the left.

1
scala> import collection.immutable._
2
import collection.immutable._
3

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

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

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

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

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

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

This is achieved with a sophisticated, and admittedly 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 is relatively easy for custom collections to fit in, while needing to provide only the minimum required details. The document linked above illustrates this with a custom collection class called RNA.

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

The Scala collections framework has received immense criticism for the complexity of its design. Some argue the extension story is not quite as natural as advertised, and that the implementation leaks through in many ways. Paul Phillips, who needs little introduction in Scala circles, criticises its foundations, and illustrates his points with numerous gotchas, 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 is also worth mentioning that I, and many others who have worked with Scala for a long time, have not shared the same degree of frustration and have found that the design works well enough in practice. Your mileage may vary.

Clojure

Clojure extends map so that it can work with an arbitrary number of sequences. How does it behave for two or more arguments? Simply: it zips the given sequences and then applies the supplied function to each grouped set of values.

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

1
(ann clojure.core/map
2
  (All [c a b ...]
3
    (Fn [[a b ... b -> c]
4
         (NonEmptySeqable a) (NonEmptySeqable b) ... b -> (NonEmptyLazySeq c)]
5
        [[a b ... b -> c]
6
         (U nil (Seqable a)) (U nil (Seqable b)) ... b -> (LazySeq c)]))

In Scala-like notation, that would roughly be:

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

3
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 both a Lisp and a dynamically typed language, variadic function application is a very natural operation in Clojure.

Note that the Typed Clojure type here gives a more expressive specification of the function’s behaviour than the Scala and Haskell counterparts, such as the different behaviour for non-empty and empty sequences. The essence of the function lies in the second signature.

Also worth noting: this particular generalisation is not Clojure’s innovation. Common Lisp’s mapcar has the same behaviour.

Fairer comparison

As we saw, the three languages are trying to generalise 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 us see how the other two languages fare at what the third tries to do.

Functor is easily expressible in Scala, and we did it above. Scalaz has it. Type-based dispatch, and therefore functor in this sense, is largely irrelevant in Clojure’s case.

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

Clojure’s variadic map, which subsumes various zipWithN operations, is hard to do in typed languages. Check out the ZipWithN material here. Typically one would use Applicative instead, which can be thought of as a generalisation of Functor for variadic arity. The ZipWithN and Applicative point holds for Scala as well.

Conclusion

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

I personally find all of the generalisations discussed here interesting and useful.

I hope this post paints a fairer picture than the tweet did.

Credits

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