technology from back to front

A study in Scala

Cards on the table: I like Scala. Right now it’s my go-to general purpose programming language, but I know that many people have a dim opinion of it, or appreciate its positives but are heavily conflicted by its negatives. Actually I do put myself in that latter camp, though I think I’ve got deep enough into learning the language that I can get past most of those negatives. Here I present a classic tale of “life with Scala”.

The problem

Scala generally has collection methods for most things you can think of, so I was pleased but not surprised to find inits and tails methods, that list all of the prefixes and suffixes respectively. These methods return an iterator, hence the use of toList below, to actually see the results. For the rest of this post, we’ll just consider inits, though tails is trivially similar.

scala> List(1,2,3).inits
res1: Iterator[List[Int]] = non-empty iterator

scala> List(1,2,3).inits.toList
res2: List[List[Int]] = List(List(1, 2, 3), List(1, 2), List(1), List())

scala> List(1,2,3).tails.toList
res3: List[List[Int]] = List(List(1, 2, 3), List(2, 3), List(3), List())

The results include the empty collection, but as it happens that doesn’t suit my needs. I want a version that doesn’t return the empty list.

What to do?

Options include:

  • Call the existing inits method then strip off the last item. However since we get an iterator this isn’t quite so trivial – we can’t just do inits.init
  • Write a new custom method to do just what I want and return a collection, not an iterator.

I decided, in the spirit of Scala, that I would add a nonEmptyInits method to ‘all collections’ (and I’m deliberately vague here) via an implicit conversion, so that it can be called just as easily as inits. It would call inits but wrap the iterator to exclude the final element. Easy peasy, but the rabbit hole loomed ahead of me.

Because I was over-engineering and trying to be purist (this was hobby code) I wanted to implement my new method for the most generic type reasonable. Figuring out what type that was challenged me rather. The Scala collections API has a fairly complicated hierarchy. This is somewhat diagrammed and explained in the documentation but that doesn’t show all the interim traits and classes that are in the guts of the implementation such as TraversableLike, GenTraversable, GenTraversableLike and 10+ others relating just to Traversable. The API is setup to support some very clever facilities, like generic collection methods typically returning collections of the same type you started with. Apparently most libraries can’t/don’t do this. However it made it hard for me to find the right place to start. Ultimately I settled on Traversable, since inits itself is defined in TraversableLike, but adding to that directly seemed like more trouble than it was worth.

implicit class TraversableExtras[T](t: Traversable[T]) {
  def nonEmptyTails: Iterator[Traversable[T]] = {
    val bufferedInits = t.inits.buffered
    new Iterator[Traversable[T]] {
      def hasNext() = bufferedInits.head.nonEmpty
      def next() = bufferedInits.next()
    }
  }
}

My solution above wraps the iterator with a buffered version, so that I can peek at head and determine whether to end early or not. This is fairly nice and simple and I’m quite happy with it. It means we can do the following, via the magic of implicit conversions.

scala> List(1,2,3,4).nonEmptyTails.toList
res7: List[Traversable[Int]] = List(List(1, 2, 3, 4), List(1, 2, 3), List(1, 2), List(1))

But Arrays mess it all up

This is all looking very promising and straightforward, but it took a fair bit of banging my head against the desk to figure out why the compiler wouldn’t let me call it on an Array.

scala> Array(1,2,3).nonEmptyTails
:9: error: value nonEmptyTails is not a member of Array[Int]

To cut a long story short, though we can seamlessly treat Array as a Traversable, Array is actually somewhat special. It maps to Java arrays for implementation reasons, but supporting generics, and with an implicit conversion to WrappedArray, which is a Seq (and hence a Traversable) to provide all the collection methods we’re used to. So far so good, but it turns out that the compiler cannot apply more than one implicit conversion at a time, as the search space would explode. Hence it cannot convert from Array to WrappedArray to my TraversableExtras. A solution in such a case, where we want two conversions, is to explicitly cast the Array, to make the first conversion explicit, then the compiler does the rest.

scala> (Array(1,2,3): Traversable[Int]).nonEmptyTails
res10: Iterator[Traversable[Int]] = non-empty iterator

Wrap-up

Finally I got where I wanted, even if that cast is a bit irritating, and I learned a lot of useful things in the process – all part of the journey of familiarity with any language. But it struck me as soon as I got a bit lost in the Scala collections hierarchy that I was on a mission with which I am all too familiar. It was at that point that I decided I would probably blog about the experience and started taking notes!

I still like Scala, but I’m very well aware that this is the price I pay, and I’m not surprised that others find it too high a price.

Just to be clear…

I realise by the way that this was all a fools errand in the first place. I deliberately went down the path described above as an explicit learning exercise because I wanted to get more experience with the collections API, iterables, implicits etc. It is possible to achieve the result more directly with a filter:

scala> Array(1,2,3).inits.filter(_.nonEmpty).toList
res16: List[Array[Int]] = List(Array(1, 2, 3), Array(1, 2), Array(1))

It’s not quite as pithy as having a nonEmptyTails method, but in all other senses it’s probably superior.

by
Sam Carr
on
10/02/14
  1. Nice! I note that the return type of your nonEmptyTails function is Iterator[Traversable[T]] on all traversable types. If you wanted it to preserve type iteration and be an Iterator[List[T]] on a List[T], Iterator[Seq[T]] on a Seq[T], etcetera, you could try the following implementation:

    import scala.collection.TraversableLike implicit class TraversableExtras[A, Repr <: TraversableOnce[A]](t: TraversableLike[A, Repr]) { def nonEmptyTails: Iterator[Repr] = { val bufferedInits = t.inits.buffered new Iterator[Repr] { def hasNext() = bufferedInits.head.nonEmpty def next() = bufferedInits.next() } } }

    TraversableLike has a second type parameter (called Repr here) which is the type of the collection itself, therefore we can return a value of that type rather than a plain Traversable, in order to preserve the type information in the result. Note that this also means that we have to introduce a constraint that Repr is a subtype of TraversableOnce here – this is so the compiler can prove that the nonEmpty operation is available on it.

    Thanks!

    Tim

  2. Sam Carr
    on 10/02/14 at 4:50 pm

    Thanks Tim – that’s really helpful. It was that second type parameter of TraversableLike that originally put me off and had me go with Traversable :-)

 
 


− one = 3

2000-14 LShift Ltd, 1st Floor, Hoxton Point, 6 Rufus Street, London, N1 6PE, UK+44 (0)20 7729 7060   Contact us