对List中的值求和

Question

我正在尝试编写一个scala函数,它将递归地对列表中的值求和.这是我到目前为止:

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

我不知道如何将各个Int值相加作为函数的一部分.我正在考虑在函数sum中定义一个新函数,并使用一个局部变量,该函数在List迭代时对值进行求和.但这似乎是一种必要的方法.有替代方法吗？

Answer 1

您也可以避免直接使用递归并使用一些基本的抽象:

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

foldLeft就像reduce()在python中一样.还有foldRight一种也被称为accumulate(例如在SICP中).

Answer 2

通过递归,我经常发现考虑如何用英语描述过程是值得的,因为这通常转化为代码而没有太多的复杂性.所以...

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

"那么,列表的总和是3 :: restOfList什么？

"什么是restOfList？

"它可能是任何东西,你不知道.但请记住,我们是递归的 - 你不具备计算列表总和的功能吗？"

"哦,对了!那么总和就是3 + sum(restOfList).

"那是对的.但现在你唯一的问题是,每个金额都是根据另一个召唤来定义的sum(),所以你永远无法获得实际的价值.你需要某种基本情况,一切都会真正达到,你可以提供一个价值."

"嗯,你是对的." 想...

"好吧,既然你的名单越来越短,那么最短的名单是什么？"

"空单？"

"对了!一个空的清单列表的总和是什么？"

"零 - 我现在得到它.所以把它放在一起,空列表的总和为零,任何其他列表的总和是它的第一个元素添加到其余部分的总和.

事实上,代码可以读取几乎完全像最后一句话:

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

(模式匹配版本,例如Kim Stebel提出的版本,基本上与此相同,它们只是以更"功能"的方式表达条件.)

Answer 3

这是"标准"递归方法:

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

而且,这是一个尾递归函数.它比非尾递归函数更有效,因为编译器将其转换为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)
}

Answer 4

你不能让它变得更容易:

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

希望能帮助到你 :)

Answer 5

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

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

}

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

Answer 6

模式匹配的规范实现:

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

这不是尾递归,但它很容易理解.