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

To add another possible answer to this, here is a solution I came up with that is a slight variation of @jgaw's answer and uses the @tailrec annotation:

def sum(xs: List[Int]): Int = {
  if (xs.isEmpty) throw new Exception // May want to tailor this to either some sort of case class or do something else

  @tailrec
  def go(l: List[Int], acc: Int): Int = {
    if (l.tail == Nil) l.head + acc // If the current 'list' (current element in xs) does not have a tail (no more elements after), then we reached the end of the list.
    else go(l.tail, l.head + acc) // Iterate to the next, add on the current accumulation
  }

  go(xs, 0)
}

Quick note regarding the checks for an empty list being passed in; when programming functionally, it is preferred to not throw any exceptions and instead return something else (another value, function, case class, etc.) to handle errors elegantly and to keep flowing through the path of execution rather than stopping it via an Exception. I threw one in the example above since we're just looking at recursively summing items in a list.

Answer 2

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 3

def sum(xs: List[Int]): Int = xs.sum

scala> sum(List(1,3,7,5))
res1: Int = 16

scala> sum(List())
res2: Int = 0

Answer 4

If you are required to write a recursive function using isEmpty, head and tail, and also throw exception in case empty list argument:

def sum(xs: List[Int]): Int = 
  if (xs.isEmpty) throw new IllegalArgumentException("sum of empty list") 
  else if (xs.tail.isEmpty) xs.head 
  else xs.head + sum(xs.tail)

Answer 5

Tried the following method without using substitution approach

def sum(xs: List[Int]) = {

  val listSize = xs.size

  def loop(a:Int,b:Int):Int={

    if(a==0||xs.isEmpty)
      b
    else
      loop(a-1,xs(a-1)+b)
  }

  loop(listSize,0)
}

Answer 6

Building heavily on @Kim's answer:

def sum(xs: List[Int]): Int = {
    if (xs.isEmpty) throw new IllegalArgumentException("Empty list provided for sum operation")
    def inner(xs: List[Int]): Int = {
      xs match {
        case Nil => 0
        case x :: tail => xs.head + inner(xs.tail)
      }
    }
    return inner(xs)
  }

The inner function is recursive and when an empty list is provided raise appropriate exception.

Answer 7

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

Answer 8

You cannot make it more easy :

val list  = List(3, 4, 12);
println(list.sum); // result will be 19

Hope it helps :)

Answer 9

Your code is good but you don't need the temporary value num. In Scala [If] is an expression and returns a value, this will be returned as the value of the sum function. So your code will be refactored to:

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

}

If list is empty return 0 else you add the to the head number the rest of the list

Answer 10

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.)

Answer 11

The canonical implementation with pattern matching:

def sum(xs:List[Int]) = xs match {
  case Nil => 0
  case x::xs => x + sum(xs)
}

This isn't tail recursive, but it's easy to understand.

Answer 12

Here's the the "standard" recursive approach:

def sum(xs: List[Int]): Int = {
  xs match {
    case x :: tail => x + sum(tail) // if there is an element, add it to the sum of the tail
    case Nil => 0 // if there are no elements, then the sum is 0
  }
}

And, here's a tail-recursive function. It will be more efficient than a non-tail-recursive function because the compiler turns it into a while loop that doesn't require pushing a new frame on the stack for every recursive call:

def sum(xs: List[Int]): Int = {
  @tailrec
  def inner(xs: List[Int], accum: Int): Int = {
    xs match {
      case x :: tail => inner(tail, accum + x)
      case Nil => accum
    }
  }
  inner(xs, 0)
}