Loading article…
関数型プログラミングにおいて、フォールドとは、再帰的なデータ構造を分析し、指定された結合操作を用いて、その構成要素を再帰的に処理した結果を再結合し、戻り値を生成する高階関数です。フォールドは、リデュース、アキュムレート、アグリゲート、コンプレス、インジェクトとも呼ばれます。通常、フォールドには、結合関数、データ構造の最上位ノード、そして場合によっては特定の条件下で使用されるデフォルト値が与えられます。フォールドは、その関数を体系的に使用して、データ構造の階層構造の要素を結合していきます。
フォールドはある意味でアンフォールドと双対です。アンフォールドはシード値を受け取り、関数を共再帰的に適用して、共再帰的なデータ構造を段階的に構築する方法を決定します。一方、フォールドは再帰的にその構造を分解し、各ノードの終端値に結合する関数を適用した結果と再帰的な結果で置き換えます（カタモルフィズム、アンフォールドのアナモルフィズムとは対照的）。
フォールドは、データ構造の構造要素を関数と値で一貫して置き換えるものと考えることができます。たとえば、多くの関数型言語では、リストは2つの基本要素から構築されます。任意のリストは、空のリスト（一般にnilと呼ばれる）（[]）であるか、別のリストの前に要素をプレフィックスとして追加してconsノード（）と呼ばれるものを作成することによって構築されます。consノードは、関数（ Haskell ではコロンとして記述される）を適用した結果です。リストに対するフォールドは、リストの末尾にあるnilを特定の値に置き換え、各consを特定の値に置き換えるものと考えることができます。これらの置き換えは、図で表すことができます。 Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil))))) cons(:)
構造変換を一貫した方法で実行する別の方法として、各ノードの2つのリンクの順序を反転させて結合関数に入力する方法があります。
これらの図は、リストの右折り畳みと左折り畳みを視覚的に示しています。また、consを に、nilを に置き換えても結果が変わらないことから、foldr (:) []はリストの恒等関数（Lisp用語では浅いコピー）であることも強調しています。左折り畳みの図は、リストを反転させる簡単な方法を示唆しています。 。追加する要素が結合関数の右辺のパラメータになるため、cons のパラメータを反転させる必要があることに注意してください。この観点から簡単にわかるもう 1 つの結果は、要素に作用する関数を と合成して、高階マップ関数をで表すことです。consnilfoldl (flip (:)) []foldrcons
map f = foldr (( : ) . f ) []ここで、ピリオド（.）は関数合成を表す演算子です。
この考え方は、様々な種類の木構造など、他の代数的データ型や構造に対して、折り畳みのような関数を設計するためのシンプルな方法を提供する。データ型のコンストラクタを所定の関数で再帰的に置き換え、型の定数値を所定の値で置き換える関数を作成する。このような関数は一般にカタモルフィズムと呼ばれる。
リストを[1,2,3,4,5]加算演算子で折り畳むと、リストの要素の合計である 15 になります[1,2,3,4,5]。大まかに言えば、この折り畳みはリスト内のコンマを + 演算に置き換えることで を得ると考えることができます1 + 2 + 3 + 4 + 5。[ 1 ]
上記の例では、+ は結合法則を満たす演算なので、括弧の有無に関わらず最終結果は同じになりますが、計算方法は異なります。非結合法則を満たす二項関数の一般的な場合、要素の結合順序によって最終結果の値に影響が出ることがあります。リストの場合、これを実現する方法は 2 つあります。最初の要素と残りの要素を再帰的に結合した結果と結合する方法 (右フォールドと呼ばれる) と、最後の要素を除くすべての要素を再帰的に結合した結果と最後の要素と結合する方法 (左フォールドと呼ばれる) です。これは、 HaskellやPrologの用語で言うと、二項演算子が右結合か左結合かに相当します。右フォールドの場合、合計は のように括弧で囲まれますが、左フォールドの場合は のように括弧で囲まれます。1 + (2 + (3 + (4 + 5)))(((1 + 2) + 3) + 4) + 5
実際には、右折りの場合はリストの末尾に達したときに使用する初期値、左折りの場合はリストの最初の要素と最初に結合する初期値を持つのが便利で自然です。上記の例では、値 0 (加法単位元) が初期値として選択され、1 + (2 + (3 + (4 + (5 + 0))))右折りの場合は、((((0 + 1) + 2) + 3) + 4) + 5左折りの場合はとなります。乗算の場合、初期値として 0 を選択しても機能しません0 * 1 * 2 * 3 * 4 * 5 = 0。乗算の単位元は 1 です。これにより、結果はとなります1 * 1 * 2 * 3 * 4 * 5 = 120 = 5!。
結合関数f の型が非対称である場合 (例: a → b → b)、つまり結果の型がリストの要素の型と異なる場合、初期値の使用が必要です。この場合、線形の適用チェーンが可能になるように、 fの結果と同じ型の初期値を使用する必要があります。それが左向きか右向きかは、結合関数が引数に期待する型によって決まります。2 番目の引数が結果と同じ型でなければならない場合、f は右側で を結合する二項演算と見なすことができ、その逆も同様です。
関数がマグマ、つまり型が対称である場合（a → a → a）、結果の型がリスト要素の型と同じであれば、括弧は任意の方法で配置できるため、ネストされた部分式の二分木が作成されます（例：）。二項演算f((1 + 2) + (3 + 4)) + 5が結合法則を満たす場合、この値は明確に定義されます。つまり、括弧の配置に関係なく同じ値になりますが、計算方法の操作上の詳細は異なります。f が厳密でない場合、これは効率に大きな影響を与える可能性があります。
線形フォールドはノード指向であり、リストの各ノードに対して一貫した方法で動作するのに対し、ツリー状フォールドはリスト全体指向であり、ノードのグループ全体にわたって一貫した方法で動作します。
演算fの単位元を初期値zとして選択したい場合がよくあります。適切な初期値がない場合、例えば、2 つのパラメータの最大値を計算する関数を空でないリストに畳み込んでリストの最大要素を取得したい場合、リストの最後の要素と最初の要素をそれぞれ初期値として使用する と のバリアントがあります。Haskell や他のいくつかの言語では、これらは と と呼ばれ、1は初期要素の自動提供と、これらが適用されるリストには少なくとも 1 つの要素が必要であることを示しています。foldrfoldlfoldr1foldl1
これらのフォールドは型対称な二項演算を使用します。つまり、引数と結果の両方の型が同じである必要があります。リチャード・バードは2010年の著書で[ 2 ]「空でないリストに対する一般的なフォールド関数」を提案していますfoldrn。これは、フォールド自体を開始する前に、追加の引数関数を適用して最後の要素を結果型の値に変換し、通常の二項演算のように型非対称な二項演算を使用して、foldrリストの要素の型とは異なる型の結果を生成することができます。
Haskellを例にとると、foldlいくつfoldrかの式で定式化できます。
foldl :: ( b -> a -> b ) -> b -> [ a ] -> b foldl f z [] = z foldl f z ( x : xs ) = foldl f ( f z x ) xsリストが空の場合は、結果を初期値とする。そうでない場合は、古い初期値と最初の要素にfを適用した結果を新しい初期値として、リストの末尾を折り返す。
foldr :: ( a -> b -> b ) -> b -> [ a ] -> b foldr f z [] = z foldr f z ( x : xs ) = f x ( foldr f z xs )リストが空の場合は、結果は初期値zになります。そうでない場合は、最初の要素にfを適用し、残りの要素を畳み込んだ結果を使用します。
リストは、有限リストと無限定義リストの両方において、ツリー状に折り畳むことができる。
foldt f z [] = z foldt f z [ x ] = f x z foldt f z xs = foldt f z ( pairs f xs ) foldi f z [] = z foldi f z ( x : xs ) = f x ( foldi f z ( pairs f xs )) pairs f ( x : y : t ) = f x y : pairs f t pairs _ t = t関数の場合、定義が不明確なfoldiリストに対して暴走評価を避けるために、関数は常に2番目の引数の値を要求してはならず、少なくともそのすべてを要求したり、すぐに要求したりしてはならない（以下の例を参照）。f
foldl1 f [ x ] = x foldl1 f ( x : y : xs ) = foldl1 f ( f x y : xs )foldr1 f [ x ] = x foldr1 f ( x : xs ) = f x ( foldr1 f xs )foldt1 f [ x ] = x foldt1 f ( x : y : xs ) = foldt1 f ( f x y : pairs f xs ) foldi1 f [ x ] = x foldi1 f ( x : xs ) = f x ( foldi1 f ( pairs f xs ))遅延評価または非厳密評価が存在する場合、はリストの先頭へのffoldrの適用と、リストの残りの部分への折り畳みの再帰ケースを直ちに返します。したがって、 f が「右側」、つまり2 番目の引数にある再帰ケースを参照せずに結果の一部を生成でき、結果の残りの部分が要求されない場合、再帰は停止します (例: )。これにより、右折り畳みは無限リストで動作できます。対照的に、はリストの末尾に到達するまで、新しいパラメータで自身を直ちに呼び出します。この末尾再帰はループとして効率的にコンパイルできますが、無限リストをまったく処理できません。無限ループで永遠に再帰します。head==foldr(\ab->a)(error"empty list")foldl
リストの末尾に達すると、ネストされた左深化アプリケーションによって式が構築され、それが評価のために呼び出し元に提示されます。関数がここで最初に 2 番目の引数を参照し、再帰ケース (ここでは左側、つまり最初の引数) を参照せずに結果の一部を生成できる場合、再帰は停止します。これは、右側で再帰している間は、遅延結合関数がリストの要素を左側から検査することを可能にし、逆に、左側で再帰している間は、遅延結合関数がそう望む場合 (たとえば、)、リストの要素を右側から検査することを可能にすることを意味します。foldlfffoldrfoldllast==foldl(\ab->b)(error"empty list")
リストの反転も末尾再帰です（ を使用して実装できます）。有限リストの場合、これは、関数を修正して引数の順序を反転させ（つまり、）、末尾再帰的に式の表現を構築するように、left-fold と reverse を組み合わせて、right-fold で構築する式の表現を構築することで、right-fold で構築する式を、left-fold と reverse を組み合わせて末尾再帰的に実行できることを意味します（ を参照）。余分な中間リスト構造は、継続渡しスタイルのテクニック で削除できます。同様に、（は、と の両方の結合関数に同じ引数の順序が使用される Scheme とは異なり、Haskell のような結合関数への引数の順序が反転している言語でのみ必要です）。rev=foldl(\ysx->x:ys)[]1+>(2+>(3+>0))==((0<+3)<+2)<+1ffoldrfz==foldl(flipf)z.foldl(flip(:))[]foldrfzxs==foldl(\kx->k.fx)idxszfoldlfzxs==foldr(\xk->k.flipfx)idxszflipfoldlfoldlfoldr
もう一つの技術的なポイントは、遅延評価を使用する左畳み込みの場合、再帰呼び出しが行われる前に新しい初期パラメータが評価されないことです。これは、リストの末尾に到達して結果として得られる巨大な式を評価しようとしたときにスタックオーバーフローを引き起こす可能性があります。このため、このような言語では、再帰呼び出しを行う前に初期パラメータの評価を強制する、より厳密な左畳み込みのバリアントが提供されることがよくあります。Haskell では、これはライブラリfoldl'の (アポストロフィに注意、'prime' と発音) 関数ですData.List(ただし、遅延データコンストラクタで構築された値を強制しても、その構成要素が自動的に強制されるわけではないことに注意してください)。末尾再帰と組み合わせることで、このような畳み込みはループの効率に近づき、最終結果の遅延評価が不可能または望ましくない場合に定数空間操作を保証します。
Haskellインタープリタを使用すると、fold関数が実行する構造変換を文字列の構築によって示すことができます。
λ > foldr ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(1+(2+(3+(4+(5+(6+(7+(8+(9+(10+(11+(12+(13+0)))))))))))))" λ > foldl ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(((((((((((((0+1)+2)+3)+4)+5)+6)+7)+8)+9)+10)+11)+12)+13)" λ > foldt ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ > foldi ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" ( map show [ 1 .. 13 ]) "(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"無限ツリー状の折り畳みは、例えば、Haskellのエラトステネスの無限篩による再帰的素数生成で実証されています。
primes = 2 : _Y (( 3 : ) . minus [ 5 , 7 .. ] . foldi ( \ ( x : xs ) ys -> x : union xs ys ) [] . map ( \ p -> [ p * p , p * p + 2 * p .. ])) _Y g = g ( _Y g ) -- = g . g . g . g . ...ここで、関数はunion順序付きリストに対して局所的に動作し、それらの集合の和集合と差集合を効率的に生成します。minus
素数の有限接頭辞は、整数の列挙された倍数のリストに対する集合差演算の折り畳みとして簡潔に定義される。
primesTo n = foldl1 minus [[ 2 * x , 3 * x .. n ] | x <- [ 1 .. n ]]有限リストの場合、例えばマージソート（およびその重複除去版nubsort）は、ツリー状の折り畳みを使用して次のように簡単に定義できます。
mergesort xs = foldt merge [] [[ x ] | x <- xs ] nubsort xs = foldt union [] [[ x ] | x <- xs ]関数はmerge、重複を保持するバリアントですunion。
関数はhead、last折り畳みによって定義できた可能性があります。
head = foldr ( \ x r -> x ) ( error "head: 空のリスト" ) last = foldl ( \ a x -> x ) ( error "last: 空のリスト" )Fold は多相関数です。定義を持つ任意のgに対して
g [] = v g ( x : xs ) = f x ( g xs )g = foldr f vまた、無限リストを持つ遅延言語では、フォールドを使用して固定点コンビネータを実装できます[ 13 ]。これは、反復をフォールドに削減できることを証明しています。
y f = foldr ( \ _ -> f ) undefined ( repeat undefined )functools.reduce：import functools 参考reduce：from functools import reduce