だから、foldl.foldr の構成を理解しようとして頭を悩ませています。次に例を示します。
(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]]
結果は 22 ですが、実際に何が起こっているのでしょうか。
私には、これが起こっているように見えます: foldl (+) 1 [6,15]. 私の疑問はそのfoldr部分に関連しています。すべてのサブリストに 1 を追加すべきではありませんか? このように: foldr (+) 1 [1,2,3]. 私の頭の中では 1 が 1 回だけ追加されますよね？（おそらくそうではありませんが、その方法/理由を知りたいです！）。
私は非常に混乱しています（そして、おそらくすべての混乱を引き起こしています、笑）。ありがとうございました！
(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]]
になる
foldl (foldr (+)) 1 [[1,2,3],[4,5,6]]
だからあなたは得る
foldl (foldr (+)) (foldr (+) 1 [1,2,3]) [[4,5,6]]
の最初のステップの後foldl、または
foldl (foldr (+)) 7 [[4,5,6]]
適用されたものを評価すると(厳密性アナライザーが起動しない限り、実際には がリスト全体をトラバースするfoldrまで評価されないサンクのままになりますが、次の式は評価されたほうが読みやすくなります)、それは次のようになります。foldl
foldl (foldr (+)) (foldr (+) 7 [4,5,6]) []
そして最後に
foldl (foldr (+)) 22 []
~> 22
調べてみましょうfoldl . foldr。それらのタイプは
foldl :: (a -> b -> a) -> (a -> [b] -> a)
foldr :: (c -> d -> d) -> (d -> [c] -> d)
意図的に個別の型変数を使用し、括弧を追加して、それらを 1 つの引数の関数として表示することがより明確になるようにしました (そしてそれらの結果は関数です)。を見るfoldlと、これは一種のリフティング関数であることがわかります: usingaから生成される関数が与えられた場合、それが機能するように(計算を繰り返すことによって)それをリフティングします。関数は似ていますが、引数が逆になっています。ab[b]foldr
申請するとどうなりますfoldl . foldrか？まず、型を導出しましょう: の結果がfoldrの引数と一致するように、型変数を統一する必要がありfoldlます。したがって、次のように置き換える必要があります: a = d, b = [c]:
foldl :: (d -> [c] -> d) -> (d -> [[c]] -> d)
foldr :: (c -> d -> d) -> (d -> [c] -> d)
だから私たちは得る
foldl . foldr :: (c -> d -> d) -> (d -> [[c]] -> d)
そして、その意味は何ですか？まず、foldrtype の引数を持ち上げてc -> d -> dリストを操作し、その引数を逆にして を取得しd -> [c] -> dます。次に、foldlこの関数を再び持ち上げて、[[c]]のリストで動作します[c]。
あなたの場合、持ち上げられる操作(+)は結合的であるため、その適用の順序は気にしません。二重リフティングは、ネストされたすべての要素に操作を適用する関数を作成するだけです。
のみを使用するfoldlと、効果はさらに良くなります。次のように、複数回持ち上げることができます。
foldl . foldl . foldl . foldl
:: (a -> b -> a) -> (a -> [[[[b]]]] -> a)
実際には、(foldl.foldr) f z xs === foldr f z (concat $ reverse xs).
連想操作であってもf、パフォーマンスに影響を与える可能性があるため、アプリケーションの正しい順序が重要です。
私たちはから始めます
(foldl.foldr) f z xs
foldl (foldr f) z xs
と書いてg = foldr f、[x1,x2,...,xn_1,xn] = xsちょっとの間、これは
(...((z `g` x1) `g` x2) ... `g` xn)
(`g` xn) ((`g` xn_1) ... ((`g` x1) z) ... )
foldr f z $ concat [xn,xn_1, ..., x1]
foldr f z $ concat $ reverse xs
したがって、あなたの場合、正しい削減シーケンスは
(foldl.foldr) 1 [[1,2,3],[4,5,6]]
4+(5+(6+( 1+(2+(3+ 1)))))
22
つまり、
Prelude> (foldl.foldr) (:) [] [[1..3],[4..6],[7..8]]
[7,8,4,5,6,1,2,3]
同様に、(foldl.foldl) f z xs == foldl f z $ concat xs. でsnoc a b = a++[b]、
Prelude> (foldl.foldl) snoc [] [[1..3],[4..6],[7..8]]
[1,2,3,4,5,6,7,8]
また、(foldl.foldl.foldl) f z xs == (foldl.foldl) (foldl f) z xs == foldl (foldl f) z $ concat xs == (foldl.foldl) f z $ concat xs == foldl f z $ concat (concat xs)など：
Prelude> (foldl.foldl.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]]
[1,2,3,4,5,6,7,8]
Prelude> (foldl.foldr.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]]
[7,8,1,2,3,4,5,6]
Prelude> (foldl.foldl.foldr) (:) [] [[[1..3],[4..6]],[[7..8]]]
[7,8,4,5,6,1,2,3]