Find Nth element from the end in Scala using recursive tail

Question

I am new to Scala and I am trying to understand this program below. Particularly I don't understand the line

case _ :: tail        =>
            lastNthR(count - 1,
              if (count > 0) resultList else resultList.tail,
              tail)

Lets say I have to find last 2nd element that is 6, the code becomes lastNthR(2-1=1?, as 1>0 it should get resultList am I right here? else resultlist.tail, tail?

I don't get it. Can someone please explain it to me. I am scratching my head for a long time. Here is full code:

  def lastNthRecursive[A](n: Int, ls: List[A]): A = {
      def lastNthR(count: Int, resultList: List[A], curList: List[A]): A =
        curList match {
          case Nil if count > 0 => throw new NoSuchElementException
          case Nil              => resultList.head
          case _ :: tail        =>
            lastNthR(count - 1,
              if (count > 0) resultList else resultList.tail,
              tail)
        }

      if (n <= 0) throw new IllegalArgumentException
      else lastNthR(n, ls, ls)
  }

  println(lastNthRecursive(2,List(4,5,6,7)))

Answer 1

Very interesting example!

It uses a list and a copy of itself to know when to stop walking trough the elements of the list. This is what happens when running your example, on each call to lastNthR:

count = 2
resultList = List(4, 5, 6, 7)
curList = List(4, 5, 6, 7)

count = 1
resultList = List(4, 5, 6, 7)
curList = List(5, 6, 7)

count = 0
resultList = List(4, 5, 6, 7)
curList = List(6, 7)

count = -1
resultList = List(5, 6, 7)
curList = List(7)

count = -2
resultList = List(6, 7)
curList = List()

As you can see, on each step, it subtracts one to count. While count is greater than zero, it won't affect resultList, which as its name states, is the list that we will use to get the final result. However, on each step, the first element from curList is removed. The function executes until curList runs out of elements. However, we have started removing elements from resultList just after we have removed the first N (in this example, 2) elements from curList. This way, we will run out of elements from curList while we still have the last 2 elements from resultList.

In a more graphic way, the intended effect is as if we moved the resultList 2 places to the right:

count: 2
resultList =       4, 5, 6, 7
curList    = 4, 5, 6, 7

Then, we start removing elements, one by one, until we run out of elements from curList, which is what the block that you pointed out does:

count: 1
resultList =    4, 5, 6, 7
curList    = 5, 6, 7

count: 0
resultList = 4, 5, 6, 7
curList    = 6, 7

When count is zero or lower, we start removing items from resultList too:

count: -1
resultList = 5, 6, 7
curList    = 7

count: -2
resultList = 6, 7
curList    =

This way, when we run out of items from curList, we still have the 2 elements left from resultList, so we only need to get the first of them. This is done with the code:

curList match {
  // ...
  case Nil => resultList.head
  // ...
}

Answer 2

Way to get nth element(o indexed) from a List:

def get[A] (n: Int, list: List[A]): A = {
   @scala.annotation.tailrec
   def go(acc: Int, li: List[A]): A = {
     if(acc == n) List.head(li)
     else go(acc+1, tail(li))
   }

  if(n > List.length(list) - 1) throw new IllegalArgumentException("indexincompatible with List length");
  go(0, list)
}

To get nth element from last, call it with index calculated from start.

Answer 3

I'm not sure if this is a typo in the title or did you miss that but this method (as the name suggests) finds the N-th element from the end (or in a reverse order) starting with 1 as the very last element (which is an uncommon notation in programming, typically indices start with 0 instead).

I think you messed up with formatting. Let's re-write this code into an equivalent form:

if(count > 0) {
 lastNthR(count - 1,
          resultList,
          tail)
}
else {
 lastNthR(count - 1,
          resultList.tail,
          tail)
}

In other words in your code the if(count > 0) statement affects calculation of the second parameter in the lastNthR call while the first parameter (count - 1) and the third parameter (tail) are "fixed", this is what comma (,) at the end of the line with that if means.

Logically this code works in two stages:

1. At the first stage when if(count > 0) holds true, we reduce the curList and count by 1 each until count becomes 0.
2. At the second stage when if(count > 0) is false, we reduce curList and resultList by 1 each until curList is empty.

In other words the algorithm says that find the n-th element from the end is the same as finding length(list) - n-th element from the start. The first stage finds this length(list) - n value (in term of a list of that length) and then the second stage does a search from the start.

You can re-write that code separating the stages explicitly in two different methods:

def lastNthRecursive[A](n: Int, ls: List[A]): A = {
  // stage 1
  // note, there is actually a very similar a standard method on a List 
  // but it doesn't fail in case of an overshot (n > length(list))
  def dropN(count: Int, curList: List[A]): List[A] = curList match {
    case _ if (count == 0) => curList // important to be above the Nil case
    case Nil => throw new IndexOutOfBoundsException(s"$n is more than the list length")
    case _ :: tail => dropN(count - 1, tail)
  }

  // stage 2      
  def dropAll(longList:List[A], shortList:List[A]):List[A] = shortList match {
      case Nil => longList
      case _  => dropAll(longList.tail, shortList.tail)    
  }

  if (n < 0) throw new IndexOutOfBoundsException(s"$n is less than 0")
  else {
    val shortenedList = dropN(n, ls)
    val resultList = dropAll(ls, shortenedList)
    resultList.head
  } 
}

P.S. I don't like the fact that exceptions are inconsistent IllegalArgumentException vs NoSuchElementException and provide no textual description at all. Also there is IMHO a better exception for this case - IndexOutOfBoundsException