[解決済み] foldrを使ったfoldlの書き方

これは紛らわしくて不思議ですね

これは混乱するようで不思議です！トリックを施し、アキュムレータを関数に置き換え、それを初期値に適用して結果を得ます。

Graham Huttonは、次のようにトリックを説明します。 foldl を foldr に変換する。の再帰的な定義を書き下すことから始めます。 foldl :

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []       = v
foldl f v (x : xs) = foldl f (f v x) xs

の静的引数変換でリファクタリングします。 f :

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs = g xs v
    where
        g []     v = v
        g (x:xs) v = g xs (f v x)

では、次のように書き換えてみましょう。 g を浮き上がらせるように v を内側に浮かせる。

foldl f v xs = g xs v
    where
        g []     = \v -> v
        g (x:xs) = \v -> g xs (f v x)

と考えるのと同じです。 g を関数を返す1つの引数の関数として考えるのと同じです。

foldl f v xs = g xs v
    where
        g []     = id
        g (x:xs) = \v -> g xs (f v x)

ここで g のように、リストを再帰的に走査する関数に、ある関数を適用します。 f . 最終的な値は恒等式関数で、各ステップの結果も同様に関数になります。

しかし を使えば、リストに対する非常に似た再帰的な関数が既に手元にあります。 foldr !

2 fold演算子

この演算子は fold 演算子は再帰理論（Kleene, 1952）に起源を持ち、一方で の fold をプログラミング言語の中心概念として使うようになったのは、APLのreduction演算子（Iverson, 1962）、そして後にFPのinsertion演算子（Backus, 1978). Haskell では fold 演算子は次のように定義できる。

fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)

つまり、ある関数が与えられたとき f 型の α → β → β という型と、値 v 型の β である場合、関数 fold f v 型のリストを処理します。 [α] 型の値を与えるために β という型の値を与える。 コンストラクタを [] をリストの末尾にある値 v であり、各コンストラクタは (:) という関数によってリスト内の f . このように fold 演算子はリストを処理するための単純な再帰パターンをカプセル化します。この場合、リストに対する2つのコンストラクタは単に他の値や関数に置き換えられます。リストに関する多くのよく知られた関数は fold .

これは、非常によく似た再帰的なスキームのように見えます。 g 関数と非常によく似た再帰的スキームのように見えます。手近なマジック（Bird、Meertens、Malcolm）をすべて使って、特別なルールである 折り畳みの普遍的性質 という特別なルールを適用する。 g の2つの定義間の等価性である。

g [] = v
g (x:xs) = f x (g xs)

もし

g = fold f v

つまり、折り畳みの普遍的な性質は、次のように述べています。

    g = foldr k v

ここで g は二つの方程式と等価でなければなりません。 k と v :

    g []     = v
    g (x:xs) = k x (g xs)

先ほどのfoldlの設計から、私たちは v == id . しかし、2番目の式では になります。 を計算する。 の定義は k :

    g (x:xs)         = k x (g xs)        
<=> g (x:xs) v       = k x (g xs) v      -- accumulator of functions
<=> g xs (f v x)     = k x (g xs) v      -- definition of foldl
<=  g' (f v x)       = k x g' v          -- generalize (g xs) to g'
<=> k = \x g' -> (\a -> g' (f v x))      -- expand k. recursion captured in g'

という計算された定義を代入すると k と v は というfoldlの定義が得られます。

foldl :: (a -> b -> a) -> a -> [b] -> a    
foldl f v xs =
    foldr
        (\x g -> (\a -> g (f v x)))
        id
        xs
        v

再帰的な g はfoldrコンビネータに置き換えられ、アキュムレータは f の連鎖によって構築される関数になります（右折りではなく左折り）。

これは確かにやや高度なので、この変換を深く理解するために 折り返しの普遍的な性質 を深く理解するには、以下のリンクにある Hutton のチュートリアルをお勧めします。

参考文献