Functional Scala: Quiz with Lists – common list functions, handcraftet

Welcome to another episode of Functional Scala!

As promised within the last episode, we’re going to take another detailed look at some more commonly used list functions. As we wanna become well acquainted with the functional side of Scala, we’re again going to implement those list functions one by one. Along the way, we’ll get a better and better understanding on how to apply some of the typical tools within the world of functional programming, like pattern matching, recursion or function composition.

As it turned out, most of us learn best in a synthetical way (that is not by dissecting the frog, but to build one). For that, we’re gonna change the style of the following sections. For every useful function, we’re first looking at their intended behaviour, maybe along with some exemplary showcases. Only when we grasp the intention, we’re trying to come up with a sensible idea for their realization and finally with an implementation. You might consider the whole episode like a little quiz and try to come up with your own solutions before you’ll take a closer look at the presented ones.

I promise, if you take the approach of thinking first of your own, you’ll become much more proficient in writing your own list functions in a more functional style after the end of this episode. So start your favoured development environment and have fun to hack …

A short refresher

All solutions are based on our own list-like data structure, which we’ve invented over the past episodes. For a short refreshment, take a look at the underlying algebraic datatype:

sealed abstract class Lst [+A]{
    def +:[S >: A] ( x :S ) :Lst[S] = new +:( x, this )
}
case object Nl extends Lst[Nothing]
case class +:[A]( x :A, tail :Lst[A] ) extends Lst[A]

You may detected two changes here: first, we renamed our object which represents the empty list from EmptyLst to Nl. This is first of all a conveniance thing. It’s shorter and in the tradition of naming the empty list after the latin word for nothing (nil, nihil). Second, we also renamed our value constructor for consing a head to a given list (as the tail of the newly constructed list). It’s now named +: instead of Cons. This way, we just saved our extractor for doing list deconstruction symmetric to list construction, since we can naturally pattern match on case classes.

Basic list functions

Ok, without any further ado, let’s start with some really basic list functions. We’ve already encountered some of them within the last episode, so i’m not gonna repeat them here again.

empty

Our first function just provides information if a given list is just the empty list or not. So it should behave like in the following samples:

empty( Nl )  // >> true
...
empty( 1 +: 2 +: 3 +: 4 +: 2 +: 5 +: Nl )  // >> false
...
empty( "a" +: "b" +: "c" +: Nl )  // >> false

In this case, we just make use of the fact, that Scalas case classes come with a sensible implementation of == for testing two instances for equality:

def empty( lst :Lst[_] ) =  lst == Nl

head

Here, we’re interested in the head (alas the first element) of a given list. Just look at the examples:

head( Nl )  // >> None
...
empty( 1 +: 2 +: 3 +: 4 +: 2 +: 5 +: Nl )  // >> Some( 1 )
...
empty( "a" +: "b" +: "c" +: Nl )  // >> Some( "a" )

In this case, we can again leverage pattern matching for simply splitting the problem space into two simpler cases – the empty list (for which we return None) and a list with at least one element (for which we return just the first element):

def head[A]( lst :Lst[A] ) : Option[A] = lst match {
    case a +: _  => Some(a)
    case _  => None
}

Of course we also could’ve come up with an unsafe version, which throws an exception in case of an empty list:

def head[A]( lst :Lst[A] ) : A = lst match {
    case a +: _  => a
    case _  => error( "no head on empty list" )
}

tail

This is the complement of the head function, which just returns everything but the head.

tail( Nl )  // >> Nl
...
tail( 1 +: 2 +: 3 +: 4 +: 2 +: 5 +: Nl )  // >> 2 +: 3 +: 4 +: 2 +: 5 +: Nl
...
tail( "a" +: "b" +: "c" +; Nl )  // >> "b" +: "c" +: Nl

The implementation might look like quite similar to the one for head. Maybe pattern matching is a good idea …

def tail[A]( lst :Lst[A] ) : Lst[A] = lst match{
    case _ +: as  => as
    case _  => lst
}

init

You may remember function last from the last episode, which results into the last element of a given list. Now again, init can be seen as the complement of last, which just returns everything but the last element:

init( Nl )  // >> Nl
...
init( 1 +: 2 +: 3 +: 4 +: 2 +: 5 +: Nl )  // >> 1 +: 2 +: 3 +: 4 +: 2 +: Nl
...
init( "a" +: "b" +: "c" +; Nl )  // >> "a" +: "b" +: Nl

