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)
...
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 Seq
s and Map
s 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.