Cookie Consent by Privacy Policies Generator Vegapit
Functional Programming exercises in Scala 3: Functions on Lists
Last updated: 2022-09-28T08:40:55

These 22 exercises should be useful to anyone looking to practice in Scala 3 and/or Functional Programming (FP). By and large, they are a curated selection of the “Working with Lists” problems on the OCaml website. The problems are vaguely sorted based on their overall complexity. All solutions provided here are my own so feel free to send me yours if they are any better.

Rules and Guidelines

To maximise the educational value of these exercises, I have looked for solutions adhering to the following principles:

  • No mutable variables
  • Using pattern matching, function compounding (especially recursion) and higher-order functions
  • Limiting my usage of List methods in the Scala standard library (less is more)
  • Making my recursive functions tail-recursive whenever possible

The Scala standard library is quite extensive. Some solutions could have been turned into direct calls to some of the specialised functions within it, but scanning the API reference to find the most relevant function to use is too much effort directed away from the task of learning to think in the FP paradigm. Therefore, I have stuck with the most fundamental methods of the List class, namely:

List.fill(5)(0) == List(0,0,0,0,0) // Constructs a list by repeating a unique value
List(1,2,3,4,5).sum == 15 // Sums all its elements
List(1,2,3,4,5).map{elt => 2*elt} == List(2,4,6,8,10) // Applies a function to every element
List(1,2,3,4,5).filter{elt => elt % 2 == 0} == List(2,4) // Filter elements based on predicate
List(1,2,3).flatMap{elt => elt::0::Nil} == List(1,0,2,0,3,0) // Applies a function to every elements and flattens the resulting list
List(1,2,3,4,5).take(2) == List(1,2) // Takes the first k elements only
List(1,2,3,4,5).drop(2) == List(3,4,5) // Takes all but first k elements

A couple of specialised methods are used in the solutions of the complex problems but these will be mentioned in the Hint section of the relevant exercise.

List fundamentals

Partitions are a very important part of thinking in the FP paradigm while processing List instances in Scala. Two of them are readily available to us: (head,tail) and (init,last).

The head(resp. last) of a List is simply its first (resp. last) element, and its tail(resp. init) is the List containing all its elements but the first (resp. last). In the code, these are expressed like this:

val my_list = List(1,2,3,4,5)
my_list == my_list.head :: my_list.tail
my_list == my_list.init :+ my_list.last

The head::tail partition is the most crucial one as it is used to express the general case in pattern matching for a List instance.

Preliminary Imports

Importing all the packages we will need from the onset is a way to clarify our code down the line:

import scala.annotation.tailrec
import scala.util.chaining.*
import scala.util.Random

given Random = Random(0)

enum RLE:
    case One(elt: Any)
    case Many(elt: Tuple2[Int, Any])

The annotation tailrec which should be applied to any tail recursive function triggers performance optimisation during the compilation process. Using it systematically is not crucially necessary but it is a healthy coding habit.

The chaining package includes the pipe method which can be applied to any function call and act as the pipe operator of the language. It is syntactic sugar making the code more concise and clearer, but here again you can get away with not using it.

We will need the Random class for generating random sequences in some of the solutions. You can see that one is initialised with seed 0 as a given instance. This will allow us to use it as contextual parameter in several functions.

The RLE enum which stands for Run-Length Encoding is used in a couple of exercises. It will allow us to learn how to process and more precisely how to pattern match enum types.

For your benefit, it is probably best to give yourself some time to design your own implementation. The solutions are really there if you are stuck or as a reference to compare to yours.

OK, I think we are all set, time to start. Good practicing!

1. Write a function last that returns an Option containing the last element of the List if it exists

last( List("a","b","c","d") ) == Some("d")
last( Nil ) == None
Solution

First, we note that the empty List does not have a last element. Then, for a List l containing more than one element, we note that last(l) == last(l.tail). We can then use pattern matching on List to recursively call the function up until we get the trivial case of a List with a single element.

@tailrec
def last(l: List[Any]) : Option[Any] = l match
    case Nil => None
    case x::Nil => Some(x)
    case h::t => last(t)

2. Write a function nth that returns an Option containing the element of the List at index i if it exists

nth( List("a","b","c","d","e"), 2 ) == Some("c")
nth( List("a"), 2 ) == None
nth( Nil, 0 ) == None
Solution

For a List l containing at least one element, we know that nth(l,i) == nth(l.tail,i-1). Once again, we can use pattern matching on List to recursively call the function up until we get a trivial case i.e. an empty List or a call with i == 0 in which case we return Some(l.head).