This one might be a bit trickier. Again, we could split the whole problem into some simpler sub cases: for the empty list, init is just again the empty list. The first successful and easiest case would be a list which only consists of two elements, so we could just return a new list without the last element before the empty list. For all other cases (where the list consists of more than two elements) we just call init on the tail of the list (which must consist of at least two elements). This recursive call will result into a list without the last element, for which we just prepend the given head of the list:

def init[A]( lst :Lst[A] ) : Lst[A] = lst match {
    case Nl  => Nl
    case a +: last +: Nl  => a +: Nl
    case a +: as  => a +: init( as )
}

List construction

Within this section, we’ll regard some functions which will be convenient to use for constructing some special list instances. Some other functions will also construct new list instances based on some already given lists.

repeat

Say we wanna create a list which consists repeadetly of one and the same given value (we’ll see shortly for what this is good for). Since we can’t produce a list which is going to be produced lazily (this is a topic catched by Scalas Stream type, we’re also going to detect in some further eposide), we can’t come up with a potentially infinite list. So in our case we need to give a number for the length of a list for which we’re saying about how often that value should be repeated within the list:

val as :Lst[String] = repeat( "a", 4 )  // >> "a" +: "a" +: "a" +: "a" +:Nl
...
val ones :Lst[Int] = repeat( 1, 6 )  // >> 1 +: 1 +: 1 +: 1 +: 1 +: 1 +:Nl
...
val succs :Lst[Int=>Int] = repeat( (x :Int) => x + 1, 3 )  // >>  (x :Int) => x + 1  +: (x :Int) => x + 1  +: ...

Ok, what about taking an element and a counter and recursively calling repeat by decrementing that counter each time (until we want to repeat that element zero times, which therefor results into an empty list)? Since repeat results into a list, we simply prepend the given value in each recursion step to that produced list:

def repeat[A]( a :A , times :Int ) :Lst[A] = if( times == 0 ) Nl else a +: repeat( a , times - 1 )

interval

Ok, this is a very limited function, since it only creates lists of integer values. In this case, we simply wanna create a list which consists of all integer values from a given starting point upto a given end value (which we  presume to be greater as the starting point). In addition to that, we might also wanna give an increment which determines the spread between two neighbor values within that list. Since it’s only a simple helper function (as we’re going to see), let’s just give an implementation for it directly:

def interval( start :Int, end :Int, step :Int ) :Lst[Int] = ( start, end ) match {
    case( s, e ) if s > e  => Nl
    case( s, e )  => s +: interval( s + step, e, step )
}

Of course we could’ve come up with a more general version which might operate on arbitrary types allowing for enumerating its elements (and therefore providing a sensible order for its values, too).

append

So far, we’re only prepending a new value to a given list to become the head of a new list. But what if we need to append a new value to be the new last element of a given list. Of course, we also wanna do so in a non-destructive way like we did within the last episode when we inserted a new element at an arbitrary position of a given list. Hey, wait a minute! What was that? If appending is like inserting, only limited to a fixed position (namely the last position within a list), why not simply delegating to  function insertAt? Luckily we’re able to determine the last position of any given list, simply by using function length, which we’ve also introdiced in the last episode:

def append[A]( a :A, lst :Lst[A] ) : Lst[A] = insertAt( length( lst ), a, lst )

Just keep in mind that appending a value to a given list is really expensive (at least for our list-like data structure), since we need to reassemble the whole list while inserting the new value at the last position!

concat

Now that we know how to add a single value to a given list (no matter at which side), what about concatenating two lists? In this case we wanna receive a new list which just consists of all elements of both lists.

val ints :Lst[Int] = 1 +: 2 +: 3 +: Nl
val moreInts :Lst[Int] = 6 +: 7 +: 8 +: 9 +: Nl
val strings :Lst[String] = "a" +: "b" +: "c" +: Nl
...
val allInts :Lst[Int] = concat( ints, moreInts )  // >>  1 +: 2 +: 3 +: 6 +: 7 +: 8 +: 9 +: Nl
...
val mixed :Lst[Any] = concat( ints, strings )  // >>  1 +: 2 +: 3 +: "a" +: "b" +: "c" +: Nl

In this case, we simply prepend the elements of the first list recursively to the second one (which’s then already concatenated with the rest of the first list):

def concat[A,B>:A]( lxs :Lst[A], lys :Lst[B] ) :Lst[B] = ( lxs, lys ) match {
    case ( Nl, ys )  => ys
    case ( x +: xs, ys )  => x +: concat( xs, ys )
}

flatten

We just saw how to concatenate two lists resulting into a single list. What about having more than two lists? Say we have a list of lists which elements should all be collected within a single list.You might see it as flattening the list of lists: the inner lists get dissolved within the outer one. Of course are the original lists not deconstructed! We wanna construct a new list, leaving the outer list as well as the inner lists untouched.

