Why is there no right-handed list type in Scala?
In theory, at least, lists come in two types: left-handed and right-handed. What’s that you say? I’m using the term left-handed for lists that are built thus:
head cons tail
where head is an element, tail is a list, and cons is a constructor. Contrary to most of the rest of human interactions, Scala is biased towards left-handed lists in most, if not all, of the sequence types: ::, List, Seq, etc. The “head” of the list is on the left and therefore the prepend operation (typically using the +: method) takes constant time. On the other hand, appending (using the :+ method) takes time proportional to the length of the list.
The consequence of this left-handedness is that certain methods such as foldLeft, reduceLeft, head are efficient (constant-time) operations, whereas foldRight, reduceRight, last are inefficient (linear-time) operations. Clearly, there must be a collection type that is a right-handed list for those situations where we need to take advantage of foldRight, etc.
But there isn’t!
Isn’t that a lacuna? Something that should be there but isn’t? I’ve twice tried to implement such a list — and, believe me, it isn’t trivial. I’ve tried to adapt the abstract class List but all (or most) of the traits that it extends are also left-biased. Thus, such a right-handed list could not even extend Seq. I’ve also tried to implement it with a class that has two parameters: a List and a direction. To reverse the list, we simply switch the direction. But, it gets very complicated and in the end, I didn’t do anything with it.
So, if you had one, how would you use it?
Here’s an example situation: implementing merge sort for lists, i.e. without copying it into an array and then sorting the array. We’re not looking for efficiency here — far from it. The usual strategy of copying/sorting/copying will be much more efficient. What we’re looking for is elegance and referential transparency.
Here’s an eager version of the sort method using a tail-recursive merge method:
def sort[X: Ordering](xs: List[X]): List[X] = xs match {
case Nil | _ :: Nil => xs
case _ =>
@tailrec
def merge(result: List[X], l: List[X], r: List[X]): List[X] =
(l, r) match {
case (_, Nil) => result ++ l
case (Nil, _) => result ++ r
case (h1 :: t1, h2 :: t2) =>
if (implicitly[Ordering[X]].compare(h1, h2) <= 0)
merge(result :+ h1, t1, r)
else
merge(result :+ h2, l, t2)
}
val (l, r) = xs.splitAt(xs.length / 2)
val (ls, rs) = (sort(l), sort(r))
merge(Nil, ls, rs)
}This code is elegant, referentially transparent, and it works!
Unfortunately, as you might predict when you see the use of the :+ method on a List, it’s going to be slow. Yes, it really is far too slow. But that (temporary) result parameter doesn’t actually need to be in its proper order while the recursion is taking place. As long as we fix it at the termination of the recursion, all should be well. Here is the corresponding lazy version:
def sort[X: Ordering](xs: List[X]): List[X] = xs match {
case Nil | _ :: Nil => xs
case _ =>
@tailrec
def merge(result: List[X], l: List[X], r: List[X]): List[X] =
(l, r) match {
case (_, Nil) => result.reverse ++ l
case (Nil, _) => result.reverse ++ r
case (h1 :: t1, h2 :: t2) =>
if (implicitly[Ordering[X]].compare(h1, h2) <= 0)
merge(h1 :: result, t1, r)
else
merge(h2 :: result, l, t2)
}
val (l, r) = xs.splitAt(xs.length / 2)
val (ls, rs) = (sort(l), sort(r))
merge(Nil, ls, rs)
}This runs significantly faster. It’s just not very elegant with those reverse method calls. BTW, :: is essentially the same as +: in this context.
But, if we had a right-handed list available for the declaration of result, we could write:
result.toList ++ r
...
result.toList ++ land
merge(result :+ h1, t1, r)
...
merge(result :+ h2, l, t2)I realize it’s only a very minor improvement in elegance but, for me, it was worth trying to find or develop a right-handed list.
Let’s pause for a moment and think about the List type. We can also use it as an immutable Stack (a first-in-last-out structure). In other words, it is serving as a reversing agent. The first element we add to our (empty) result, is the last to appear in an iteration — and that’s the reason that we must perform a reverse.
What if we used a data structure that doesn’t have this reversing property? In other words, what if we used a Queue? It works just as you’d expect — no explicit reversal is required. Here’s the most elegant version of the code:
def sort[X: Ordering](xs: List[X]): List[X] = xs match {
case Nil | _ :: Nil => xs
case _ =>
@tailrec
def merge(result: Queue[X], l: List[X], r: List[X]): List[X] =
(l, r) match {
case (_, Nil) => result ++: l
case (Nil, _) => result ++: r
case (h1 :: t1, h2 :: t2) =>
if (implicitly[Ordering[X]].compare(h1, h2) <= 0)
merge(result += h1, t1, r)
else
merge(result += h2, l, t2)
}
val (l, r) = xs.splitAt(xs.length / 2)
val (ls, rs) = (sort(l), sort(r))
merge(Queue.empty, ls, rs)
}This is the final elegant and referentially transparent version of merge sort*. However, I must admit that it works a little more efficiently (by a factor of about 25% perhaps) if we make our Queue mutable rather than immutable. And, somewhat sadly, neither of these Queue-based implementations can match the speed of the lazy List-based implementation shown above.
*Wait! Naturally, I didn’t like having two similar lines of form result ++: x and two calls to merge. I avoided these DRY aspects by creating a new class with an appropriate unapply method for pattern-matching. It does improve the look slightly, but it’s a technique that has little to do with left/right-handed lists.
