Findig the 2nd last item in the list, please explain this solution

Question

// But pattern matching also makes it easy.
  def penultimateRecursive[A](ls: List[A]): A = ls match {
    case h :: _ :: Nil => h
    case _ :: tail     => penultimateRecursive(tail)
    case _             => throw new NoSuchElementException
  }

Can someone comment what this is doing line by line?

Is the [A] a generic like in c# we would do ?

h doesn't seem to be defined?

I think the major part of the algo is the recursive call:

case _ :: tail     => penultimateRecursive(tail)

There doesnt' seem to be a check for 2 items in the list, and then taking the 1st item to get the 2nd last, confused!

Answer 1

The keys to understanding the pattern match are to realize that x :: y will only match a list with a single item x followed by the rest of the list y (which could be just Nil, or could be many elements), and that _ means "there needs to be something here, but we won't bother naming it". (And that the matches occur in order, and that lists end with Nil.)

You're correct that [A] is a generic type.

So, the first line:

case h :: _ :: Nil => h

says, if our list looks like (conceptually) Node(h) -> Node(whatever) -> Nil, then we return h. This is exactly a two-element list with the first item selected. Note that Nil does not match any arbitrary tail of the list; it matches only the end-of-list item Nil. This is because of a rule that Scala uses to distinguish the two: lower case variables are treated as wildcards that are to have the appropriate value filled in, while upper case variables are treated as constants to match. (If you must match a lower-case name, you can if surround it by backticks.)

Okay, now suppose it's not a two-element list. Then if it's not empty, it will match

case _ :: tail => penultimateRecursive(tail)

so if we haven't got a two-element list, we throw away the first item and try again. Finally, if we somehow never ended up with a two-element list, we get to

case _ => throw new NoSuchElementException

and we're done. (This could also be case Nil, actually, since this is the only possibility that doesn't match the other two entries.)