9

Fold(別名reduce) は、非常に重要な高次関数と見なされます。Mapで表すことができますfold(ここを参照)。しかし、私には実用的というよりもアカデミックに聞こえます。典型的な用途は、数値の合計、積、または最大値を取得することですが、これらの関数は通常、任意の数の引数を受け入れます。(fold + 0 '(2 3 5))では、なぜ(+ 2 3 5)うまくいくのかを書くのです。私の質問は、どのような状況で使用するのが最も簡単または最も自然foldですか?

4

6 に答える 6

13

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

を使用すると、2 つの要素で定義された任意のfold関数を一般化して、任意の数の要素に適用できます。通常、リストよりも 2 つの引数を適用する単一の関数を作成、テスト、保守、および変更する方がはるかに簡単であるため、これは勝利です。そして、似ているが完全ではない機能を持つ 2 つの関数ではなく、1 つの単純な関数を作成、テスト、保守などする方が常に簡単です。

fold(さらに言えば、map、 、およびその仲間) には明確に定義された動作があるためfilter、明示的な再帰よりもこれらの関数を使用したコードを理解する方がはるかに簡単です。

基本的に、1 つのバージョンを取得すると、もう 1 つのバージョンを「無料」で取得できます。最終的には、同じ結果を得るために行う作業が少なくなります。

于 2011-03-16T21:28:07.240 に答える
8

reduce以下に、実際にうまく機能する簡単な例をいくつか示します。

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

クロージャ:

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

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

クロージャ:

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 の例については、Project Euler の問題18 & 67に対する私の解決策reduceを確認してください。

参照: reduce と apply

于 2011-03-16T21:27:20.663 に答える
7

Common Lisp では、関数は任意の数の引数を受け入れません。

すべての Common Lisp 実装CALL-ARGUMENTS-LIMITで定義された定数があり、これは 50 以上でなければなりません。

これは、そのような移植可能に作成された関数は、少なくとも 50 個の引数を受け入れる必要があることを意味します。しかし、それは50だけかもしれません。

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

したがって、移植可能な Common Lisp コードで大きな (50 要素を超える) リストまたはベクトルを実際に処理するには、反復構造、reduce、map などを使用する必要があります。(apply '+ large-list)したがって、使用しないで使用することも必要(reduce '+ large-list)です。

于 2011-03-18T09:18:26.363 に答える
5

fold を使用するコードは通常、読みにくいものです。そのため、利用可能な場合は、map、filter、exists、sum などが好まれます。最近は主にコンパイラとインタープリタを書いています。ここに私が折り畳みを使用するいくつかの方法があります:

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

これらすべての用途に共通しているのは、シーケンスに関する情報を何らかのセットまたはディクショナリに蓄積していることです。 実用性抜群。

于 2011-03-17T01:46:36.827 に答える
4

  1. あなたの例(+ 2 3 4)は、引数の数が事前にわかっているためにのみ機能します。折り畳みは、さまざまなサイズのリストで機能します。

  2. fold/reduceは、"cdr-ing down a list" パターンの一般的なバージョンです。シーケンスのすべての要素を順番に処理し、そこからの戻り値を計算する各アルゴリズムは、それで表現できます。これは基本的に foreach ループの機能バージョンです。

于 2011-03-16T22:36:38.733 に答える
3

これは、他の誰もまだ言及していない例です。

「fold」のような小さく明確に定義されたインターフェースを備えた関数を使用することにより、それを使用するプログラムを壊すことなく、その実装を置き換えることができます。たとえば、数千台のPCで実行される分散バージョンを作成できるため、それを使用した並べ替えアルゴリズムは分散並べ替えになります。プログラムはより堅牢に、よりシンプルに、そしてより速くなります。

あなたの例は些細なものです。+すでに任意の数の引数を取り、小さなメモリですばやく実行され、コンパイラを作成した人によってすでに作成およびデバッグされています。これらのプロパティは、実行する必要のあるアルゴリズムには当てはまらないことがよくあります。

于 2011-03-16T22:45:10.537 に答える