@tailrec
def nth(l: List[Any], i: Int) : Option[Any] = l match
    case Nil => None
    case h::t => if i == 0 then Some(h) else nth(t, i-1)

3. Write a function length that returns the length of a list

length( List("a","b","c") ) == 3
length( Nil ) == 0
Solution

For a List l containing at least one element, we know that length(l) == length(l.tail) + 1. We can then use pattern matching on List to recursively call the function up until we get an empty List.

def length(l: List[Any]) : Int = l match 
    case Nil => 0
    case h::t => length( t ) + 1

This function works but it is not tail recursive since we are making an extra operation ( plus one ) on the recursive call. We can define a tail recursive inner function with an accumulator and a remainder, and call this function instead.

def length(l: List[Any]) : Int =
    @tailrec
    def sub(acc: Int, rem: List[Any]) : Int = rem match 
        case Nil => acc
        case h::t => sub( acc + 1, t )
    sub(0, l)

4. Write a function reverse that returns the original List with its elements in reverse order

reverse( List("a","b","c") ) == List("c","b","a")
reverse( Nil ) == Nil
Solution

For a List l containing at least one element, we know that reverse(l) == reverse(l.tail) :+ l.head. We can then use pattern matching on List to recursively call the function up until we get an empty List. Simularly to the length case, the basic version would not be tail recursive hence the need for an inner function. Note that in the inner function, the head is prepended to the accumulator.

def reverse(l: List[Any]) : List[Any] =
    @tailrec
    def sub(acc: List[Any], rem: List[Any]) : List[Any] = rem match
        case Nil => acc
        case h::t => sub( h::acc, t )
    sub(Nil, l)

5. Write a function flatten that transforms any nested List structure into a flat List

flatten( List("a", List("b","c"), List("d", "e")) ) == List("a", "b", "c", "d", "e")
flatten( List("a", List("b","c",List("d", "e"))) ) == List("a", "b", "c", "d", "e")
Solution

In the most general case for a List l, we know that flatten(l) == flatten(l.head) ++ flatten(l.tail). If the head is not a List, we would prepend it instead of concatenating it. The function is clearly not tail recursive but I could not find an inner function that would be so since we want to flatten lists containing sublists which could themselves contain sublists, etc.

def flatten(l: List[Any]) : List[Any] = l match
    case Nil => Nil
    case h::t => h match
        case h: List[Any] => flatten(h) ++ flatten(t)
        case _ => h :: flatten(t)

6. Write a function compress that eliminates consecutive duplicates in the List

compress( List("a","a","a","b","c","c","d","e","e","e") ) == List("a", "b", "c", "d", "e")
Solution

Since we need to compare the current head with the previous head encountered, using an inner function with an accumulator is the way to go. Whether the last element of the accumulator equals the head element or not defines what needs to be done with the head element in relation to the accumulator. To do this comparison, we can use the function last we have defined previously and pattern match its Option output.

def compress(l: List[Any]) : List[Any] =
    @tailrec
    def sub(acc: List[Any], rem: List[Any]) : List[Any] = rem match
        case Nil => acc
        case h::t => last(acc) match
            case Some(elt) => if elt == h then sub(acc,t) else sub(acc :+ h, t)
            case None => sub( h::Nil, t )
    sub(Nil, l)

7. Write a function pack that groups consecutive duplicates into sub-Lists

pack( List("a","a","a","b","c","c","d","e","e","e") ) == List(List("a","a","a"), List("b"), List("c","c"), List("d"), List("e","e","e"))
Solution

The logic used in this function is very close to the one used in the compress function. The only difference is in the processing of the head element as we are handling sublists.

def pack(l: List[Any]) : List[List[Any]] =
    @tailrec
    def sub(acc: List[List[Any]], rem: List[Any]) : List[List[Any]] = rem match
        case Nil => acc
        case h::t => last(acc) match
            case None => sub( List(h)::Nil , t )
            case Some(lst: List[Any]) => 
                if lst.head == h then sub( acc.init :+ (lst :+ h), t ) 
                else sub( acc :+ List(h), t )
    sub( Nil, l )

8. Write a function encodeTuple that performs run-length encoding with Tuple2 on the List

encodeTuple( List("a","a","a","b","c","c","d","e","e","e") ) == List((3, "a"), (1, "b"), (2, "c"), (1, "d"), (3, "e"))
Solution

