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 higherorder functions

Limiting my usage of
List
methods in the Scala standard library (less is more)  Making my recursive functions tailrecursive 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 RunLength 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.
@tailrecdef 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,i1)
. 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)
.
@tailrecdef 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, i1)
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 =
@tailrecdef 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] =
@tailrecdef 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] =
@tailrecdef 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 subLists
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]] =
@tailrecdef 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 runlength
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 runlength 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 runlength 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] =
.flatMap{_ match
lcase 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] =
.flatMap{List.fill(k)(_)} l
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] =
@tailrecdef 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  Theshuffle
method of theRandom
class randomly sorts the elements of aList
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] =
.shuffle(l) rng
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, k1)
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, k1).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 ofsizes.sum
distinct objects chosen from theList
. The methoddiff
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]]] =
@tailrecdef 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 methodminBy
can be used to calculate the minimum of the transformed elements aList
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]] =
@tailrecdef 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