Functional Scala: List sugarization

In the last episode we started to look at persistent list-like data structures. We came up with an algebraic datatype which allows to construct arbitrary lists, featuring parametric polymorphism with regard to the type of the lists content. So far, we didn’t see the non-destructive nature of those datatypes when it comes to updating a given list or removing some elements.

Bear with me. We’re going to inspect a bulk of widely accepted, commonly used list functions, operating on persistent data structures in a non-destructive way! But before, we’ll need to prepare ourself with a set of tools for an easier way of tinkering with our list-like data structure.

Syntactic sugar

First of all, let’s add some syntactic sugar to our list type. You may remember that building a list was a bit cumbersome. We always needed to use our value constructor Cons in a nested form, beginning with the empty list object EmptyLst as the final tail:

val intList :Lst[Int] = Cons( 1, Cons( 2, Cons( 3, EmptyLst ) ) )
val stringList :Lst[String] = Cons( "a", Cons( "b", Cons( "c", EmptyLst ) ) )

Clearly we can see the recursive structure of our list type, but declaring or reading a certain list instance seems a bit laborious. Unfortunately, Scala doesn’t allow infix notation for function application, so we can’t come up with a function which simply prepends another element to a given list and use that for cushy list construction, like 1 ‘prep’ 2 ‘prep’ EmptyLst. For a kind of workaround, we’ll now leave the pure functional path for a moment and make use of Scalas object oriented features. What about adding a (pure) method to our list type, which let’s us apply a new element to a given list instance. The method then simply constructs a new list for us by prepending the passed value as the new head and the given list as the tail. Observe:

sealed abstract class Lst [+A]{
    // compile error: covariant type A occurs in contravariant position in type A of value x
    def +: ( x :A ) :Lst[A] = Cons( x, this )
}

Before we get to that compile error, let’s firstly take a look at the methods +: core intention: we just wanna apply a new value x to our function, which should be of the same type as the already given type of the given lists content. We then simply construct and return a new list value which consists of the new element x as the head and the given list as the tail, just as said. It’s just a helper function which hides the manual list construction based on the value constructor Cons.

Unfortunately it won’t compile! Remember the last episode were we introduced covariance for type parameter A? We did so, because we wanted to share our empty List as a single object for all of our list instances as the final tail. For that, this single object needed to be a subtype for all possible list instances in A. Now we have to play the game of covariance for A! And this means, that we have to allow to prepend an element which might be of a supertype of A. In that case, the newly constructed list is type parametrized by that more general type. So the following definition should work, since we just leverage Scalas power to simply apply a lower type bound for our new element to prepend:

sealed abstract class Lst [+A]{
    def +:[S >: A] ( x :S ) :Lst[S] = Cons( x, this )
}

Now x can be of any type S which may be of the same type as A or a supertype of A. We finally result into a list which contains elements, for which S is the most specific type. Now, with our new helper method +: at hand, list construction can be done in a more concise way:

val lst :Lst[Int] = 1 +: 2 +: 3 +: 4 +: 5 +: EmptyLst
val anotherLst :Lst[Any] = 1 +: "a" +: 2 +: "b" +: EmptyLst

Ahhh, now we got a much shorter way of defining new list instances. As you could see with anotherLst, the type of the lists content is Any, since it’s the most specific type for Int and String. There’s only one little thing that may get you into baffling mode. Taking above list anotherLst for example, it looks like we’re calling method +: on value 1 for prepending it to value “a”. But that’s not the case! As soon as our method ends with a colon, it’s gonna be called in a right associative manner. That is, +: is first called on EmptyLst for prepending value “b”, resulting into an instance of Lst[String]. Then +: is again called on that list instance, prepending value 2. Since that value is of type Int, we end up with a new list of type Lst[Any] and so on and so on …

Pattern matching

Ok, now we got a fancy tool for list construction, but what about deconstructing lists by pattern matching? As you surely remember from some older episodes, pattern matching is one of the main tools for operating on algebraic datatypes. And since our list type is defined in the tradition of algebraic datatypes, we shouldn’t have any problems to use pattern matching upon the given value constructors of our list type. For example, let’s determine the length of a given list by defining an appropriate function:

val length : Lst[_] => Int = _ match{
    case EmptyLst => 0
    case Cons( _ , tail ) => 1 + length( tail )
}

That wasn’t too complicated. We just accept arbitrary lists with an arbitrary content type by stating an existential type for our list argument in the functions signature. We then simply deconstruct the given list, decomposing it into its head and tail (the rest of the list) until we reach the empty list, each time adding 1 to the length for each element we’ll find all the way down. If you’re not worrying about the unbalance for using value constructor Cons for deconstruction while using our new method +: for construction, everything is fine. But things get more ugly pretty fast again, if we need to pattern match against more than a single head and tail of a list.

