1

典型的なアカデミックな例は、リストを合計することです。実用性に光を当てる折り畳みの使用の実例はありますか?

4

3 に答える 3

8

foldおそらく、シーケンスに対する最も基本的な操作です。その有用性を求めることはfor、命令型言語でループの有用性を求めるようなものです。

リスト (または配列、ツリー、または ..)、開始値、および関数を指定すると、fold演算子はリストを 1 つの結果に減らします。また、リストの自然なカタモルフィズム(デストラクタ) でもあります。

リストを入力として取り、リストの要素を調べた後に出力を生成する操作は、折り畳みとしてエンコードできます。例えば

sum      = fold (+) 0

length   = fold (λx n → 1 + n) 0

reverse  = fold (λx xs → xs ++ [x]) []

map f    = fold (λx ys → f x : ys) []

filter p = fold (λx xs → if p x then x : xs else xs) []

折り畳み演算子はリストに固有のものではありませんが、統一された方法で「通常の」データ型に一般化できます。

したがって、さまざまなデータ型に対する最も基本的な操作の 1 つとして、確かにいくつかの用途があります。アルゴリズムをフォールドとして記述できる場合を認識できることは、よりクリーンなコードにつながる便利なスキルです。

参考文献:

于 2012-05-04T12:58:21.683 に答える
1

たくさんの foldLeft の例には、次の関数がリストされています。

  • 和
  • 製品
  • カウント
  • 平均
  • 過去
  • 最後から二番目
  • 含む
  • 得る
  • 弦に
  • 逆行する
  • 個性的
  • 設定する
  • ダブル
  • 挿入ソート
  • ピボット (クイックソートの一部)
  • エンコード (連続する要素を数える)
  • デコード (連続する要素を生成)
  • グループ化 (偶数サイズのサブリストに)
于 2016-10-10T09:16:06.440 に答える
0

私の不完全な答えはそれです：

  • foldrは、問題を原始的なケースに減らしてから、バックアップを組み立てるためのものです（非末尾再帰として動作します）
  • foldlは、問題を減らし、すべてのステップでソリューションを組み立てるためのものです。基本的なケースでは、ソリューションの準備ができています（末尾再帰/反復として機能します）

この質問は、RalfLämmelGoingBananasによる講演をすぐに思い出させました（ rfold演算子の表記はバナナ（|および|）のように見えるため）。再帰をフォールドにマッピングし、一方のフォールドをもう一方のフォールドにマッピングする非常にわかりやすい例があります。

古典的な論文（最初は非常に難しい）は、バナナ、レンズ、を使用した関数型プログラミングです。他のオペレーターの外観にちなんで名付けられた封筒と有刺鉄線。

于 2012-05-05T11:22:28.047 に答える