You might see the whole process as concatenating two lists repeatedly until all (inner) lists are concatenated:

def flatten[A]( xxs :Lst[Lst[A]] ) :Lst[A] = xxs match {
    case Nl => Nl
    case x +: xs => concat( x, flatten( xs ) )
}

Sublists

As the last section within this episode, we’ll take a closer look at some functions which will deliver a certain sublist for a given list.

take

Imagine we need a function which just returns the first n elements of a given list. So clearly we need to give a number how many elements we wanna take from a given list and the list from which the elements are taken from:

val ints :Lst[Int] = 1 +: 2 +: 3 +: +: 4 +: 5 +: Nl
...
val firstThree :Lst[Int] = take( 3, ints )  // >> 1 +: 2 +: 3 +: Nl
...
val moreThanExists :Lst[Int] = take( 10, ints )  // >> 1 +: 2 +: 3 +: +: 4 +: 5 +: Nl
...
val nope = take( 0, ints )  // => Nl

Let’s try to split the problem into some simpler sub problems, once more: first, if we want to take some elements from the empty list, we surely can’t deliver anything else as the empty list itself. second, if we want to take zero elements from any given list, we again receive only the empty list. Finally, if we want an arbitrary number from a non-empty list, we just deliver the first element of the list and take a a decremented number of elements from the rest of the list:

def take[A]( count :Int, lst :Lst[A] ) :Lst[A] = ( count, lst ) match {
    case ( _ , Nl )  => Nl
    case ( 0 , _ )  => Nl
    case ( i, a +: as )  => a +: take( i-1, as )
}

drop

This one is just the opposite of function take. this time we don’t wanna take the first n elements but drop them, resulting into a list with all elements but the first n ones.

The cases here are almost the same: droping from an empty list results into an empty list. Second, dropping zero elements from a given list just result into that list. And finally, dropping an arbitrary number of elements from a given list is just omitting the head of the list and dropping a decremented number from the rest of the list:

def drop[A]( count :Int, lst :Lst[A] ) :Lst[A] = ( count, lst ) match {
    case ( _ , Nl )  => Nl
    case ( 0 , as )  => as
    case ( i, a +: as )  => drop( i-1, as )
}

splitAt

Here, we wanna split a given list at a certain position, resulting into a pair of two sublists. The first sublist will contain all elements from head until the element before the position to split. The second one will contain all elements from the position to split upto the last element:

val ints :Lst[Int] = 1 +: 2 +: 3 +: 4 +: 5 +: Nl
...
val (firstTwo,lastThree) = splitAt( 2, ints )  // >> ( 1 +: 2 +: Nl  ,  3 +: 4 +: 5 +: Nl )

You may wanna think back to those two introduced functions take and drop: Splitting a list can be seen as taking some elements for the first sublist and droping them for the second sublist. So here we go:

def splitAt[A]( pos :Int, lst :Lst[A] ) : (Lst[A],Lst[A]) = ( take( pos, lst ), drop( pos, lst ) )

Of course you may say, that we’ll traversionf the original list twice (well, in the worst case for splitting near the end of a list). First for taking the first n elements and then again for dropping them. Of course we could come up with another implementation, which just traverses the list only once:

def splitAt[A]( pos :Int, lst :Lst[A] ) : (Lst[A],Lst[A]) = ( pos, lst) match {
    case( _ , Nl )      => (Nl,Nl)
    case( 0, as )      => ( Nl, as )
    case( i, a +: as ) => val (p1,p2) = splitAt( i-1, as ); ( a +: p1, p2 )
}

See that thirs case expression? It’s a bit ugly since we need to put prepending the given head after the recursive split for the rest of the list (otherwise you would end up with a reversed list)

Summary

We could continue with that quiz for hours and hours. There are far more useful list functions we haven’t discovered yet! Hopefully you did some ruminations and experimentation for yourself for getting an even better understanding and feeling on how to operate on lists in a more functional style.

In this episode we just saw some of those commonly used list functions and gave a rather straightforward implementation. We did all this by only using pattern matching, recursion and delegation to some other known functions.

We’re by far not at the end. As promised within the last episode, we’ll encounter some very powerful functions which we’ll levrage to build most of the functions we discovered today in a more concise (but also more abstract) way!  But before we’ll get there, we need to extend our functional tool box. We’ll see how to kind of derive new functions out of some already given functions by using currying. Don’t be afraid! It’s not about indian food but receiving another mighty tool which allows us to become an even more powerful apprentice of functional programming in Scala. So hope to see you there …