Fold（高階関数）

関数型プログラミングにおいて、fold (または、 Reduce、Accumulate、Aggregate、Compress、またはInjectとも呼ばれる) は、再帰的なデータ構造を分析し、指定された結合操作を使用して、その構成要素を再帰的に処理した結果を再結合し、戻り値を構築する高階関数のファミリを指します。通常、foldは、結合関数、データ構造の最上位ノード、および特定の条件下で使用されるいくつかのデフォルト値とともに提供されます。次に、 foldは、関数を体系的に使用して、データ構造の階層の要素を結合します。

ある意味では、フォールドは展開と双対です。展開はシード値を受け取り、関数をコアカーシブに適用して、コアカーシブなデータ構造を段階的に構築する方法を決定します。一方、フォールドは構造を再帰的に分解し、各ノードでその終端値と再帰結果に結合関数を適用した結果に置き換えます(展開のアナモルフィズムに対して、カタモルフィズム)。

折り畳みは、データ構造の構造コンポーネントを一貫して関数と値に置き換えることと見なすことができます。たとえば、リストは、多くの関数型言語で 2 つのプリミティブから構築されます。すべてのリストは、一般にnil   ( []) と呼ばれる空のリスト、または別のリストの前に要素を付加して構築され、関数 ( Haskell ではコロンとして記述) の適用の結果として、コンス  ノード(  ) と呼ばれるものが作成されます。リストの折り畳みは、リストの末尾の nil を特定の値に置き換え、  各コンスを特定の関数に置き換えることと見なすことができます。これらの置き換えは、次の図で確認できます。 Cons(X1,Cons(X2,Cons(...(Cons(Xn,nil)))))cons(:)

構造変換を一貫した方法で実行する別の方法があります。結合関数に入力するときに、各ノードの 2 つのリンクの順序を反転します。

これらの図は、リストの右折り畳みと左折り畳みを視覚的に示しています。また、 がfoldr (:) []リストの恒等関数 ( Lisp用語では浅いコピー)であるという事実も強調しています。これは、 consを に、nilを に置き換えても結果が変わらないためです。左折り畳みの図は、リスト を逆にする簡単な方法を示しています。追加する要素が結合関数の右側のパラメータになったため、 cons へのパラメータを反転する必要があることに注意してください。この観点からわかるもう 1 つの簡単な結果は、を持つ要素に作用する関数を次のように構成することにより、に関して高階マップ関数を記述することです。 consnilfoldl (flip (:)) []foldrcons

 マップ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 は右 に関連付ける  2 項演算と見なすことができ、その逆も同様です。

関数がマグマ、つまりその型が対称的 ( a → a → a) であり、結果の型がリスト要素の型と同じである場合、括弧は任意の方法で配置され、入れ子になった部分式のバイナリ ツリー((1 + 2) + (3 + 4)) + 5が作成されます (例: ) 。二項演算f  が結合的である場合、この値は明確に定義されます (つまり、どの括弧で囲んでも同じです)。ただし、計算方法の操作の詳細は異なります。fが非厳密 で  ある場合、これは効率に大きな影響を与える可能性があります。

線形フォールドはノード指向であり、リストの各ノードに対して一貫した方法で動作しますが、ツリー状のフォールドはリスト全体指向であり、ノードのグループ間で一貫した方法で動作します。

多くの場合、操作fの単位元を初期値zとして選択する必要があります。初期値が適切ではないと思われる場合、たとえば、2 つのパラメーターの最大値を計算する関数を空でないリストにわたって畳み込んでリストの最大要素を取得する場合、リストの最後の要素と最初の要素をそれぞれ初期値として使用するとのバリエーションがあります。Haskell や他のいくつかの言語では、これらはおよび と呼ばれ、1 は初期要素の自動提供を意味し、適用されるリストには少なくとも 1 つの要素がなければならないことを意味します。 foldrfoldlfoldr1foldl1

これらのフォールドは、型対称の二項演算を使用します。つまり、引数と結果の両方の型は同じである必要があります。リチャード・バードは、2010 年の著書で^[2]「空でないリストの一般的なフォールド関数」を提案していますfoldrn。これは、フォールド自体を開始する前に、追加の引数関数を適用して最後の要素を結果の型の値に変換し、通常のように型非対称の二項演算を使用して、リストfoldrの要素の型とは異なる型の結果を生成できます。

Haskell を例にするとfoldl、foldrいくつかの方程式で定式化できます。

 折り畳み:: ( b -> a -> b ) -> b -> [ a ] -> b折り畳みf z [] = z折り畳みf z ( x : xs ) =折り畳み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 :ペアf xs ) foldi1 f [ x ] = x foldi1 f ( x : xs ) = f x ( foldi1 f (ペアf xs ))         
            
 
         
            

