I have been studying the Scala programming language by Martin Odersky and his lab in great depth recently and I really like what I see. Scala is a very effective blend of functional, imperative and object oriented techniques and has a practical minded design despite supporting very advanced techniques.

I was perusing the Scala standard library and came upon the library's implementation of List. The implementation was quite idiomatic of the functional style with the member functions expressed mostly in terms of various combinations of Car (head), Cdr (tail), and Cons (::). The implementation was mediochre because many of the functions were not tail-recursive. This meant that the code was very compact and readable ( which I like ), but caused stack overflows on lists of over 1000 elements (which was unacceptable) as well as being inefficient ( which I can live with ).

I decided to try my hand at rewriting the class to see if I could do any better, and I came upon the observation that a list implementation can be entirely expressed in terms of an interface containing simply one function: foreach. I decided to build a set of classes all deriving from a single Sequence trait ( a kind of abstract class) as follows:

  trait Sequence[+a]  {
    def foreach(f: a => unit): unit;
  }

The List trait introduces dozens of functions derived from this as follows (they are not all tested yet, sorry):

  trait List[+a] extends Sequence[a]
  {
    def defaultElement : a =
      null.asInstanceOf[a];

    def apply(n : Int) =
      { var i = 0; foldLeft[a](defaultElement)((xs, x) => { i = i + 1; if (i - 1 == n) x else xs; }); }

    def head : a =
      apply(0);

    def last: a =
      { var i = 0; foldLeft[a](head)((xs, x) => x); }

    def tail : List[a] =
      { var atHead = true; foldLeft[List[a]](Nil)((xs, x) => if (atHead) { atHead = false; Nil } else x :: xs);  }

    def isEmpty: Boolean =
      length == 0;

    def ::[b >: a](x: b): List[b] =
      new diggins.::(x, this);

    def map[b](f: a => b): List[b] =
      foldLeft[List[b]](Nil)((xs, x) => f(x) :: xs);

    def filter(p: a => Boolean): List[a] =
      foldLeft[List[a]](Nil)((xs, x) => if (p(x)) x :: xs else xs);

    def reverse: List[a] =
      foldLeft[List[a]](Nil)((xs, x) => x :: xs);

    def reverseForeach(f : a => unit) =
      reverse.foreach(f);

    def reverseMap[b](f : a => b) : List[b] =
      reverse.map(f);

    def length: Int =
      { var i = 0; var x = this; while (x != Nil) { i = i + 1; x = x.tail; }; i; }

    def count(p : a => Boolean) : Int =
      { var i = 0; foreach(x : a => if (p(x)) { i = i + 1; }); i; }

    def indices: List[Int] =
      { var i = -1; map[Int](x : a => { i = i + 1; i; }); }

    def init: List[a] =
      take(length - 1);

    def take(n: Int): List[a] =
      { var i = -1; filter(x : a => { i = i + 1; i < n; } ); }

    def drop(n: Int): List[a] =
      { var i = -1; filter(x : a => { i = i + 1; i >= n; } ); }

    def takeRight(n : Int): List[a] =
      drop(length - n);

    def dropRight(n : Int): List[a] =
      take(length - n);

    def splitAt(n: Int): Pair[List[a], List[a]] =
      Pair(take(n), drop(n));

    def takeWhile(p: a => Boolean): List[a] =
      { var ret = true; filter(x => if (p(x)) ret else { ret = false; false; }) }

    def dropWhile(p: a => Boolean): List[a] =
      { var ret = false; filter(x => if (p(x)) ret else { ret = true; true; }) }

    def span(p: a => Boolean): Pair[List[a], List[a]] =
      Pair(takeWhile(p), dropWhile(p));

    def negate_predicate[b](p: b => Boolean)(x : b) : Boolean =
      !p(x);

    def break(p: a => Boolean): Pair[List[a], List[a]] =
      span(negate_predicate[a](p));

    def remove(p : a => Boolean) : List[a] =
      filter(negate_predicate[a](p));

    def partition(p : a => Boolean) : Pair[List[a], List[a]] =
      Pair(filter(p), remove(p));

    def forAll(p : a => Boolean) : Boolean =
      { var ret = true; foreach(x => if (!p(x)) ret = false); ret; }

    def exists(p : a => Boolean) : Boolean =
      { var ret = false; foreach(x => { if (p(x)) ret = true }); ret; }

    def contains(elem: Any): boolean =
      exists(x => x == elem);

    def foldLeft[b](z: b)(f: (b, a) => b): b =
      { var ret = z; foreach(x : a => { ret = f(ret, x); }); ret; }

    def foldRight[b](z: b)(f: (a, b) => b): b =
      { var ret = z; reverseForeach(x : a => { ret = f(x, ret); }); ret; }
  }

