いくつかの説明が順番に！
id 関数とは何ですか? 役割は何ですか？なぜここでそれが必要なのですか？
idは恒等関数であり、関数合成をid x = x使用して一連の関数を構築するときに、ゼロに相当するものとして使用されます。Prelude で定義されていることがわかります。(.)
上記の例では、id 関数はラムダ関数のアキュムレータですか?
アキュムレータは、関数の繰り返し適用によって構築される関数です。アキュムレータに名前を付けているため、明示的なラムダはありませんstep。必要に応じて、ラムダで記述できます。
foldl f a bs = foldr (\b g x -> g (f x b)) id bs a
または、グラハム・ハットンが書くように：
5.1foldlオペレーター
次に、例を一般化して、関数を使用して値を結合し、値を開始値として使用して、リストの要素を左から右の順序で処理するsuml標準演算子を考えてみましょう。foldlfv
foldl :: (β → α → β) → β → ([α] → β)
foldl f v [ ] = v
foldl f v (x : xs) = foldl f (f v x) xs
この演算子を使用sumlすると、 によって簡単に再定義できますsuml = foldl (+) 0。を使用して、他の多くの関数を簡単な方法で定義できますfoldl。たとえば、標準関数は次のようにreverse再定義できfoldlます。
reverse :: [α] → [α]
reverse = foldl (λxs x → x : xs) [ ]
(++)この定義は、非効率的なリストの追加演算子の使用を回避するため、fold を使用した元の定義よりも効率的です。
関数の前のセクションでの計算を単純に一般化すると、次のように関数をsuml再定義する方法が示されます。foldlfold
foldl f v xs = fold (λx g → (λa → g (f a x))) id xs v
対照的に、 はリスト引数の末尾で正格ですが、そうではないためfold、 に関して再定義するfoldlこと
はできません。とに関する多くの有用な「双対性定理」があり、特定のアプリケーションに最適な演算子を決定するためのガイドラインもいくつかあります (Bird, 1998)。foldlfoldfoldfoldl
foldr のプロトタイプは foldr :: (a -> b -> b) -> b -> [a] -> b
Haskell プログラマーは、の型は.foldr(a -> b -> b) -> b -> [a] -> b
最初のパラメーターは2つのパラメーターを必要とする関数ですが、myFoldlの実装のステップ関数は3つのパラメーターを使用します.私は完全に混乱しています
これは紛らわしく、魔法です！トリックを実行し、アキュムレータを関数に置き換えます。関数は初期値に適用され、結果が得られます。
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起源は再帰理論 (Kleene、1952 年) ですfoldが、プログラミング言語の中心的な概念としての使用は、APL のリダクション演算子 (Iverson、1962 年) にまでさかのぼり、後に FP の挿入演算子 (Backus 、1978）。Haskell では、foldリストの演算子は次のように定義できます。
fold :: (α → β → β) → β → ([α] → β)
fold f v [ ] = v
fold f v (x : xs) = f x (fold f v xs)
つまり、 type の関数fと typeα → β → βの値vを指定すると、β関数
は typefold f vのリストを処理して、リストの末尾にある nil コンストラクターを[α]value にβ置き換え、リスト内の各 cons コンストラクターを関数。このように、演算子は、リストを処理するための単純な再帰パターンをカプセル化します。このパターンでは、リストの 2 つのコンストラクターが単純に他の値と関数に置き換えられます。リストに関するおなじみの関数の多くは、 を使用して簡単に定義できます。[]v(:)ffoldfold
これは、関数と非常によく似た再帰スキームのように見えgます。ここでのトリック: 手元にあるすべての利用可能な魔法 (別名、Bird、Meertens、Malcolm) を使用して、fold の普遍的なプロパティでgある特別な規則を適用します。これは、リストを処理する関数の 2 つの定義間の同等性であり、
g [] = v
g (x:xs) = f x (g xs)
場合に限り
g = fold f v
したがって、折り畳みの普遍的な性質は次のように述べています。
g = foldr k v
どこでg_ _kv
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 のチュートリアルをお勧めします。
参考文献