Summing values in a List

Question

I'm trying to write a scala function which will recursively sum the values in a list. Here is what I have so far :

  def sum(xs: List[Int]): Int = {     val num = List(xs.head)        if(!xs.isEmpty) {       sum(xs.tail)     }     0    } 

I dont know how to sum the individual Int values as part of the function. I am considering defining a new function within the function sum and have using a local variable which sums values as List is beuing iterated upon. But this seems like an imperative approach. Is there an alternative method ?

Answer 1

Also you can avoid using recursion directly and use some basic abstractions instead:

val l = List(1, 3, 5, 11, -1, -3, -5) l.foldLeft(0)(_ + _) // same as l.foldLeft(0)((a,b) => a + b) 

foldLeft is as reduce() in python. Also there is foldRight which is also known as accumulate (e.g. in SICP).

Answer 2

With recursion I often find it worthwhile to think about how you'd describe the process in English, as that often translates to code without too much complication. So...

"How do I calculate the sum of a list of integers recursively?"

"Well, what's the sum of a list, 3 :: restOfList?

"What's restOfList?

"It could be anything, you don't know. But remember, we're being recursive - and don't you have a function to calculate the sum of a list?"

"Oh right! Well then the sum would be 3 + sum(restOfList).

"That's right. But now your only problem is that every sum is defined in terms of another call to sum(), so you'll never be able to get an actual value out. You'll need some sort of base case that everything will actually reach, and that you can provide a value for."

"Hmm, you're right." Thinks...

"Well, since your lists are getting shorter and shorter, what's the shortest possible list?"

"The empty list?"

"Right! And what's the sum of an empty list of ints?"

"Zero - I get it now. So putting it together, the sum of an empty list is zero, and the sum of any other list is its first element added to the sum of the rest of it.

And indeed, the code could read almost exactly like that last sentence:

def sumList(xs: List[Int]) = {     if (xs.isEmpty) 0     else xs.head + sumList(xs.tail) } 

(The pattern matching versions, such as that proposed by Kim Stebel, are essentially identical to this, they just express the conditions in a more "functional" way.)