For example, let’s write a function which delivers the last element of a list. For doing that, we need to get past two considerations. First, we wanna preserve the type of the lists content. If we want to retrieve the last element for a list of Strings, we should return a String. If it’s a list of Ints, we’d like to return an Int value! For that to achieve, our function need to be polymorphic in the type of the lists content. As we figured out in an earlier episode, this is best done (and even the idiomatic way) by providing a polymorphic method instead of a function value within a polymorphic environment:

def last[A]( lst :Lst[A] ) : A = ...

Second, how do we wanna operate upon an empty list, since there’s simply no last element which we could hand out. For handling the possible absence of a last element we’re going to use type Option, which suits this kind of dilemma to a T: we simply return a value of Option[A] which is just None in the case of an empty list. That way, we stay really honest about the type of our return value (while simply returning null wouldn’t be honest at all, as Dr. Erik Meijer now would say). So we end up with a function like this:

def last[A]( lst :Lst[A] ) : Option[A] = lst match {
    case EmptyLst => None
    case Cons( x, EmptyLst ) => Some( x )
    case Cons( _ , Cons( x, xs ) ) => last( Cons( x, xs ) )
}

Admitted, it’s a somewhat contrived example, since we needn’t to pattern match againt the first two elements and the rest of the list explicitly (as you may see in the third case expression at line four). Let’s simply say we wanted to communicate that constitution of the list (in that the list contains at least two elements) in a very definite way. Anyway, you might see, that using value constructor Cons for deconstructing more than a single head and tail leads again to very cumbersome patterns!

Fortunately, we already know about Extractors as another way to define patterns which are somewhat independent of the structure of value constructors. So what speaks against an Extractor which allows us to form patterns, kind of mimicing the way we construct lists via method +: ? Therefore, we just name such an Extractor object like our construction method. Just watch:

object +: {
    def unapply[A]( x: Lst[A] ) : Option[ (A, Lst[A]) ] = x match {
        case Cons( hd, tl ) => Some( (hd, tl) )
        case _ => None
    }
}

So now we just could come up with a nice pattern declaration which really looks like list notations at the construction side. This way, we just recovered the balance between the form of construction and deconstruction:

def last[A]( lst :Lst[A] ) : Option[A] = lst match {
    case EmptyLst => None
    case x +: EmptyLst=> Some( x )
    case _ +: x +: xs => last( x +: xs )
}

Now pattern matching is fun again, since forming patterns don’t differ from forming list instances any more. In fact, we could kind of hide our value constructor Cons from the eyes of our users. We simply don’t need to know about it, wether on construction, nor on deconstruction side.

Now, to bring this episode to a close, let’s define just another little function show, which simply converts a given list into an appropriate string representation. This string representation might also resemble the form of a list, like we use for construction and deconstruction:

def show( lst :Lst[_] ) :String = lst match {
    case EmptyLst => "EmptyLst"
    case x +: xs 	=>  x + " +: " + show( xs )
}
...
val lst :Lst[Int] = 1 +: 2 +: 3 +: 4 +: 5 +: EmptyLst
...
val lstShow :String = show( lst )   // results into ''1 +: 2 +: 3 +: 4 +: 5 +: EmptyLst''

Here we just cheated a bit, since we rely on method toString for the string representation of the given list values. To get back to a more functional style, there should be another show function for turning those values into an appropriate string representation, too. The question is how do we enforce that such a function need to exist for any list value type. There we just detected the need for some more powerful constraints which we’ll adress when looking at type classes (but that will be within an episode in the distant future).

Summary

In this eposide we just set the stage for writing all those commonly used list functions in a more comfortable way.

First, we added some syntactic sugar for easier list construction. For there’s no way of doing infix function application, we provided an appropriate helper method for our list type which simply takes a new element and builds a new list, obeying covariance. We’re now able to construct a new list in a right associative way, since Scala calls every method which ends with a colon on the object at the right side of the method call.

We finally found a nice way to form pattern expressions to use within pattern matching which kind of mimic the same notation as for list construction. There, we just leveraged the idea of Extractors for providing an appropriate instance which is named after the method for building lists by prepending values. This way, we kind of established a nice notational balance between list construction and deconstruction.

Now we got some nice tools for defining a whole bunch of list functions, like inserting, replacing or removing elements in an easy, concise way. As you’ll see, we’ll doing so in a completely non-destructive way. But that’s the topic for another episode. Hope to see you there …