機能的言語での折り畳み/削減の実際的な使用

Question

Fold （別名 reduce）非常に重要な高次関数と見なされます。 Map の観点から表現できます fold (こちらをご覧ください）。しかし、それは私にとって実用的よりも学問的に聞こえます。典型的な使用は、合計、製品、または最大数の数を取得することですが、これらの関数は通常、任意の数の引数を受け入れます。なぜ書くのですか (fold + 0 '(2 3 5)) いつ (+ 2 3 5) 正常に動作します。私の質問は、どのような状況で使用するのが最も簡単または最も自然なのかということです fold?

Answer 1

のポイント fold それはもっと抽象的だということです。以前にはできなかったことをすることができるわけではなく、もっと簡単にできることです。

を使って fold, 、一般化することができます どれか 任意の数の要素に適用する2つの要素に定義された関数。これは通常、リストよりも2つの引数を適用する単一の関数を書き込み、テスト、維持、変更するのがはるかに簡単であるためです。また、書き込み、テスト、維持などが常に簡単です。2つではなく、1つの単純な機能が同様の機能ではなく、1つの単純な機能があります。

以来 fold （そしてそのことについては、 map, filter, 、そして友人）明確に定義された動作をしているので、明示的な再帰よりもこれらの機能を使用してコードを理解する方がはるかに簡単です。

基本的に、1つのバージョンを取得すると、もう1つのバージョンが「無料」になります。最終的に、あなたは同じ結果を得るために少ない仕事をすることになります。

Answer 2

ここにいくつかの簡単な例があります reduce 本当にうまくいきます。

各サブリストの最大値の合計を見つける

Clojure：

user=> (def x '((1 2 3) (4 5) (0 9 1)))
#'user/x
user=> (reduce #(+ %1 (apply max %2)) 0 x)
17

ラケット：

> (define x '((1 2 3) (4 5) (0 9 1)))
> (foldl (lambda (a b) (+ b (apply max a))) 0 x)
17

リストからマップを作成します

Clojure：

user=> (def y '(("dog" "bark") ("cat" "meow") ("pig" "oink")))
#'user/y
user=> (def z (reduce #(assoc %1 (first %2) (second %2)) {} y))
#'user/z
user=> (z "pig")
"oink"

より複雑なClojureの例を特徴とする reduce, 、 チェックアウト 私の解決策 オイラーの問題を投影する 18 & 67.

参照： 削減vs.適用

Answer 3

一般的なLISP関数は、何の議論を受け入れません。

すべての一般的なLISP実装で定義された定義があります call-arguments-limit, 、50以上でなければなりません。

これは、そのような携帯的に書かれた機能が少なくとも50の引数を受け入れるべきであることを意味します。しかし、それはわずか50かもしれません。

この制限は、コンパイラが最適化された呼び出しスキームを使用する可能性があり、無制限の数の引数が渡される可能性のある一般的なケースを提供しないようにするために存在します。

したがって、ポータブルな一般的なLISPコードで大きな（50を超える要素を超える）リストまたはベクトルを処理するには、反復構築物、削減、マップなどを使用する必要があります。したがって、使用しないでください (apply '+ large-list) しかし、使用してください (reduce '+ large-list).

Answer 4

1. あなたの例 (+ 2 3 4）事前に議論の数を知っているので、機能するだけです。折り畳みの動作は、そのサイズが異なる可能性のあるリストのリストです。

2. fold/reduce 「リストダウン」パターンの一般的なバージョンです。シーケンスのすべての要素を順番に処理し、そこから何らかの返品値を計算することに関する各アルゴリズムを表現できます。基本的には、foreachループの機能バージョンです。

Answer 5

foldを使用したコードは通常、読み取るのが厄介です。そのため、人々はMAP、フィルター、存在、合計などを好む理由です。最近では、私は主にコンパイラと通訳者を書いています。これが私がfoldを使用するいくつかの方法です：

• 関数、式、またはタイプの自由変数のセットを計算する
• たとえば、タイプチェックのために、シンボルテーブルに関数のパラメーターを追加します
• 一連の定義から生成されたすべての賢明なエラーメッセージのコレクションを蓄積する
• 事前定義されたすべてのクラスをブートタイムでスモールトークインタープリターに追加します

これらすべての用途に共通しているのは、彼らが 順序 ある種の 設定 また 辞書. 非常に実用的です。

Answer 6

これが他の誰も言及していない例です。

「fold」のような小さな明確なインターフェイスで関数を使用することにより、それを使用するプログラムを破らずにその実装を置き換えることができます。たとえば、aを作成できます 数千のPCで実行される分散バージョン, 、したがって、それを使用したソートアルゴリズムは 分散ソート, 、 等々。あなたのプログラムはなります より堅牢で、よりシンプルで、より速い.

あなたの例は些細なものです： + すでにいくつかの議論を受けており、ほとんど記憶の中で迅速に実行されており、コンパイラを書いた人によってすでに書かれてデバッグされています。これらのプロパティは、実行する必要があるアルゴリズムに当てはまることはありません。