P04 – Find the number of elements of a list
Posted by rbpasker on April 16, 2009
This one should be pretty easy, since we already know from the last problem how to get to the nth element.
scala> def length[T](l: List[T]) : Int = l match {
| case Nil => 0
| case e::Nil => 1
| case _::t => 1 + length(t)
| }
length: [T](List[T])Int
scala> length(List())
res7: Int = 0
scala> length(List(1))
res8: Int = 1
scala> length(List(1,2,3,4,5,6,7,8))
res10: Int = 8
There are two functional answers to this problem.
The first is a “simple recursive” solution:
def length[T](l: List[T]): Int = l match {
case Nil => 0
case _ :: tail => 1 + length(tail)
}
I see now that I didn’t need the middle case case e::Nil => 1, because the last case would have properly copmuted length(Nil) as 0.
The second answer, however, is more interesting and also somewhat disappointing. It says
Unfortunately, the JVM doesn’t do tail-call elimination in the general case. Scala *will* do it if the method is either final or is a local function.
Which means that all the work I’ve been doing to get out of the imperative (iterative) style, as per P01′s admonition about the “functional approach” which uses recursion, was a nice exercise, but frankly nearly futile in Scala because these functions, given a large enough List, will blow the stack. Luckily their answer to P04 links to a blog with a way to get tail recursion in Scala, and frankly, its not pretty. It involves some special maneuvers which you can read about there.
