This one is a little tricky because it doesn’t say what the function should do if there are less than two elements in the list. Which makes me wonder how P01 behaves with an empty list:
scala> last(List())
java.util.NoSuchElementException: head of empty list
Ok, last throws throws an NSEE when there’s fewer than one element, so P02 should also throw a NSEE when there are fewer than 2 elements.
Speaking of Exceptions, what happens to them in Scala? Well, NSEE derives from RuntimeException, which is unchecked, so it wouldn’t need to be thrown in a Java program. Searching for “scala checked exception” led me to this little gem on exception-handling in Scala and now I know I can use a Java-like throw clause.
From the previous problem, I know that Scala has pattern matching, which seems like a fancy way to do if/then/else. Here’s the code from P01′s answer:
def last[T](l: List[T]): T = l match {
case e :: Nil => e
case _ :: tail => last(tail)
case _ => throw new NoSuchElementException
}
There are three cases, and it looks like ” e::Nil” refers to an element followed by nothing, so “::” must be some sort of concatenation operator, and “=>” is the then part of the statement. So we have
- “e :: Nil ” – an element followed by Nil, which returns the element “e”
- “e :: tail” – an element followed by a non-Nill tail, which returns the (recursive) last element of the tail.
- “_” – which I guess is the default case.
In P02, we have 4 cases: an empty list, which should produce a NSEE; a 1-element List which should also produce an NSEE, a 2-element List which should produce the first element; and a 3 or more-element list, which should recurse on the tail:
scala> def penultimate[T](l: List[T]) :T = l match {
case e0::e1::Nil => e0
case e0::e1::tail => penultimate(e1::tail)
case _ => throw new NoSuchElementException
}
penultimate: [T](List[T])T
scala> penultimate(List())
java.util.NoSuchElementException
scala> penultimate(List(1))
java.util.NoSuchElementException
scala> penultimate(List(1,2))
res3: Int = 1
scala> penultimate(List(1,2,3,4,5,6))
res4: Int = 5
Sweet!
Theanswer to problem 2 which relies on pattern matching, however, is subtly different:
def penultimate[T](l: List[T]): T = l match {
case e :: _ :: Nil => e
case _ :: tail => penultimate(tail)
case _ => throw new NoSuchElementException
}
That “_” which I thought was the default case now crops up in the first two cases as well, and I’m not sure why.
This article on pattern matching says that “_” is a wildcard, which means it matches anything that wasn’t previously matched.
So there are two differences between their solution and mine. In the first case, they don’t use e0 and e1, but instead e and _, so e gets bound to the first element, _ matches and then throws away the tail, which is not needed for penultimate, and Nil matches an empty List. Interestingly, this pattern will only match a two-element list. Why? Because I misinterpreted ::, which doesn’t mean concatenated. It means HeadElement::TailList, so e::_::Nil should be interpreted as (e::(_::Nil)) (schematically, (head::(head::Nil))), which will only match a two-element list. Exercise for the reader: how do we know :: associates right-to-left and not left-to-right, like this: ((e::_)::Nil)?
Because :: means HeadElement::TailList, we immedately see the second difference:
_ :: tail => penultimate(tail) // their version
versus
e0::e1::tail => penultimate(e1::tail) // my version
Rather than trying to pattern match two head elements and a tail list, their version just recursively removes the head element, until it matches a 2-element list.
I have to say, even after two simple problems, I’ve learned a lot.
