Extending Scala collections: One based Array index exercise

Question

As an exercise, I'd like to extend the Scala Array collection to my own OneBasedArray (does what you'd expect, indexing starts from 1). Since this is an immutable collection, I'd like to have it return the correct type when calling filter/map etc.

I've read the resources here, here and here, but am struggling to understand how to translate this to Arrays (or collections other than the ones in the examples). Am I on the right track with this sort of structure?

class OneBasedArray[T] 
  extends Array[T] 
  with GenericTraversableTemplate[T, OneBasedArray]
  with ArrayLike[T, OneBasedArray]

Are there any further resources that help explain extending collections?

Answer 1

• For a in depth overview of new collections API: The Scala 2.8 Collections API
• For a nice view of the relation between main classes and traits this

By the way I don't think Array is a collection in Scala.

Answer 2

Here is an example of pimping iterables with a method that always returns the expected runtime type of the iterable it operates on:

import scala.collection.generic.CanBuildFrom

trait MapOrElse[A] {
  val underlying: Iterable[A]

  def mapOrElse[B, To]
      (m: A => Unit)
      (pf: PartialFunction[A,B])
      (implicit cbf: CanBuildFrom[Iterable[A], B, To])
      : To = {

    var builder = cbf(underlying.repr)        

    for (a <- underlying) if (pf.isDefinedAt(a)) builder += pf(a) else m(a)

    builder.result
  }
}

implicit def toMapOrElse[A](it: Iterable[A]): MapOrElse[A] =
  new MapOrElse[A] {val underlying = it}

The new function mapOrElse is similar to the collect function but it allows you to pass a method m: A => Unit in addition to a partial function pf that is invoked whenever pf is undefined. m can for example be a logging method.

Answer 3

An Array is not a Traversable -- trying to work with that as a base class will cause all sorts of problems. Also, it is not immutable either, which makes it completely unsuited to what you want. Finally, Array is an implementation -- try to inherit from traits or abstract classes.

Answer 4

Array isn't a typical Scala collection... It's simply a Java array that's pimped to look like a collection by way of implicit conversions.

Given the messed-up variance of Java Arrays, you really don't want to be using them without an extremely compelling reason, as they're a source of lurking bugs.

(see here: http://www.infoq.com/presentations/Java-Puzzlers)

Creaking a 1-based collection like this isn't really a good idea either, as you have no way of knowing how many other collection methods rely on the assumption that sequences are 0-based. So to do it safely (if you really must) you'll want add a new method that leaves the default one unchanged:

class OneBasedLookup[T](seq:Seq) {
  def atIdx(i:Int) = seq(i-1)
}

implicit def seqHasOneBasedLookup(seq:Seq) = new OneBasedLookup(seq)

// now use `atIdx` on any sequence.

Even safer still, you can create a Map[Int,T], with the indices being one-based

(Iterator.from(1) zip seq).toMap

This is arguably the most "correct" solution, although it will also carry the highest performance cost.