# Scala recursion lists

How does this recursive function operate in scala? Is there an easy way to understand how it operates? Similar functions will be assessed in my upcoming exam, would appreciate a helpful and informative explanation of how the recursion operates.

``````def process(op : Int => Int, list : List[Int]) : List[Int] =
list match {
case Nil => Nil
case hd :: tl => op(hd) :: process(op, tl)
}
``````

What would the following result in and how?

``````process((x : Int) => x * 3, List(3, 4, 5))
``````

• answered 2018-11-08 08:29

so let's break this down a bit. what you're looking at here is really just `map` on `List` but with a bit different notation.

First let's look at a possible definition of list (I am using covariance here like the standard implementation but you can ignore it):

``````sealed trait List[+A]
final case class Cons[A](head:A, tail:List[A]) extends List[A]
final case object Nil extends List[Nothing]
``````

because the trait is sealed and the case classes/objects are final that means that a given instance of `List[A]` can only ever be a `Cons[A]` or a `Nil` which allows us to do safe pattern matching.

Now I'm going to write down a possible implementation of `map`. Note how it looks similar to your `process`.

``````def map[A, B](op: A => B, list:List[A]):List[B] = list match {
case Cons(head, tail) => Cons(op(head), map(op, tail))
case Nil => Nil
}
``````

Whenever we patternmatch we should cover all possible cases for the thing we match over. because we sealed our `List` we know it can only be one of 2 things. Now if it's `Nil` that is our recursion base case and we return `Nil` again which is really just an empty list. If we have a `Cons` (in the std-lib List that'd be `::`) we apply our transformation function on the `head` of the list and map over the remaining `tail`. because our `tail` is always one element shorter than the `list` parameter we match over, this will eventually get us to the `Nil` case.

Really the only difference between `map` and your `process` is that yours is specialized to the `Int` type.

I hope this helps

Edit: No I didn't run this code and there would probably be naming collision issues if you'd try to do it :D