7 
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl step zero (x:xs) = foldl step (step zero x) xs
foldl _    zero []     = zero

（a-> b-> a ）がなぜaを返すのか、また（a-> b-> a）-> a->[b]->aがaを返すのかよくわかりません。（a-> b-> c）-> a->[b]-> cのようになります。以下の例に基づいて誰かが私にそれを説明できますか？ありがとう！

foldl (+) 0 (1:2:3:[])
foldl (+) (0 + 1) (2:3:[])
foldl (+) ((0 + 1) + 2) (3:[])
foldl (+) (((0 + 1) + 2) + 3) ([])
foldl (+) (((0 + 1) + 2) + 3)
4

2 に答える 2

14

aアキュムレータ値bの型を表し、入力の各要素の型を表します。(a -> b -> a)リスト内のいくつかのアイテムであるアキュムレータ値を取り、次のステップに渡すことができる新しいアキュムレータ値を返す関数です。

初期値の型はa、関数の最初の呼び出しでアキュムレータ値を受け取ることができるようにする必要があります。アキュムレータ関数は、アキュムレータ値をフォールドの各ステップに渡すことができるように、を取り、aを返さなければなりません。aフォールドの最終値は必ず でなければなりませんa。これは、フォールド関数の最終呼び出しによって返されるアキュムレータの型であるためです。

(a -> b -> c) -> a -> [b] -> c折りたたみ関数は をとらないため、折りたたみを表現できませんc。アキュムレータを次の折りたたみステップに渡すことができるように、折りたたみ関数の入力と出力は同じ型でなければなりません。

fold 関数が を返した場合に何が起こるかの例を見てみましょうc。

f :: Integer -> Integer -> Bool   -- this is a valid (a -> b -> c)
f acc n = (acc + n) > 0

動的言語を使用しているふりをして、 で折り畳もうとしfます。実行時に何が起こりますか?

foldl f 0 [1]     ~ (0 + 1) > 0            == True :: Bool

foldl f 0 [1, 2]  ~ ((0 + 1) > 0) + 2) > 0 == error - no instance of (+) for Bool
                     \_________/   \
                          |         \
                         Bool      + Integer

互換性のない型で積み上げようとすると、折り畳みが機能しないことがわかります。

于 2013-02-08T08:57:35.867 に答える
2

(型の(a -> b -> a)) 折りたたみ関数の戻り値の型は、最初の入力の型と同じでなければなりません。これは、foldl (+)あなたが与えた（最後の行を除いて、ほぼ正しいです。最後の行を除いて、それは . したがって、型が一致する必要があります。(a -> b -> c)最初の引数と結果の型は if (型が等しい) にのみ一致しa ~ cますが、この場合は a と c が等しいので、両方を a と呼ぶこともできます。折りたたみ関数が型 a の何かを返すとすると、foldl 呼び出し全体の結果も型 a になります。これは、単に折りたたみ関数への最後の呼び出しの結果を返すためです。

于 2013-02-08T08:50:27.960 に答える