This function can be implemented by applying a function on every element of the List output of the function pack we implemented previously. We can use the map method in the List class for this purpose.

def encodeTuple(l: List[Any]) : List[Tuple2[Int,Any]] = 
    pack(l).map{elt => (length(elt), elt.head)}

9. Write a function encode that performs run-length encoding with RLE on the List

encode( List("a","a","a","b","c","c","d","e","e","e") ) == List(RLE.Many((3, "a")), RLE.One("b"), RLE.Many((2, "c")), RLE.One("d"), RLE.Many((3, "e")))
Solution

Once again, we can use the map method in the List class for this purpose, but this time on the output of the encodeTuple function we have defined. We will be using the RLE enum to store the data into.

def encode(l: List[Any]) : List[RLE] =
    encodeTuple(l).map{elt => if elt(0) == 1 then RLE.One(elt(1)) else RLE.Many(elt) }

10. Write a function decode that contructs a List based on its run-length encoding.

decode( List(RLE.Many((3, "a")), RLE.One("b"), RLE.Many((2, "c")), RLE.One("d"), RLE.Many((3, "e"))) ) == List("a","a","a","b","c","c","d","e","e","e")
Solution

In this case also, it is a simple transformation of every element in the input List. We can use map to generate a list of sublists and then flatten the output. flatMap is a List method than performs these successive operations by default. We also use the fill method which builds a List of specified length containing copies of a unique element.

def decode(l: List[RLE]) : List[Any] =
    l.flatMap{_ match
        case RLE.One(v) => v::Nil
        case RLE.Many((k,v)) => List.fill(k)(v)
    }

11. Write a function replicate that replicates each element of a List successively k number of times

replicate( List("a", "b", "c", "d"), 3 ) == List("a","a","a","b","b","b","c","c","c","d","d","d")
Solution

This is a straightforward composition of the standard library methods fill and flatMap we have introduced previously.

def replicate(l: List[Any], k: Int) : List[Any] =
    l.flatMap{List.fill(k)(_)}

12. Write a function split that cuts a list into two parts where the first is of length k

split( List("a", "b", "c", "d", "e", "f", "g", "h", "i", "j"), 3 ) == ( List("a", "b", "c"), List("d", "e", "f", "g", "h", "i", "j") )
split( List("a", "b", "c", "d"), 5 ) == ( List("a", "b", "c", "d"), Nil )
Solution

We should use two useful List methods to implement this function: take(k) which returns a List containg the first k elements of the List, and drop(k) which returns all but the first k elements of the List.

def split(l: List[Any], k: Int) : Tuple2[List[Any], List[Any]] =
    (l.take(k), l.drop(k))

13. Write a function rotate that rotates a list k places to the left

rotate( List("a", "b", "c", "d", "e", "f", "g", "h"), 3 ) == List("d", "e", "f", "g", "h", "a", "b", "c")
Solution

This is a straightforward usage of the output of the split function defined previously. Note the use of the pipe method from the chaining imported package which facilitates function compounding in Scala 3.

def rotate(l: List[Any], k: Int) : List[Any] =
    split(l, k).pipe{(fst,snd) => snd ++ fst}

14. Write a function removeAt that returns a List with the element at index k removed

removeAt( List("a", "b", "c", "d"), 1 ) == List("a", "c", "d")
Solution

Again, this is a straightforward usage of the output of the split function defined previously.

def removeAt(l: List[Any], k: Int) : List[Any] =
    split(l, k).pipe{(fst, snd) => fst ++ snd.tail}

15. Write a function insertAt that returns a List with the element x added at index k

insertAt( List("a", "b", "c", "d"), 1 , "alfa") == List("a", "alfa", "b", "c", "d")
Solution

Once again, this is a direct usage of the output of the split function defined previously.

def insertAt(l: List[Any], k: Int, x: Any) : List[Any] =
    split(l, k).pipe{(fst, snd) => fst ++ (x :: snd)}

16. Write a function range that creates a List containing all integers from i to j (increasing or decreasing order)

range(4, 9) == List(4,5,6,7,8,9)
range(9, 4) == List(9,8,7,6,5,4)
Solution

We can define an inner function with an accumulator and an index ix. Depending on how the index compares to the target number j, we set the accumulator and the next index passed to the recursive call accordingly.

def range(i: Int, j: Int) : List[Int] =
    @tailrec
    def sub(acc: List[Int], ix: Int) : List[Int] = 
        if ix > j then sub( acc :+ ix, ix - 1)
        else if ix < j then sub( acc :+ ix, ix + 1)
        else acc :+ ix
    sub(Nil, i)

