54

リスト内の値を再帰的に合計するスカラ関数を作成しようとしています。これが私がこれまでに持っているものです:

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

関数の一部として個々の Int 値を合計する方法がわかりません。関数 sum 内で新しい関数を定義することを検討しており、List が繰り返されるときに値を合計するローカル変数を使用しています。しかし、これは必須のアプローチのようです。別の方法はありますか？

4

12 に答える 12

111

また、再帰を直接使用することを避け、代わりにいくつかの基本的な抽象化を使用できます。

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

foldLeftreduce()pythonのとおりです。また、 （SICPなどで）foldRightとして知られているものもあります。accumulate

于 2012-10-13T14:21:08.053 に答える
80

再帰を使用すると、プロセスを英語でどのように説明するかを考える価値があることがよくあります。これは、多くの場合、あまり複雑にならずにコードに変換されるためです。そう...

「整数のリストの合計を再帰的に計算するにはどうすればよいですか?」

「さて、リストの合計は3 :: restOfList？

「なにrestOfList？

「それは何でもかまいません。しかし、覚えておいてください。私たちは再帰的です。そして、リストの合計を計算する関数を持っていませんか?」

「そうそう！ では、合計は3 + sum(restOfList).

「そのとおりです。しかし、唯一の問題は、すべての合計が の別の呼び出しに関して定義されているsum()ため、実際の値を取得できないことです。すべてが実際に到達する何らかの基本ケースが必要になります。 、そしてあなたが値を提供できること。」

「うーん、あなたは正しいです。」 考える...

「そうですね、あなたのリストはどんどん短くなっていきますが、可能な限り短いリストは何ですか?」

「空のリスト？」

「そうです! では、int の空のリストの合計は?」

「ゼロ - 今わかりました。まとめると、空のリストの合計はゼロであり、他のリストの合計は、残りのリストの合計に追加された最初の要素です。

実際、コードは最後の文とほぼ同じように読むことができます。

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

(Kim Stebel によって提案されたようなパターン マッチング バージョンは、本質的にこれと同じであり、より「機能的な」方法で条件を表現するだけです。)

于 2012-09-19T14:50:07.587 に答える
65

「標準」の再帰的アプローチは次のとおりです。

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)
}
于 2012-09-19T14:36:42.947 に答える
40

もっと簡単にすることはできません：

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

それが役に立てば幸い ：）

于 2015-10-20T19:50:17.520 に答える
14

あなたのコードは良いですが、一時的な値 num は必要ありません。Scala では [If] が式で値を返す場合、これは sum 関数の値として返されます。したがって、コードは次のようにリファクタリングされます。

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

}

リストが空の場合は0を返します。それ以外の場合は、リストの残りの部分をヘッド番号に追加します

于 2012-09-19T15:21:02.607 に答える
5

パターン マッチングを使用した正規の実装:

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

これは末尾再帰ではありませんが、理解しやすいです。

于 2012-09-19T14:37:46.390 に答える
3

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

内部関数は再帰的であり、空のリストが提供されると、適切な例外が発生します。

于 2016-10-17T20:18:03.837 に答える
1 
 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)  
}
于 2016-08-18T08:10:30.803 に答える
0

置換アプローチを使用せずに次の方法を試しました

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)
}
于 2016-11-25T07:39:15.543 に答える