Wed 22 Jul 2009
Building A Simple Scala List From Scratch
Posted by Matt under General, Scala
No Comments
In Java you don’t see a lot of linked lists, and if you do it’s almost always java.util.LinkedList. People never write their own lists. They don’t really need to, I suppose. The one from java.util is fine. Plenty of people are leading fulfilling software careers never having implemented their own linked list. But it’s kind of a shame. Knowing how your data structures work makes you a better programmer.
It’s even rarer for a person to implement his own linked list in Scala. Scala’s scala.List is one of the most used classes in the language, so it’s packed with functionality. It’s abstract, covariant, it has helper objects such as List and Nil and the little-known ‘::’ class, it inherits from Product, Seq, Collection, Iterable, and PartialFunction. The machinery of List pulls in Array, ListBuffer, and more. It can be hard to take it all in.
So let’s build our own linked list. We’ll start out with something very basic and un-Scala-like. Then we’ll improve it gradually until we have something a little closer to scala.List. I encourage you to fire up your Scala interpreter and follow along.
Back to Basics
First, a short review of linked lists. A linked list is a chain of nodes, each referring to exactly one other node until you get to the end of the chain. You refer to the list by its first item and you follow the chain of references to reach the other nodes.
What are the requirements for our first try? Our node should be able to hold a piece of data, and refer to the next node. It should also be able to report its length, and provide a toString method so we can visualize the list. Here we go.
class MyList(val head: Any, val tail: MyList) {
def isEmpty = (head == null && tail == null)
def length: Int = if (isEmpty) 0 else 1 + tail.length
override def toString: String = if (isEmpty) "" else head + " " + tail
}
The value ‘head’ holds the data for the node, ‘tail’ refers to the next element in the chain. The ‘isEmpty’ method is true if the head and tail are both null. The length and toString methods are both defined using a similar pattern: if (isEmpty) [base result] else [data for current node + result of same method on tail].
Here’s what it looks like when we use this class:
scala> var list = new MyList(null, null)
list: MyList =
scala> list.length
res0: Int = 0
scala> list.isEmpty
res1: Boolean = true
scala> list = new MyList("ABC", list)
list: MyList = ABC
scala> list.length
res3: Int = 1
scala> list.isEmpty
res4: Boolean = false
scala> list = new MyList("XYZ", list)
list: MyList = XYZ ABC
scala> list = new MyList("123", list)
list: MyList = 123 XYZ ABC
scala> list.tail.head
res7: Any = XYZ
Not bad. It gets the job done. But it has some problems. First is the use of ‘null’. Use of null references is sloppy and increases the odds of a null pointer exception so, ideally, we don’t want to see that. It has other problems, too. It’s too verbose. It’s not typesafe. But for now let’s concentrate on getting rid of the nulls.
No Nulls Is Good Nulls
How can we do it? We’re using the null as a special value, a marker to tell us when a node is at the end of a list. So we’ll just use something else as that marker instead. What can we use? We’ll create a special object for the empty list. It will be recognized as empty just based on its identity, not on null values. So let’s try it:
class MyList(val head: Any, val tail: MyList) {
def isEmpty = false
def length: Int = if (isEmpty) 0 else 1 + tail.length
override def toString: String = if (isEmpty) "" else head + " " + tail
}
object MyListNil extends MyList("arbitrary value", null) {
override def isEmpty = true
}
That’s better. (The observant reader will note the similarity of MyListNil to scala.List’s Nil object.) We got rid of the nulls in the isEmpty method, but we still have to put something in the head and tail parameters of the MyList constructor. We put an arbitrary non-null value in head, but what do we put for tail? Either null or create a new MyList. And how can that MyList be instantiated? It also needs a tail. Vicious circle. So this solution leaves us still stuck with a null.
Earlier, the null was there to mark a special node. We factored out that usage. Now it’s there to allow us to create the MyListNil. How can we factor that out? MyListNil is required to call its parent’s constructor. What if had no parent? Then it wouldn’t be a MyList anymore. What if it had an abstract parent? Now you’re talking. Let’s see what that would look like.
abstract class MyList {
def head: Any
def tail: MyList
def isEmpty: Boolean
def length: Int
}
class MyListImpl(val head: Any, val tail: MyList) extends MyList {
def isEmpty = false
def length: Int = 1 + tail.length
override def toString: String = head + " " + tail
}
object MyListNil extends MyList {
def head: Any = throw new Exception("head of empty list")
def tail: MyList = throw new Exception("tail of empty list")
def isEmpty = true
def length = 0
override def toString = ""
}
It’s a little more code, but much neater. There are no nulls anywhere. Here’s how it looks when we use this new MyList:
scala> var list: MyList = MyListNil
list: MyList =
scala> list = new MyListImpl("ABC", list)
list: MyList = ABC
scala> list = new MyListImpl("XYZ", list)
list: MyList = XYZ ABC
scala> list = new MyListImpl("123", list)
list: MyList = 123 XYZ ABC
scala> list.length
res3: Int = 3
scala> list.tail.head
res4: Any = XYZ
scala> list.tail.tail.tail.head
java.lang.Exception: head of empty list
at ...
Pretty neat. The equivalent of MyListImpl in the Scala’s real List implementation is a class called ‘::’, which has that funny name, by the way, because it looks nice in pattern matching code. Sometimes ‘::’ is referred to as cons. With nulls finally eliminated, we can concentrate on other issues.
Brevity Is The Heart Of List
The thing that I notice at this point is that a lot of typing (on the keyboard) is required to use this list. We have to type out “list = new MyListImpl(…, list)” every time we add an item. We can improve this with a new method.
abstract class MyList {
[...]
def add(item: Any): MyList = new MyListImpl(item, this)
}
Now we have classes referring to each other. MyList creates new MyListImpls, and MyListImpl extends MyList. So you’ll need to put these classes in a .scala file and compile them instead of just typing them into the Scala interpreter. But, wow! Look how much easier it is to use MyList now:
scala> var list = MyListNil add("ABC") add("XYZ") add("123")
list: MyList = 123 XYZ ABC
scala> list.length
res1: Int = 3
So much easier! One thing I notice, though, is that the order of items in the code is different from the order produced by toString. We can change our ‘add’ method so that is right-associative instead of left-associative by using a method name that ends in ‘:’ (colon). We’ll use ‘::’ as the method name since that’s what scala.List uses.
abstract class MyList {
[...]
def ::(item: Any): MyList = new MyListImpl(item, this)
}
scala> var list = "ABC" :: "XYZ" :: "123" :: MyListNil
list: MyList = ABC XYZ 123
Now we’re really getting somewhere. This is starting to look more like scala.List. One other thing that the standard list implementation gives you is a shortcut for initializing lists. It looks like “List(1, 2, 3, 4)”. Notice there’s no ‘new’ keyword. This is done using the scala.List helper object and its ‘apply’ method. Below is our own MyList helper object.
object MyList {
def apply(items: Any*): MyList = {
var list: MyList = MyListNil
for (idx <- 0 until items.length reverse)
list = items(idx) :: list
list
}
}
scala> var list = MyList("ABC", "XYZ", "123")
list: MyList = ABC XYZ 123
scala> list = "Cool" :: list
list: MyList = Cool ABC XYZ 123
Better Type-Safe Than Sorry
Better. Our code looks much neater now when we use MyList. I’ll introduce just one more improvement to MyList. It still has a rather glaring problem. It provides no type information. It keeps all of its data using a reference to Any. If you don’t see why this is a problem, let’s see what happens when we want to get the length of some items in a MyList:
scala> var list = MyList("ABC", 12345, "WXYZ")
list: MyList = ABC 12345 WXYZ
scala> list.head.length
<console>:6: error: value length is not a member of Any
list.head.length
^
scala> list.head.asInstanceOf[String].length
res10: Int = 3
scala> list.tail.head.asInstanceOf[String].length
java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String
at .<init>(<console>:6)
Ouch! First, when we try to call method ‘length’ on list.head Scala complains that list.head is a reference to Any. Any doesn’t have a length method. This isn’t a dynamically typed language like, say, Ruby. An object has to have the right type before we can start calling methods. What to do? You could implement a MyStringList where the head has type String. But then you’ll need a MyIntList, MyDoubleList, etc. What we need is a way to specify the type of data in the list when we create the MyList instance. What we need is a type parameter.
Here’s the complete MyList code using a type parameter, and a little demonstration code:
abstract class MyList[A] {
def head: A
def tail: MyList[A]
def isEmpty: Boolean
def length: Int
def ::(item: A): MyList[A] = new MyListImpl[A](item, this)
}
class MyListImpl[A](val head: A, val tail: MyList[A]) extends MyList[A] {
def isEmpty = false
def length: Int = 1 + tail.length
override def toString: String = head + " " + tail
}
object MyListNil extends MyList[Nothing] {
def head: Nothing = throw new Exception("head of empty list")
def tail: MyList[Nothing] = throw new Exception("tail of empty list")
def isEmpty = true
def length = 0
override def toString = ""
}
object MyList {
def apply[A](items: A*): MyList[A] = {
var list: MyList[A] = MyListNil.asInstanceOf[MyList[A]]
for (idx <- 0 until items.length reverse)
list = items(idx) :: list
list
}
}
scala> var list = MyList("ABC", "WXYZ", "123")
list: MyList[java.lang.String] = ABC WXYZ 123
scala> list.head.length
res0: Int = 3
scala> 3.14159 :: list
<console>:6: error: type mismatch;
found : Double
required: java.lang.String
3.14159 :: list
^
scala> var list = MyList("ABC", 123, 3.14159)
list: MyList[Any] = ABC 123 3.14159
Look at line 32. The “MyList(…)” returns a MyList[String]. Scala figures out from the parameters what type to use. In line 35, you can see how much easier it is to use the list contents when you know the type at compile time.
If you try to mix types, as in line 45, Scala determines the nearest common ancestor of the types (Any, in this case) and uses that. However, if the type parameter is already determined, as in line 38, it won’t change when you try to add data of a different type. To make line 38 work, we can make a small change to the ‘::’ method:
abstract class MyList[A] {
[...]
def ::[B >: A](item: B): MyList[B] =
new MyListImpl(item, this.asInstanceOf[MyList[B]])
}
scala> var list = MyList("ABC", "XYZ")
list: MyList[java.lang.String] = ABC XYZ
scala> 3.14159 :: list
res0: MyList[Any] = 3.14159 ABC XYZ
This says that ‘::’ takes a parameter of type B, which is either A or a superclass of A, and returns a MyList[B]. So if you have a MyList[String] and you call ‘::’ on it with a Double parameter, Scala figures out that although Double is not a superclass of String, String and Double are both descendants of Any, and it returns a MyList[Any].
Conclusion
That’s a good stopping point for now. Obviously you can take the MyList class a lot further and add a lot more methods, but we’ve created some code that approximates the basics provided by scala.List. In fact, you could take several of the scala.List methods (foldLeft, for example) and basically drop them right into MyList and they’d work fine.