遅延評価、つまり非厳密な評価がある場合、は、リストの先頭へのffoldrの適用と、リストの残りの部分に対する再帰的な折り返しを直ちに返します。したがって、 f が、その「右側」、つまり2 番目の引数の再帰的なケースを参照せずに結果の一部を生成でき、結果の残りの部分が要求されない場合、再帰は停止します (例: )。これにより、右折り返しが無限リストに対して動作できるようになります。対照的に、 は、リストの最後に到達するまで、新しいパラメータを使用して直ちに自分自身を呼び出します。この末尾再帰は、ループとして効率的にコンパイルできますが、無限リストをまったく処理できません。無限ループで永久に再帰することになります。 head == foldr (\a b->a) (error "empty list")foldl

リストの末尾に到達すると、ネストされた左深化の-適用によって式が事実上構築され、それが呼び出し元に渡されて評価されます。関数がここで最初に 2 番目の引数を参照し、再帰ケース (ここでは左側、つまり最初の引数)を参照せずに結果の一部を生成できる場合、再帰は停止します。つまり、 が右側で再帰している間は、遅延結合関数を使用してリストの要素を左から検査できます。逆に、 が左側で再帰している間は、遅延結合関数を使用してリストの要素を右から検査することもできます (選択する場合など)。 foldlfffoldrfoldllast == foldl (\a b->b) (error "empty list")

リストの反転も末尾再帰的です ( を使用して実装できます)。有限リストでは、これは left-fold と reverse を組み合わせて、末尾再帰的な方法で right fold を実行することができることを意味します ( を参照  )。そのためには、関数 を変更して引数の順序を逆にし (つまり)、right-fold が構築する式の表現を末尾再帰的に構築します。無関係な中間リスト構造は、継続渡しスタイルの手法 で削除できます。同様に、( は、 の結合関数への引数の順序が反転している Haskell などの言語でのみ必要であり、たとえば Scheme では、と の両方への結合関数に同じ引数の順序が使用されています)。 rev = foldl (\ys x -> x : ys) []1+>(2+>(3+>0)) == ((0<+3)<+2)<+1ffoldr f z == foldl (flip f) z . foldl (flip (:)) []foldr f z xs == foldl (\k x-> k . f x) id xs zfoldl f z xs == foldr (\x k-> k . flip f x) id xs zflipfoldlfoldlfoldr

もう 1 つの技術的なポイントは、遅延評価を使用する左折り畳みの場合、再帰呼び出しが行われる前に新しい初期パラメータが評価されないことです。これにより、リストの末尾に到達し、結果として得られる潜在的に巨大な式を評価しようとすると、スタック オーバーフローが発生する可能性があります。このため、このような言語では、再帰呼び出しを行う前に初期パラメータの評価を強制する、より厳格な左折り畳みのバリエーションが提供されることがよくあります。Haskell では、これはライブラリfoldl'内の (アポストロフィに注意。「プライム」と発音) 関数です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" (マップ表示[ 1 .. 13 ]) "(((((1+2)+(3+4))+((5+6)+(7+8)))+(((9+10)+(11+12))+13))+0)" λ > foldi ( \ x y -> concat [ "(" , x , "+" , y , ")" ]) "0" (マップ表示[ 1 .. 13 ]) "(1+((2+3)+(((4+5)+(6+7))+((((8+9)+(10+11))+(12+13))+0))))"          

 
          

 
          

 
          

無限の木のような折り畳みは、例えばHaskellのエラトステネスの無限ふるいによる再帰的な素数生成で実証されています。

素数= 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マイナス[[ 2 * x , 3 * x .. n ] | x <- [ 1 .. n ]]         

例えば有限リストの場合、マージソート（およびその重複除去型nubsort）は、木のような折り畳みを使用して簡単に定義できます。

マージソートxs =折り畳みマージ[] [[ x ] | x <- xs ] nubsort xs =折り畳みユニオン[] [[ x ] | x <- xs ]          
            

関数 は のmerge重複を保持する変形ですunion。

関数headとをlast折り畳みによって次のように定義できる。

head = foldr ( \ x r -> x ) (エラー"head: 空のリスト" ) last = foldl ( \ a x -> x ) (エラー"last: 空のリスト" )        
        

Foldは多態的関数である。定義を持つ 任意のgに対して

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

gは次のように表される^[12]

 g =折り畳みfv​    

また、無限リストを持つ遅延言語では、固定小数点コンビネータをfoldを介して実装することができ、^[13]反復をfoldに減らすことができることを証明しています。

 y f = foldr ( \ _ -> f ) undefined (繰り返しundefined )         

• 集計関数
• 反復二項演算
• カタモルフィズム、褶曲の一般化
• 準同型性
• マップ（高階関数）
• プレフィックス合計
• 再帰データ型
• 削減演算子
• 構造的再帰

• 「高階関数 - マップ、フォールド、フィルター」
• 「ユニット 6: 高次の折り畳み関数」
• 「Tcl で折り畳む」
• 「左折り畳みと右折り畳みからのリスト準同型性の構築」
• 「魔法の折り紙」