foldl。 foldr関数の構成 - Haskell

Question

私は実際にfoldl.foldrの構成を理解しようと私の脳を揚げています。ここで は一例です：

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

結果は22ですが、本当にここ何が起こっているのか？

私には、これは起こっているようです：foldl (+) 1 [6,15]。 疑問は、foldrの部分に関連しています。すべてのサブリストに1を加えてはいけませんか？このように：foldr (+) 1 [1,2,3]。 私の頭の中では、1回だけ追加されていますね。 （おそらくそうではありませんが、私はどのように/なぜか知りたがっています！）。

私は非常に混乱しています（そしておそらくすべての混乱、ハハを作っています）。 ありがとうございました！

Answer 1

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]] 

stricない限り、我々は適用foldrを評価するのであれば、あなたが（foldl、または

foldl (foldr (+)) 7 [[4,5,6]] 

の最初のステップの後

foldl (foldr (+)) (foldr (+) 1 [1,2,3]) [[4,5,6]] 

を取得

foldl (foldr (+)) 1 [[1,2,3],[4,5,6]] 

なりtnessアナライザはfoldlは、リスト全体を横断したまで、それは現実には、未評価のサンク残る中キックが、次の式は評価される）と、より読みやすいです、それは

foldl (foldr (+)) (foldr (+) 7 [4,5,6]) [] 

し、最終的に

foldl (foldr (+)) 22 [] 
~> 22 

なり

Answer 2

foldl . foldrを調べてみましょう。その種類は、私が意図的に異なった型変数を使用し、それは我々が（そしてその結果が機能している）1つの引数の関数として今それらを表示することがより明白になるように、私は括弧を追加

foldl :: (a -> b -> a) -> (a -> [b] -> a) 
foldr :: (c -> d -> d) -> (d -> [c] -> d) 

です。 foldlを見ると、それは一種の持ち上げ関数であることがわかります。aをaからbを使用して生成する関数を与えた場合、計算を繰り返すことによって[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) 

を取得し、その意味は何ですか？まず、foldrは、タイプc -> d -> dの引数をリスト上で動作させ、引き数を逆にしてd -> [c] -> dを得る。次に、foldlは[[c]] - [c]のリストを処理するためにこの機能を再び持ち上げます。

あなたのケースでは、操作が解除された(+)は連想的なので、アプリケーションの順序には気を付けません。ダブルリフティングは、すべてのネストされた要素に操作を適用する関数を作成するだけです。

我々だけfoldlを使用する場合は、効果がさらに進歩して：私たちは、実際のような

foldl . foldl . foldl . foldl 
    :: (a -> b -> a) -> (a -> [[[[b]]]] -> a) 

Answer 3

で、(foldl.foldr) f z xs === foldr f z (concat $ reverse xs)を複数回持ち上げることができます。

fが連想操作であっても、パフォーマンスに影響を与える可能性があるため、アプリケーションの正しい順序が重要です。

私たちは一瞬g = foldr fと[x1,x2,...,xn_1,xn] = xsと書い

(foldl.foldr) f z xs 
foldl (foldr f) z xs 

で始まり、これはだからあなたの場合には、正しい削減シーケンスはウィットに

(foldl.foldr) 1 [[1,2,3],[4,5,6]] 
4+(5+(6+( 1+(2+(3+ 1))))) 
22 

(...((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 

をです、

同様に0

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]