haskell - 長さを計算する Haskell 高階関数

Question

ここで何が起こっているのか理解できませんか？誰でもこのコードを説明できますか? この関数はどのように長さを計算しますか?

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

ラムダ、アンダースコア、アンダースコアと n の間のスペース、および右側のゼロを使用するのはなぜですか?

Answer 1

(\_ n -> 1 + n) 2 つの引数を取り、2 番目の引数よりも 1 つ多い引数を返す関数を意味します。アンダースコアは単にパラメーターが無視されることを意味します。比較のために、ワイルドカード パターン (アンダースコア) を使用しないトップレベルの宣言として、この関数は次のようになります。

foo x n = 1 + n

リストの例を次に示します。

[1, 2, 3, 4]

これは、実際には次の構文糖衣です。

1 : 2 : 3 : 4 : []

eachを与えられた関数にfoldr再帰的に置き換え、関数の後の引数 ( zero ) に置き換えます。したがって、任意の場合は次のようになります。(:)[]foldr f z [1, 2, 3, 4]fz

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

foldr (:) [](これが、指定したのと同じリストを返す理由です。元のリスト構造を再構築することになります。)

この場合、関数fooとゼロ 0 を使用すると、次のようになります。

foo 1 (foo 2 (foo 3 (foo 4 0)))

fooは最初の引数を無視し、2 番目の引数よりも 1 つ多く返すことがわかっています。したがって、これは次と同じです。

1 + (1 + (1 + (1 + 0)))

これは、リストの長さである 4 です。基本的に、折り畳みはリストのすべての要素を無視し、すべての要素のアキュムレータに 1 を追加して、長さを指定します。0 は、プロセス全体を終了するために使用されます。これは、空のリストの長さが 0 であるためです。

これをより詳細に確認するために、各呼び出しを段階的に展開できます。

foldr foo 0 (1 : 2 : 3 : 4 : [])
foo 1 (foldr foo 0 (2 : 3 : 4 : []))
1 + foldr foo 0 (2 : 3 : 4 : [])
1 + foo 2 (foldr foo 0 (3 : 4 : []))
1 + 1 + foldr foo 0 (3 : 4 : [])
1 + 1 + foo 3 (foldr foo 0 (4 : []))
1 + 1 + 1 + foldr foo 0 (4 : [])
1 + 1 + 1 + foo 4 (foldr foo 0 [])
1 + 1 + 1 + 1 + foldr foo 0 []
1 + 1 + 1 + 1 + 0
1 + 1 + 1 + 1
1 + 1 + 2
1 + 3
4