PFDS Section 2.2

Section 2.2 presents immutable sets implemented with unbalanced binary search trees, a slightly more complex example of immutable data sharing than the list example in Section 2.1. My first challenge was to reimplement Okasaki’s base implementation of unbalanced binary search tree sets using idiomatic Scala. I had to learn a fair amount more about Scala’s type system to be able to write such an implementation, so I figured I’d write up some of the things I learned about Scala in the process as well as the implementation.

A generic trait for sets

Okasaki’s set interface contains two methods, insert and member. Similar to the generic stack trait implementation that I wrote about last time , it’s easy to create this interface as a generic trait in Scala.

Unbalanced binary search trees

Unbalanced binary search trees are a great choice for a simple implementation of Okasaki’s set interface, since insert and member in an unbalanced binary search tree both take on average O(log n) time in the number of elements in the tree, or O(n) time in the pathological case where each subsequent insert is greater than the last.

I decided to follow Okasaki’s functor-like pattern for the implementation, so I wrote a simple binary tree data type using case classes. This allowed me to use Scala’s pattern matching feature in my implementation of the binary search tree.

Binary search trees rely on the ordering of the type of element that they’re storing, so a generic binary search tree implementation similarly must require that its type parameter has an order. In Scala, this can be accomplished with either of two methods: either by using a view bound on the type parameter to require that it be implicitly convertable to an Ordered type, or by requiring an instance of Ordering, parameterized on the binary tree’s input type, as a value parameter.

In trying to write the most Scala-idiomatic version of the data structure, I ended up investigating both methods before deciding on one, since it wasn’t obvious at first which method would be the simplest. If you’re already familiar with Scala view bounds and type orderings, or if you just want to get to the implementation of the 2.2 data structures already, then you should skip right ahead to the implementation.

View bounds

A view bound is specified by the <% operator. Specifying T <% U in a type parameter adds the restriction that the type parameter T must be implicitly convertible to U, which is true when there exists a method implicit def t2u(t: T): U somewhere in the current scope. In our case, we’re interested in view bounding T by Ordered[T], which will give us access to the comparison methods (<, >, etc) defined on the Ordered[T] type for values of type T.

For example, to implement a generic less-than function lt that utilizes the < method on the input type’s Ordered implementation, we write

def lt[T <% Ordered[T]](x: T, y: T): Boolean = x < y

Without specifying the view bound on T, we would not have access to the < method on x, since it is not defined for any arbitrary type T.

Ordering instances

The other Scala-idiomatic way to provide or access the ordering of a type T is through objects that implement the trait Ordering[T]. An object that implements Ordering[T] provides the compare(x: T, y: T) method, which acts as the underlying implementation for the trait’s other methods, which include lt(x: T, y: T), gt(x: T, y: T), and the like.

For example, to implement a generic less-than function lt that utilizes the lt method on the input type’s Ordering implementation, we could write the curried method

def lt[T](x: T, y: T)(implicit val ordering: Ordering[T]): Boolean = ordering.lt(x, y)

Note that we don’t have to specify a type bound on T, but we still ensure that T is comparable at the type system level by requiring as an argument an ordering object that’s parameterized on T. We make the ordering an implicit and curried argument, so that if T has an implicit conversion to Ordering[T], as most of Scala’s comparable types do, the user doesn’t have to explicitly pass in the ordering.

Using instances of Ordering[T] makes your code slightly less pretty, as you can no longer write x < y, you have to instead write ordering.lt(x, y), but it makes more explicit what’s going on under the hood. It wouldn’t necessarily be obvious that writing x < y where x and y are instances of type T <% Ordered[T] actually invokes the < method on whatever Ordered[T] object x and y are implicitly convertible to. I think I prefer the more explicit version using Ordering[T], but that’s probably because using implicit conversions at all leaves me with a funny taste in my mouth. It seems to me that overusing implicit conversions would lead to a special hell of confusing spaghetti code.

Scala implementation of unbalanced binary tree sets

For the implementation, I wrote the actual insert and member logic as private methods on a utility object. The class that actually implements the Set trait uses the utility object as its underlying implementation. I used Scala’s companion object idiom to structure the whole thing in an elegant way.

Here’s the companion object that contains the underlying implementation logic:

And here’s the class that actually implements the Set interface using the companion object:

You can see the code in its entirety, as well as a small unit test, on GitHub. Next time I’ll implement solutions for section 2.2’s exercises.