This also is another trait, and it can not be instantiated. Two concrete classes which implement the List interface are:

  object Nil extends List[All] {
    override def isEmpty = true;
    override def foreach(f: All => unit): unit = error("head of empty list");
  }

  class ::[+a](hd: a, tl: List[a]) extends List[a] {
    override def isEmpty = false;
    override def foreach(f: a => unit): unit =
      { var x:List[a] = this; while (!x.isEmpty) { f(x.head); x = x.tail; } }
    override def head: a = hd;
    override def tail: List[a] = tl;
  }

A rather nifty feature of Scala is that identifiers can be symbols. In this case :: is a name of a class which implements the List interface. We can also use it with infix notation as follows:

  val x : List = 1 :: 2 :: 3 :: nil;

This is however only the tip of the iceberg. Scala also makes it easy to implement lazy lists ala Haskell. I was able to create a lazy list in only a few lines of code as follows:

  class LazyRange(begin_a : int, end_a : int) extends List[int]
  {
    def begin = begin_a;
    def end = end_a;

    override def foreach(f: int => unit): unit =
      { var i = begin; while (i <= end) { f(i); i = i + 1; }; };

    override def apply(n : int) = n + begin;
    override def reverse : LazyRange = new ReverseLazyRange(begin_a, end_a);
    override def length = end - begin;
    override def head = begin;
    override def last = end;
    override def tail = new LazyRange(begin_a, end_a - 1);
  }

I also created an efficient implementation of a list by using an array adapter:

class ArrayRange[a](arr_a : Array[a], begin_a : int, end_a : int) extends List[a]
{
  val arr = arr_a;
  val begin = begin_a;
  val end = end_a;

  override def isEmpty = begin == end;
  override def tail = { if (length == 1) Nil else new ArrayRange[a](arr, begin + 1, end); }
  override def length : Int = { end - begin; }
  override def apply(n : int) : a = { arr(n); }
  override def head = apply(0);
  override def last = apply(length-1);

  override def foreach(f : a => Unit) : Unit = {
    var i = 0;
    while (i < length) {
      f(apply(i));
      i = i + 1;
    }
  }

  override def map[b](f: a => b): ArrayRange[b] = {
    var ret = new Array[b](length);
    var i = 0;
    while (i < length) {
      ret(i) = f(apply(i));
      i = i + 1;
    }
    fromArray[b](ret);
  }

  override def filter(p: a => Boolean): ArrayRange[a] = {
    var i = 0;
    var j = 0;
    var ret = new Array[a](length);
    while (i < length) {
      if (p(apply(i))) {
        ret(j) = apply(i);
        j = j + 1;
      }
      i = i + 1;
    }
    fromArray[a](ret);
  }

  override def reverse : ArrayRange[a] =
    new ReverseArrayRange[a](arr, begin, end);

  def fromArray[b](x : Array[b]) : ArrayRange[b] =
    new ArrayRange[b](x, 0, x.length);
}

I think Scala is one of the strongest new languages to come out in a long time, I encourage everyone to check it out. For more of my Scala code you can see my posts to the mailing list online at http://news.gmane.org/gmane.comp.lang.scala.