6

私は関数型プログラミングが初めてなので、関数型アプローチを使用して解決するのが難しい問題もあります。

1 から 10.000 までの数字のリストがあり、最大で n (100 としましょう) まで合計されるリストの項目を取得したいとします。そのため、合計が 100 を超えるまで数値を取得します。

命令型プログラミングでは、この問題を解決するのは簡単です。なぜなら、各対話で変数を保持し、目的が達成されたら停止できるからです。

しかし、関数型プログラミングで同じことを行うにはどうすればよいでしょうか? sum 関数は完成したリストで動作するので、まだ完成したリストを持っていません。どうすれば計算を「続行」できますか?

合計が遅延計算された場合、次のように書くことができます。

           (1 to 10000).sum.takeWhile(_ < 100)

PS:どんな回答でもありがたいのですが、速度に関しては明らかに命令型バージョンの方がはるかに最適であるため、毎回合計を計算しないものを希望します。

編集：

命令型ループのアプローチを機能的な再帰関数に「変換」できることを知っています。既存のライブラリ関数の 1 つを使用して、何かが必要になるたびにライブラリ関数を作成しない方法を提供できるかどうかを調べることにもっと興味があります。

4

4 に答える 4

9

を使用しStreamます。

scala> val ss = Stream.from(1).take(10000)
ss: scala.collection.immutable.Stream[Int] = Stream(1, ?)

scala> ss.scanLeft(0)(_ + _)
res60: scala.collection.immutable.Stream[Int] = Stream(0, ?)

scala> res60.takeWhile(_ < 100).last
res61: Int = 91

編集：

コンポーネントの入手もそれほど難しくありません。これはあなたがそれを行う方法です：

scala> ss.scanLeft((0, Vector.empty[Int])) { case ((sum, compo), cur) => (sum + cur, compo :+ cur) }
res62: scala.collection.immutable.Stream[(Int, scala.collection.immutable.Vector[Int])] = Stream((0,Vector()), ?)

scala> res62.takeWhile(_._1 < 100).last
res63: (Int, scala.collection.immutable.Vector[Int]) = (91,Vector(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13))

タプルの 2 番目の部分は、目的の結果です。

明らかなように、この場合、ベクトルを構築するのは無駄です。代わりに、合計に寄与したストリームからの最後の数値のみを保存できます。

scala> ss.scanLeft(0)(_ + _).zipWithIndex
res64: scala.collection.immutable.Stream[(Int, Int)] = Stream((0,0), ?)

scala> res64.takeWhile(_._1 < 100).last._2
res65: Int = 13
于 2012-05-14T11:28:50.467 に答える
1

これは、「関数型」メソッドを使用しても難しくありません。
変更したローカル変数で状態を維持するのではなく、再帰を使用して、パラメーターと戻り値に状態を保持します。

したがって、合計が最大であるリストの最長の最初の部分を返すには、次のようにしNます。

  1. リストが空の場合は完了です。空のリストを返します。
  2. リストの先頭が より大きい場合はN、完了です。空のリストを返します。
  3. それ以外の場合Hは、リストの先頭にします。ここで必要なのは、リストの末尾
    の最初の部分で、その合計が最大で である場合、そのリストに「cons」を追加すれば完了です。 これまで使用してきたのと同じ手順を使用して、これを再帰的に計算できるため、簡単な手順です。N - HH

簡単な擬似コード ソリューション:

sum_to (n, ls) = if isEmpty ls or n < (head ls)
                 then Nil
                 else (head ls) :: sum_to (n - head ls, tail ls)

sum_to(100, some_list)
于 2012-05-14T12:06:07.143 に答える
0

シーケンスを1回通過するだけでよいすべてのシーケンス操作は、時々呼ばれるように、reduceのfoldsを使用して実装できます。関数型プログラミングに慣れてから、フォールドを頻繁に使用しています。

したがって、ここでは奇妙な1つの可能なアプローチ初期値として空のコレクションを使用し、この戦略に従ってフォールドします。処理されたコレクションと新しい値が与えられた場合、それらの合計が十分に低いかどうかを確認し、コレクションに値を費やす場合は何もしません。

その解決策はあまり効率的ではありませんが、次のマップフォールドフィルターzipなどが関数型プログラミングに慣れるための方法であることを強調したいと思います。構文や再帰関数をローピングする代わりに、可能な限りそれらを使用してみてください。

于 2012-05-15T18:29:49.937 に答える