17. Write a function permutation that returns a random permutation of the List

permutation( List("a", "b", "c", "d", "e", "f") ) == List("e", "b", "c", "f", "d", "a")
Hint - The shuffle method of the Random class randomly sorts the elements of a List
Solution

We can use as contextual parameter the instance of the Random class defined with the given keyword previously. Then it is a straighforward call to the shuffle method.

def permutation(l: List[Any])(using rng : Random) : List[Any] =
    rng.shuffle(l)

18. Write a function randSelect that randomly extracts k elements from the List

randSelect(List("a", "b", "c", "d", "e", "f", "g", "h"), 3) == List("b", "a", "g")
Solution

We can simply take the first k elements of the random permutation returned by the function previously defined.

def randSelect(l: List[Any], k: Int)(using Random) : List[Any] =
    permutation(l).take(k)

19. Write a function lottoSelect that randomly draws k different numbers between 1 and N

lottoSelect( 6, 49 ) == List(2, 10, 11, 18, 33, 12)
Solution

Straightforward compounding of the functions range and randSelect defined previously.

def lottoSelect(k: Int, N: Int)(using Random) : List[Any] =
    range(1,N).pipe{randSelect(_, k)}

20. Write a function extract that generates all combinations of k distinct objects chosen from the List

extract( List("a", "b", "c", "d", "e", "f"), 3 ).length == 20 // C(6,3) = (6*5*4)/(3*2) = 20
Hint - For each element of the List, you can strictly divide the final combinations into 2 groups: The ones that contain it and the ones that don’t.
Solution

To generate all combinations of k elements that contain the head of the List l, we can call extract(l.tail, k-1) and append the head to all the sublists returned. To generate all combinations of k elements that do not contain the head of the List l, we can call extract(l.tail, k).

def extract(l: List[Any], k: Int) : List[List[Any]] = 
    if k == 0 then Nil::Nil
    else l match
        case Nil => Nil
        case h::t => extract(t, k-1).map{h :: _} ++ extract(t, k) // {With h} ++ {Without h}

21. Write a function group that generates all groups of the elements of the List into disjoint subsets of given sizes

group( List("a", "b", "c", "d", "e", "f"), List(3,2,1) ).length == 60 // C(6,3) * C(3,2) * C(1,1) = 20 * 3 * 1 = 60
group( List("a", "b", "c", "d"), List(2,1) ).length == 12 // C(4,2) * C(2,1) = 6 * 2 = 12
Hint - Each set of subsets is build from a group of sizes.sum distinct objects chosen from the List. The method diff allows you to do the difference (in the algebraic sense) between two lists
Solution

We first generate all groups of sizes.sum distinct objects from the List using the extract function previously defined. Iterating through sizes, for each set of groups picked so far, we extract all groups of the size of interest that can be generated from the elements than have not been picked so far.

def group(l: List[Any], sizes: List[Int]) : List[List[List[Any]]] =
    @tailrec
    def sub(acc: List[List[List[Any]]], rem: List[Int], omega: List[Any]) : List[List[List[Any]]] = rem match
        case Nil => acc
        case h::t => 
            val nxt = acc match
                case Nil => extract(omega, h).map{_::Nil}
                case _ => acc.flatMap{prt => extract( flatten(prt).pipe(g => omega.diff(g)), h ).map{prt :+ _}}
            sub( nxt, t, omega )
    extract(l, sizes.sum).flatMap{sub(Nil, sizes, _)}

22. Write a function lenghSort that sorts sublists based on their length

lengthSort( List( List("a", "b", "c"), List("d","e"), List("f","g","h"), List("i","j","k","l") ) ) == List( List("d","e"), List("a", "b", "c"), List("f","g","h"), List("i","j","k","l") )
Hint - The method minBy can be used to calculate the minimum of the transformed elements a List
Solution

We identify the shortest sublist of the input List using the minBy method, append it to the accumulator and recursively call the function on the remaining elements. We need to use an inner function to make it tail recursive.

def lengthSort(l: List[List[Any]]) : List[List[Any]] =
    @tailrec
    def sub(acc: List[List[Any]], rem: List[List[Any]]) : List[List[Any]] = rem match
        case Nil => acc
        case _ =>
            val min_elt = rem.minBy{_.length}
            sub( acc :+ min_elt, rem.filter{_ != min_elt} )
    sub( Nil, l )

If you like this post, follow me on Twitter and get notified on the next posts