CODEWITHSUNDEEP
listscalarecursionpattern-matching
user3789100
user3789100

Reputation: 37

Finding the nth element of a list in scala recursively with pattern matching

I have a problem here from 99 scala problems (http://aperiodic.net/phil/scala/s-99/p03.scala) that I am trying to figure out how it works. I'm fairly new to Scala. I was able to complete this challenge with a similar solution using pattern matching and recursion however mine did not consider the list in the matching. My code is below:

def nth[A](k: Int, l: List[A]): A = k match {
  case 0 => l.head
  case _ => nth(k-1, l.drop(1))
}

and this seemed to do the job. However, there's no error checking if the list is Nil. The solution 99 scala problems provides is:

def nthRecursive[A](n: Int, ls: List[A]): A = (n, ls) match {
  case (0, h :: _   ) => h
  case (n, _ :: tail) => nthRecursive(n - 1, tail)
  case (_, Nil      ) => throw new NoSuchElementException
}

What I dont understand is 

case(0, h:: _ )

and 

case(n, _ :: tail)

What is the author doing here? I understand :: appends whatever is on the left to the beginning of whats on the right but I'm not sure exactly what is happening. Can anyone enlighten me?

Thank you!

Upvotes: 1

Views: 1411

Answers (2)

Xiaohe Dong
Xiaohe Dong

Reputation: 5023

Basically, it is pattern matching expression. That is why Scala pattern matching is so powerful, so we can drop some heavy visitor pattern like Java (out of this topic).

A simple example:

case class User(name: String, age: Int)

def doStuff(user: User) = user match {
  case User(_, age) if age > 100 => println("Impossible!")
  case User(name, _) => println("hello " + name)
}

In this case, _ :: tail just means I want to get the reference of the tail.

Upvotes: 1

some some
some some

Reputation: 548

The :: operator is used to extract the head and the rest of the list (the tail).

Here:

case(0, h :: _ )

only the head is relevant so the tail doesn't get a reference.

And Here:

case(n, _ :: tail)

only the tail is relevant so the head doesn't get a reference.

You can also use:

case(0, head :: tail)
case(n, head :: tail)

(i.e. giving both parts a reference) and get exactly the same result.

Upvotes: 2

Related Questions