Find 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 anyone comment on what this does row by row?

Is [A] generic, as in C #, will we do?

h does not seem to be defined?

I think the main part of the algorithm is a recursive call:

 case _ :: tail => penultimateRecursive(tail) 

There does not seem to be a check for 2 items in the list, and then the first item to get the second last, embarrassed!

Answer 1

The keys to understanding pattern matching are to understand that x :: y will only match a list with one x element, followed by the rest of the list y (which may be just Nil , or there may be many elements), and that _ means "here should to be something, but we will not name it. " (And that matches occur in order and end with Nil .)

You are correct that [A] is a generic type.

So the first line:

 case h :: _ :: Nil => h 

says that if our list looks (conceptually) Node(h) -> Node(whatever) -> Nil , then we return h . This is exactly a two-item list with the first item selected. Note that Nil does not match an arbitrary tail of the list; it matches only the end of the Nil list item. This is because of the rule that Scala uses to distinguish between two: lowercase variables are treated as wildcards, which must have the corresponding value filled in, while uppercase variables are treated as constants for matching. (If you must match the name in lowercase, you can if you surround it with reverse windows.)

Ok, now suppose this is not a two-item list. Then, if it is not empty, it will match

 case _ :: tail => penultimateRecursive(tail) 

therefore, if we do not have a two-element list, we discard the first element and try again. Finally, if we somehow did not finish the two-element list, we move on to

 case _ => throw new NoSuchElementException 

and you're done. (This could also be case Nil , in fact, as this is the only possibility that does not match the other two elements.)

Answer 2

A is a type variable, meaning that a function is defined in the general case for any type of A

h bound by pattern matching: the first case states, if there are exactly two elements, then call the first h and return it.

There does not seem to be checking for 2 items in a list

There is: h :: _ :: Nil means "an element h followed by any element followed by more elements." Nil not an element, this is the end of the list.

and then take the 1st element to get the second last

Taking the first of a two-element list means using the penultimate one. If there are fewer or more elements in the list than two, two other cases apply.

Answer 3

larsmans and Rex reviewed your questions, but see chapter 9 for more details on '::' http://www.scala-lang.org/docu/files/ScalaByExample.pdf

Answer 4

The first line means that any element of the list h will be returned if h is followed by another and a pointer Nil (at the end of the list). The actual element following h is not important, so you use _ to indicate that there is an element, but you do not care about its value.

If the first case does not match, the second case will cause recursion if there is a head element and a tail of at least one element in the list.

Finally, you exit the lists consisting of only one element. Once again, you do not need to care about the actual value of the value of the elements.