7

受講しているクラスの講義ノートの一部を理解しようとしています。長さ関数を次のように定義します。

length = foldr (\_ n -> 1 + n) 0

誰かがこれがどのように機能するか説明できますか? 私はそれについて私の心を包むことができません。

4

3 に答える 3

27

まず、タイプfoldr：(a -> b -> b) -> b -> [a] -> b

使用法をコンテキストにfoldr取り入れて、3つの引数を取ります：関数（a。リストの要素とb。アキュムレータを取り込んで、アキュムレータを返します）、アキュムレータの開始値、およびリスト。foldrリストを介して関数を適用した後、アキュムレータの最終結果を返します。

このコードについて：

length = foldr (\_ n -> 1 + n) 0

ご覧のとおり、リストがありません。したがって、右側の戻り値は、リストを取り込んでInt（と同じ型0）を生成する関数です。タイプ：[a] -> Int。

右側の意味については：(\_ n -> 1 + n) 0

\名前のない関数を宣言することを意味します

_リストから要素を無視することを意味します（aのタイプに対応しfoldrます）。ご存知のfoldrように、リストを調べて、各要素に関数を適用します。これは、関数に渡される要素です。関数では使用しないlengthので、無視する必要があることを示します。

nアキュムレータとして渡されるIntのパラメータです。

->戻ることを意味します

1 + nアキュムレータをインクリメントします。戻り値がに戻され、関数への次の呼び出しに渡すために値が保存されることを想像foldrできfoldrます(\_ n -> 1 + n)。

括弧の0外側は、カウンターの開始値です。

于 2012-07-11T04:17:05.933 に答える
8

関数foldrは右結合演算子でリストを折り畳むことです。演算子(+), を使用すると、関数が何をするかを簡単に理解できます (関数は と同じ動作をしますsum):

foldr (+) 0 [1,2,3,4,5] = 1+(2+(3+(4+(5+0))))

長さ関数の場合、次と同等です。

foldr (\_ n -> 1 + n) 0 [1,2,3,4,5] = 1+(1+(1+(1+(1+0))))

それがfoldr目的です

于 2012-07-11T05:41:27.327 に答える
6

それを理解するには、いくつかの同等の方法があります。1 つ目:foldr f z [1, 2, 3, 4, ..., n]次の値を計算します。

f 1 (f 2 (f 3 (f 4 (f ... (f n z)))))

だからあなたの場合：

length [1,2,3,4] = foldr (\_ n -> 1 + n) 0 [1,2,3,4]  
                 = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 ((\_ n -> 1 + n) 4 0)))
                 = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 ((\_ n -> 1 + n) 3 (1 + 0)))
                 = (\_ n -> 1 + n) 1 ((\_ n -> 1 + n) 2 (1 + (1 + 0)))
                 = (\_ n -> 1 + n) 1 (1 + (1 + (1 + 0)))
                 = 1 + (1 + (1 + (1 + 0)))
                 = 1 + (1 + (1 + 1))
                 = 1 + (1 + 2)
                 = 1 + 3
                 = 4

もう 1 つは、リストをコピーするこの関数から開始することです。

listCopy :: [a] -> [a]
listCopy [] = []
listCopy (x:xs) = x : listCopy xs

些細な関数のように見えるかもしれませんが、基本的にはそれだけですが、空のリストとペア コンストラクターを右側foldrにハードコーディングすることを除いて、引数として提供される任意の定数と関数を使用します。私はときどきこれらの引数を and ( andは Lisp 言語の演算子と定数の名前です) と呼ぶのが好きです。ある意味では、リストを「コピー」しているのに偽のコンストラクタを使用しているためです。[]:fakeConsfakeNilconsnil:[]

foldr fakeCons fakeNil [] = fakeNil
foldr fakeCons fakeNil (x:xs) = fakeCons x (subfold xs)
    where subfold = foldr fakeCons fakeNil

したがって、この解釈では、length関数はリストを「コピー」していますが、空のリストの代わりに を使用し、要素を破棄して現在の合計に 1 を追加する0代わりに.:

の 3 番目の解釈は次のfoldr f z xsとおりです。

  1. zリストが空の場合の問題の解決策です。
  2. flist の要素と部分的な解決策の 2 つの引数を取る関数です:に渡された要素の右側に表示される要素のリストに対する問題の解決策fです。 f次に、「1要素大きい」ソリューションを生成します。

したがって、次の場合length：

  1. 空のリストの長さは 0 なので、 の 2 番目の引数として 0 を使用しますfoldr。
  2. の長さが の場合、 の長xsさnはx:xsですn+1。foldrそれが、 ,への最初の引数\_ n -> n + 1が行っていることです: リストの長さを計算し、引数としてリストの最初の要素 (この場合は無視します) とリストの残りの長さ ( n) を指定します。

この考え方foldrは非常に強力であり、過小評価すべきではありません。基本的に、最初の引数として に渡す関数では、foldr解決しようとしている問題が、扱っているリストよりも短いすべてのリストについて既に解決されていると想定することができます。したがって、引数関数がしなければならないことは、1 要素長いリストの答えを計算することだけです。

于 2012-07-12T17:10:37.513 に答える