scala 汇总列表中的值

Summing values in a List

提问by user701254

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

我正在尝试编写一个 Scala 函数，它将递归地对列表中的值求和。这是我到目前为止所拥有的：

  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 ?

我不知道如何将各个 Int 值作为函数的一部分求和。我正在考虑在函数 sum 中定义一个新函数，并使用一个局部变量来对值进行求和，因为 List 正在迭代。但这似乎是一种势在必行的方法。有没有替代方法？

回答by eivanov

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)

foldLeftis as reduce()in python. Also there is foldRightwhich is also known as accumulate(e.g. in SICP).

foldLeft就像reduce()在python中一样。还有foldRight一个也被称为accumulate（例如在 SICP 中）。

回答by Andrzej Doyle

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.

“如何递归计算整数列表的总和？”

“嗯，一份清单的总和是3 :: restOfList多少？

“什么restOfList？

“它可以是任何东西，你不知道。但请记住，我们是递归的——你没有计算列表总和的函数吗？”

“哦，对了！那么总和就是3 + sum(restOfList)。

“没错。但现在你唯一的问题是每一个总和都是根据另一个调用来定义的sum()，所以你永远无法得到一个实际的值。你需要某种基本情况，一切都会实际达到，并且您可以为其提供价值。”

“嗯，你说得对。” 认为...

“嗯，既然你们的名单越来越短，那么最短的名单是什么？”

“空单？”

“对！一个空的整数列表的总和是多少？”

“零 - 我现在明白了。所以把它放在一起，一个空列表的总和为零，任何其他列表的总和是它的第一个元素添加到它的其余部分的总和。

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

（模式匹配版本，例如 Kim Stebel 提出的版本，本质上与此相同，它们只是以更“功能”的方式表达条件。）

回答by dhg

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:

而且，这是一个尾递归函数。它将比非尾递归函数更有效，因为编译器将其转换为 while 循环，不需要为每次递归调用在堆栈上推送新帧：

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

回答by GuillaumeAgis

You cannot make it more easy :

你不能让它更容易：

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

Hope it helps :)

希望能帮助到你 ：）

回答by Makis Arvanitis

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:

您的代码很好，但您不需要临时值 num。在 Scala 中 [If] 是一个表达式并返回一个值，这将作为 sum 函数的值返回。所以你的代码将被重构为：

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

如果列表为空返回 0 否则将列表的其余部分添加到头部编号

回答by Kim Stebel

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.

这不是尾递归，但很容易理解。

回答by Segmented

Building heavily on @Kim's answer:

大量建立在@Kim 的回答上：

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.

内部函数是递归的，当提供空列表时会引发适当的异常。

回答by Bilal Wahla

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

如果需要使用 isEmpty、head 和 tail 编写递归函数，并在空列表参数的情况下抛出异常：

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)

回答by AYAN JAVA

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

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

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

回答by abhi

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 @tailrecannotation:

要为此添加另一个可能的答案，这是我想出的一个解决方案，它是@jgaw 答案的一个细微变化，并使用了@tailrec注释：

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.

关于检查传入的空列表的快速说明；在进行函数式编程时，最好不要抛出任何异常，而是返回其他内容（另一个值、函数、案例类等）以优雅地处理错误并继续通过执行路径而不是通过Exception. 我在上面的例子中扔了一个，因为我们只是在看递归地总结列表中的项目。