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))

1 answer

  • answered 2018-11-08 08:29 Dominic Egger

    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