Scala: Seq, Map and Set as functions

Programming, Scala

Yesterday my mate asked me: “I have a List[String] and a Map[String, Int] and I want a List[Int] where its values are those of the Map whose keys match the List[String] elements, maintaining the order. Should I use pattern matching?”. I know, the sentence is a bit convoluted but the code will make it clear, hopefully. Anyway, I replied: “No, you don’t need pattern matching, you just need this”:

 
scala> val m = Map("a" -> 1, "b" -> 2, "c" -> 3)
m: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 2, c -> 3)

scala> val l = List("a", "c", "b")
l: List[String] = List(a, c, b)

scala> l collect m
res0: List[Int] = List(1, 3, 2)

Hold on, how does it work? If you look at the definition of the collect method you’ll see it accepts a PartialFunction, instead I passed a Map to it. Well, it turns out that Map is a PartialFunction.

Since this peculiarity surprised him I decided to write a small post showing how Scala’s Map, List (actually Seq) and Set can be viewed as functions.

Before starting: functions vs partial functions

In short, a function is a mapping A => B that relates each value of type A to a value of type B–modulo bottom. A and B are called domain and codomain, respectively. If you’re not a math addict, roughly speaking, the domain is the set of all values that you may provide as input to your function, while the codomain is the result of the function application to the input, that is your function output.
On the other hand a partial function from A to B is not defined for some inputs of type A. E.g.:

 
// function
scala> val abs: Double => Double = x => if (x > 0) x else -x
abs: Double => Double = <function1>

scala> abs(42)
res1: Double = 42.0

scala> abs(-42)
res2: Double = 42.0

// partial function
scala> val sqrt: PartialFunction[Double, Double] = {
     |   case x if x >= 0 => math.sqrt(x)
     | }

scala> sqrt(4)
res3: Double = 2.0

scala> sqrt(-1)
scala.MatchError: -1.0 (of class java.lang.Double)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:253)
  at scala.PartialFunction$$anon$1.apply(PartialFunction.scala:251)
  at $anonfun$1.applyOrElse(<console>:7)
  at $anonfun$1.applyOrElse(<console>:7)
  at scala.runtime.AbstractPartialFunction$mcDD$sp.apply$mcDD$sp(AbstractPartialFunction.scala:36)
  ... 33 elided

Note that the PartialFunction definition is the following:

 
trait PartialFunction[-A, +B] extends (A) => B

That is a PartialFunction is a Function that will just throw for those inputs the partial function is not defined at. So you can use a PartialFunction wherever a Function is expected. Just keep in mind you’ll get an exception for some input values.

Seq[A] as PartialFunction[Int, A]

Being List an indirect subclass of collection.Seq and given that the latter has the following definition, you can see clearly that every Seq[A] is also a PartialFunction[Int, A]:

 
trait Seq[+A] extends PartialFunction[Int, A] with ...

Here’s an example:

 
scala> val xs = List("a", "c", "b")
l: List[String] = List(a, c, b)

scala> val f1: PartialFunction[Int, String] = xs
f1: PartialFunction[Int,String] = List(a, c, b)

scala> f1(0)
res4: String = a

Of course I could have used xs directly without the assignment to f1:

 
scala> xs(0)
res2: String = a

I assigned the list to f1 just to emphasise the fact that it’s a partial function. It corresponds to the index-based lookup.

Performance concern: Take into account that the index-based lookup on List has a cost of O(n). For this type of access you may consider using a Vector which has constant-time access cost. Anyway this post is not about performance concerns about the collection API so I won’t dig into this topic.

Map[A, B] as PartialFunction[A, B]

If you look at the Map definition you’ll see that it extends MapLike which, in turn, extends PartialFunction. So you can use it as follows:

 
scala> val m = Map("a" -> 1, "b" -> 2, "c" -> 3, "d" -> 4)
m: scala.collection.immutable.Map[String,Int] = Map(a -> 1, b -> 2, c -> 3, d -> 4)

scala> val f2: PartialFunction[String, Int] = m
f2: PartialFunction[String,Int] = Map(a -> 1, b -> 2, c -> 3, d -> 4)

scala> f2("a")
res5: Int = 1

Set[A] as A => Boolean

Here’s the definition of Set:

 
trait Set[A] extends (A) => Boolean with ...

It, evidently, extends A => Boolean which, as you probably already know, is just syntactic sugar for the more verbose Function[A, Boolean]. Example:

 
scala> val s = Set("a", "b", "c")
s: scala.collection.immutable.Set[String] = Set(a, b, c)

scala> val f3: String => Boolean = s
f3: String => Boolean = Set(a, b, c)

scala> f3("a")
res6: Boolean = true

So, for instance, you can use a set to filter a list:

 
scala> val xs = List("a", "c", "b")
xs: List[String] = List(a, c, b)

scala> val s = Set("a", "b", "d")
s: scala.collection.immutable.Set[String] = Set(a, b, d)

scala> xs filter s
res7: List[String] = List(a, b)

Conclusions

As a final consideration take into account that Seqs and Maps are partial functions while Set is a function. Partial functions could introduce insidious bugs. For instance, consider the very first example of this post. If the Map hadn’t contained all the elements of the List and I had used the map method instead of collect I would have introduced a bug:

 
scala> val xs = List("a", "b", "c", "d")
xs: List[String] = List(a, b, c, d)

scala> val m = Map("a" -> 1)
m: scala.collection.immutable.Map[String,Int] = Map(a -> 1)

scala> xs map m
java.util.NoSuchElementException: key not found: b
  at scala.collection.MapLike$class.default(MapLike.scala:228)
  at scala.collection.AbstractMap.default(Map.scala:59)
  at scala.collection.MapLike$class.apply(MapLike.scala:141)
  at scala.collection.AbstractMap.apply(Map.scala:59)
  at scala.collection.immutable.List.map(List.scala:277)
  ... 33 elided

This is because map accepts a function and providing a partial function instead you get the exception for not valid inputs as I said in the functions vs partial functions section.

From now on, whenever you have a collection hanging around, consider looking at it as a function. This could help to solve your problem without using pattern matching or other boilerplate.