共起

コンピュータ サイエンスでは、共帰は再帰と双対になるタイプの操作です。再帰は分析的に動作し、ベース ケースから離れたデータから始めて、それを小さなデータに分割し、ベース ケースに到達するまで繰り返しますが、共帰は合成的に動作し、ベース ケースから始めてそれを構築し、ベース ケースから離れたデータを反復的に生成します。簡単に言うと、共帰アルゴリズムは、自身が生成したデータを、利用可能になり、必要になったときに少しずつ使用して、さらにデータ ビットを生成します。類似しているが異なる概念に生成再帰があります。これは、共帰と再帰に固有の明確な「方向」がない場合があります。

再帰では、任意の複雑なデータを単純なデータ (基本ケース) に縮小できる限り、プログラムはそのデータを操作できますが、共再帰では、単純なデータ (基本ケース) から一連の有限ステップで生成できる限り、プログラムはストリームなどの任意の複雑で潜在的に無限のデータ構造を作成できます。再帰は終了せず、基本状態に到達しない場合がありますが、共再帰は基本状態から開始し、後続のステップを決定論的に生成します。ただし、無限に続行する (したがって厳密な評価では終了しない) 場合や、生成するよりも多くを消費して非生産的になる場合もあります。従来、再帰的として分析される多くの関数は、代わりに、おそらくより自然に、階乗などの再帰関係など、特定の段階で終了する共再帰関数として解釈できます。

共起は、結果として有限および無限の データ構造の両方を生成でき、自己参照データ構造を使用することもできます。共起は、潜在的に無限の構造の有限のサブセットのみを生成するために、遅延評価と組み合わせて使用​​されることがよくあります (一度に無限の構造全体を生成しようとするのではなく)。共起は関数型プログラミングにおいて特に重要な概念であり、関数型プログラミングでは、共起とコデータによって、言語全体で無限のデータ構造を扱う ことができます。

共帰は、より馴染みのある再帰と対比することで理解できます。共帰は主に関数型プログラミングで重要ですが、命令型プログラミングを使用して説明することもできます。これは、以下でPythonのジェネレータ機能を使用して行います。これらの例では、ローカル変数が使用され、命令的 (破壊的) に値が割り当てられていますが、純粋関数型プログラミングの共帰ではこれらは必要ありません。純粋関数型プログラミングでは、ローカル変数に割り当てるのではなく、これらの計算された値が不変のシーケンスを形成し、前の値は自己参照によってアクセスされます (シーケンス内の後の値は、計算されるシーケンスの前の値を参照します)。割り当ては、単に命令型のパラダイムでこれを表現し、計算が行われる場所を明示的に指定するため、説明が明確になります。

再帰の典型的な例は、0! := 1およびn! := n × (n - 1)!によって再帰的に定義される階乗の計算です。

特定の入力に対する結果を再帰的に計算するために、再帰関数は、異なる（何らかの意味で「小さい」）入力で自分自身（のコピー）を呼び出し、この呼び出しの結果を使用して結果を構築します。再帰呼び出しは、基本ケースに到達していない限り、同じことを行います。したがって、そのプロセスで呼び出しスタックが作成されます。たとえば、fac(3)を計算するために、これはfac(2)、fac(1)、fac(0)を順番に再帰的に呼び出し（スタックを「巻き上げ」）、その時点で再帰はfac(0) = 1で終了し、次にスタックは逆の順序で巻き戻され、結果は呼び出しスタックに沿って最初の呼び出しフレームfac(3)に戻る途中で計算されます。最初の呼び出しフレームfac(3) は、 fac(2) = 2の結果を使用して、最終結果を3 × 2 = 3 × fac(2) =: fac(3)として計算し、最後にfac(3) = 6 を返します。この例では、関数は単一の値を返します。

このスタックの巻き戻しは、階乗を反復子としてコアカーシブに定義することで説明できます。反復子では、の場合から開始し、この開始値から、上記の再帰定義で「時間矢印」を逆にして と逆に読むように、増加する数値1、2、3... の階乗値を構築します。このように定義されたコアカーシブ アルゴリズムは、すべての階乗のストリームを生成します。これは、ジェネレータとして具体的に実装できます。次の階乗値を計算するには、 nとf (前の階乗値)の両方を追跡する必要があることに注意して、記号的に次のように表すことができます。 ${\displaystyle 1=:0!}$${\displaystyle n!\times (n+1)=:(n+1)!}$

${\displaystyle n,f=(0,1):(n+1,f\times (n+1))}$

またはHaskellでは、

  ( \ ( n , f ) -> ( n + 1 , f * ( n + 1 ))) `反復` ( 0 , 1 )     

は、「 から始めて、各ステップで次の値は として計算されます」という意味です。これは数学的に同等で、再帰定義とほぼ同じですが、 は、階乗値が、最初に減分しながらベースケースまで逆方向に進んだ後に計算されるのではなく、開始ケースから順方向に 構築されていることを強調しています。再帰関数の直接出力には、階乗値が単に含まれているのではなく、各値に対して、シーケンス内のインデックスnの補助データも含まれているため、必要に応じて、それらすべての結果の中から特定の 1 つの結果を選択できます。 ${\displaystyle n,f=0,1}$${\displaystyle n+1,f\times (n+1)}$${\displaystyle +1}$${\displaystyle -1}$${\displaystyle n!}$

これは表示的意味論との関連があり、再帰プログラムの表示はこのようにして再帰的に構築されます。

Pythonでは、再帰階乗関数は次のように定義できます。^[a]

def  factorial ( n :  int )  ->  int : 
"""再帰階乗関数。""" if n == 0 : return 1 else : return n * factorial ( n - 1 )    
       
         
    
             

これを、たとえば5!factorial(5)を計算するために呼び出すことができます。

対応する共再帰ジェネレータは次のように定義できます。

def  factorials (): 
"""共帰的ジェネレータ。""" n 、f = 0 、1 while True : yield f n 、f = n + 1 、f * ( n + 1 )    
        
     
         
                  

これにより、無限の階乗のストリームが順番に生成されます。その有限の部分は次のように生成できます。

 n_factorialsを定義します( n :  int ): 
    k 、 f  =  0 、 1
    ですが 、k  <=  nの場合、 f k 、f = k + 1 、f * ( k + 1 )が生成されます。
         
                  

これを呼び出して、 5までの階乗を生成することができます。

 fが n_factorials ( 5 )の 場合: print ( f )
    

特定の階乗だけに興味がある場合は、最後の値だけを取るか、生成とアクセスを1つの関数に統合することができます。

def  nth_factorial ( n :  int ): 
    k ,  f  =  0 ,  1 
    k < nの場合 : k , f = k + 1 , f * ( k + 1 )を返すf  
                  
     

ここですぐにわかるように、これは実質的には（そこにreturnある のみを に置き換えるだけで）、明示的なループに展開された末尾再帰yieldのアキュムレータ引数テクニックと同等です。したがって、コア再帰の概念は、該当する場合は再帰定義による反復計算プロセスの具体化の説明であると言えます。

同様に、フィボナッチ数列は次のように表すことができます。

${\displaystyle a,b=(0,1):(b,a+b)}$

フィボナッチ数列は2 次再帰関係であるため、共帰関係は 2 つの連続する項を追跡する必要があり、 は1 ステップ前方にシフトし、 は次の項を計算することに対応します。これは次のように実装できます (並列割り当てを使用)。 ${\displaystyle (b,-)}$${\displaystyle (-,a+b)}$

def  fibonacci_sequence (): 
    a ,  b  =  0 ,  1が
    Trueの場合 : a a , b = b , a + bが返される
         
              

Haskellでは、

 map fst ( ( \ ( a , b ) -> ( b , a + b )) ` iterate ` ( 0 , 1 ) )        

深さ優先アプローチによるツリー トラバーサルは、再帰の典型的な例です。同様に、幅優先トラバーサルは、コア再帰によって非常に自然に実装できます。

反復的にツリーをトラバースするには、ルート ノードをデータ構造に配置し、そのデータ構造が空でない間にそのデータ構造を反復処理し、各ステップで最初のノードを削除して、削除したノードの子ノードをそのデータ構造に戻します。データ構造がスタック( LIFO) の場合は深さ優先のトラバースになり、データ構造がキュー( FIFO) の場合は幅優先のトラバースになります。

${\displaystyle {\text{trav}}_{\text{nn}}(t)={\text{aux}}_{\text{nn}}([t])}$

${\displaystyle {\text{aux}}_{\text{df}}([t,\ ...ts])={\text{val}}(t);\ {\text{aux}}_{\text{df}}([\ ...{\text{children}}(t),\ ...ts\ ])}$

${\displaystyle {\text{aux}}_{\text{bf}}([t,\ ...ts])={\text{val}}(t);\ {\text{aux}}_{\text{bf}}([\ ...ts,\ ...{\text{children}}(t)\ ])}$

再帰を使用すると、ツリーの深さ優先のトラバーサルは、ルート ノードの子ノードを順に再帰的にトラバーサルするだけの単純な方法で実装されます。したがって、2 番目の子サブツリーは、最初の子サブツリーが終了するまで処理されません。ルート ノードの値は、最初の子がトラバーサルされる前 (事前順序のトラバーサル)、最初の子が終了して 2 番目の子が終了してから (順序どおり)、または 2 番目の子ノードが終了した後 (後順序) に別々に処理されます (説明を簡単にするために、ツリーはバイナリであると仮定します)。呼び出しスタック (再帰トラバーサル関数呼び出しの) は、前述の明示的な LIFO 構造操作で反復されるスタックに対応します。象徴的に、

${\displaystyle {\text{df}}_{\text{in}}(t)=[\ ...{\text{df}}_{\text{in}}({\text{left}}(t)),\ {\text{val}}(t),\ ...{\text{df}}_{\text{in}}({\text{right}}(t))\ ]}$

${\displaystyle {\text{df}}_{\text{pre}}(t)=[\ {\text{val}}(t),\ ...{\text{df}}_{\text{pre}}({\text{left}}(t)),\ ...{\text{df}}_{\text{pre}}({\text{right}}(t))\ ]}$

${\displaystyle {\text{df}}_{\text{post}}(t)=[\ ...{\text{df}}_{\text{post}}({\text{left}}(t)),\ ...{\text{df}}_{\text{post}}({\text{right}}(t)),\ {\text{val}}(t)\ ]}$

ここでの「再帰」には 2 つの意味があります。1 つ目は、ツリー トラバーサル関数の再帰呼び出しです。より適切なのは、結果の値リストがここでどのように構築されるかに対処することです。再帰的なボトムアップ出力の作成により、右から左へのツリー トラバーサルが行われます。意図した左から右への順序で実際に実行するには、シーケンスを何らかの外部手段で強制する必要があります。または、出力がトップダウン方式、つまりコア再帰的に構築される場合は、シーケンスが自動的に実現されます。 ${\displaystyle {\text{df}}_{xyz}}$

上から下への順序で出力を作成する幅優先のトラバーサルは、コアクシブに、ルートノードから始めてその値を出力し、^[b]幅優先でサブツリーをトラバースすることによっても実装できます。つまり、サブツリーのリスト全体を次のステップに渡します (再帰的アプローチのように単一のサブツリーではありません)。次のステップでは、すべてのルートノードの値を出力し、子サブツリーを渡すなどします。 ^[c]この場合、ジェネレータ関数、つまり出力シーケンス自体がキューとして機能します。上記の階乗の例では、インデックスの補助情報 (ステップ 1 がどのステップであったか、n ) が、実際の出力nに加えてプッシュされました。この場合、残りのサブツリーの補助情報が、実際の出力に加えてプッシュされます。象徴的に、

${\displaystyle v,ts=([],[{\text{FullTree}}]):({\text{RootValues}}(ts),{\text{ChildTrees}}(ts))}$

つまり、各ステップで、このレベルのノードの値のリストを出力し、次のレベルのノードに進みます。このシーケンスからノードの値だけを生成するには、補助的な子ツリーデータを破棄し、リストのリストを平坦化する必要があります（値は最初にレベル（深さ）でグループ化されます。平坦化（グループ化解除）により、平坦な線形リストが生成されます）。これは、上記の仕様と拡張的に同等です。Haskellでは、 ${\displaystyle {\text{aux}}_{\text{bf}}}$

 concatMap fst ( ( \ ( v , ts ) -> ( rootValues ts , childTrees ts )) ` iterate ` ( [] , [ fullTree ]) )             

特に、無限ツリーが与えられた場合、^[d]共起的な幅優先走査は有限ツリーの場合と同様にすべてのノードを走査しますが、再帰的な深さ優先走査は 1 つのブランチを下ってすべてのノードを走査するわけではなく、実際、この例のように (またはインオーダーで) 後順で走査する場合は、葉に到達することがないため、ノードをまったく訪問しません。これは、無限データ構造を処理する場合、再帰ではなく共起の有用性を示しています。無限の分岐係数を持つツリーでは、空間をよりよく探索するために、より注意深いインターレースが必要になるという注意点が 1 つ残っています。dovetailingを参照してください。

Pythonでは、これを次のように実装できます。^[e] 通常のポストオーダー深さ優先探索は次のように定義できます。^[f]

def  df ( node ): 
"""後順序の深さ優先トラバーサル。""" if node is not None : df ( node . left ) df ( node . right ) print ( node . value )    
        
        
        
        

これを呼び出して、df(t)ツリーのノードの値をポストオーダーの深さ優先で印刷することができます。

幅優先共再帰生成器は次のように定義できる: ^[g]

def  bf ( tree ): 
"""幅優先共起ジェネレータ。""" tree_list = [ tree ] while tree_list : new_tree_list = [] for tree in tree_list : if tree is not None : yield tree . value new_tree_list . append ( tree . left ) new_tree_list . append ( tree . right ) tree_list = new_tree_list    
      
     
          
           
                
                 
                
                
          

これを呼び出すと、ツリーのノードの値が幅優先順に出力されます。

 i が bf ( t )の 場合: print ( i )
    

初期データ型は、何らかの型方程式の最小の不動点（同型まで）として定義できます。同型は初期代数によって与えられます。同様に、最終（または終端）データ型は、型方程式の最大の不動点として定義できます。同型は最終余代数によって与えられます。

議論のドメインが集合と全関数のカテゴリである場合、最終データ型には無限の非基礎値が含まれる可能性がありますが、初期型には含まれません。^{[1] [2]}一方、議論のドメインが完全な半順序と連続関数のカテゴリである場合（これはHaskellプログラミング言語にほぼ相当します）、最終型は初期型と一致し、対応する最終コアルジェブラと初期代数は同型を形成します。^[3]

共帰は、範囲（共ドメイン）が最終データ型である関数を再帰的に定義する手法であり、通常の再帰がドメインが初期データ型である関数を再帰的に定義する方法と双対的です。 ^[4]

以下の説明では、Haskell で共起を区別するいくつかの例を示します。大まかに言えば、これらの定義を集合のカテゴリに移植しても、共起的になります。この非公式な使用法は、Haskell に関する既存の教科書と一致しています。^[5]この記事で使用されている例は、共起を定義し、それが何であるかを説明する試みよりも前のものです。

codataのプリミティブ共起の規則は、data のプリミティブ再帰の規則と双対です。コンストラクタ (より前にどこかで呼び出されているため、既製のデータを受け取り、その構成要素であるサブパーツ、つまり「フィールド」を取得) のパターン マッチングによって引数を下降する代わりに、その「デストラクタ」(または「オブザーバ」。 より後にどこかで呼び出されるため、実際にはコンストラクタを呼び出し、後で観察される結果の別のビットを作成しています) を埋め込むことによって結果を上昇します。したがって、共起は(潜在的に無限の) codata を作成し、通常の再帰は (必然的に有限の) data を分析します。通常の再帰は、終了しない可能性があるため、codata には適用できない場合があります。逆に、結果の型がデータの場合、データは有限でなければならないため、共起は厳密には必要ありません。

「Coqでのストリームプログラミング：ケーススタディ：エラトステネスの篩」^[6]では、

hd (濃度a s ) = a tl (濃度a s ) = s                    
     

( sieve p s ) = if div p ( hd s ) then sieve p ( tl s ) else conc ( hd s ) ( sieve p ( tl s ))             
                     

hd (素数s ) = ( hd s ) tl (素数s ) =素数(ふるい( hd s ) ( tl s ))               
         

ここで素数は「ストリームに素数演算を適用することで得られる（Enu 2）」。上記の表記法に従うと、素数のシーケンス（先頭に捨て値の0が付く）と数値ストリームが段階的にふるい分けられ、次のように表すことができます。

${\displaystyle p,s=(0,[2..]):(hd(s),sieve(hd(s),tl(s)))}$

またはHaskellでは、

( \ ( p , s @ ( h : t )) -> ( h , sieve h t )) `反復` ( 0 , [ 2 .. ])         

著者らは、 の定義が常に生産的sieveであるとは限らず、たとえば を初期ストリームとして呼び出した場合などにスタックする可能性があることを説明しています。 [5,10..]

これは Haskell での別の例です。次の定義は、線形時間で フィボナッチ数のリストを生成します。

fibs = 0 : 1 : zipWith ( + ) fibs (末尾のfibs )          

この無限リストは遅延評価に依存しています。要素は必要に応じて計算され、有限のプレフィックスのみがメモリ内で明示的に表現されます。この機能により、codata の一部に対するアルゴリズムを終了できます。このようなテクニックは Haskell プログラミングの重要な部分です。

これはPythonでも同様に実行できます: ^[7]

>>> itertoolsから tee 、chain 、islice をインポートします>>> def fibonacci (): ... def deferred_output (): ... yield from output ... ... result 、c1 、c2 = tee ( deferred_output (), 3 ) ... paired = ( x + y for x 、y in zip ( c1 、islice ( c2、1 、None ) )) ... output = chain ([ 0、1 ] 、paired ) ... return result >>> print ( * islice ( fibonacci ( ) , 20 ), sep = '、' ) 0、1、1、2、3、5、8、13、21、34、55、89、144、233、377、610、987、1597、2584、 4181    
 
     
         

         
                
        
     
  

の定義はzipWithインライン化することができ、次のようになります。

fibs = 0 : 1 : next fibs where next ( a : t @ ( b : _ )) = ( a + b ) : next t       
  
         

この例では、自己参照データ構造を採用しています。通常の再帰では自己参照関数を使用しますが、自己参照データは扱えません。ただし、これはフィボナッチの例にとって重要ではありません。次のように書き直すことができます。

fibs = fibgen ( 0 , 1 ) fibgen ( x , y ) = x : fibgen ( y , x + y )   
      

これは、結果を構築するために自己参照関数のみを使用します。厳密なリスト コンストラクターで使用すると、暴走再帰の例になりますが、厳密でないリスト コンストラクターを使用すると、この保護された再帰によって、無期限に定義されたリストが徐々に生成されます。

共起は必ずしも無限のオブジェクトを生成するわけではありません。共起キュー^[8]はこの現象の特に良い例です。次の定義は、トップダウン方式で二分木の幅優先走査を線形時間で生成します（すでに上記の平坦化が組み込まれています）。

データツリーa b =リーフa |ブランチb (ツリーa b ) (ツリーa b )      
                      

bftrav :: Tree a b -> [ Tree a b ] bftrav tree = tree : tsここでts = gen 1 ( tree : ts )        
     
  
        

  gen 0 p = [] gen len ( Leaf _ : p ) = gen ( len - 1 ) p gen len ( Branch _ l r : p ) = l : r : gen ( len + 1 ) p -- ----読み取り---- ----先行書き込み---                                          
                         
                 
  

-- bfvalues ツリー = [v | (ブランチ v _ _) <- bftrav ツリー]

この定義はツリーを受け取り、そのサブツリー (ノードとリーフ) のリストを生成します。このリストは、入力キューと結果 (リストに沿って入力バックポインター より先にgen len p出力ノッチ を生成する) の両方の目的を果たします。これは、初期ツリーが有限である場合にのみ有限です。キューの長さは、終了を確実にするために明示的に追跡する必要があります。この定義が無限ツリーにのみ適用される場合は、これを安全に省略できます。 lenp

この Haskell コードは自己参照データ構造を使用していますが、本質的には遅延評価に依存していません。これは、遅延言語ではない Prolog などに簡単に変換できます。重要なことは、トップダウン方式でリスト (キューとして使用) を構築する機能です。そのために、Prolog にはcons (つまり、オープンエンド リスト) を法とする末尾再帰があります。これは、可変末尾センチネル ポインターを持つリンク リストを使用して、Scheme、C などでエミュレートすることもできます。

bftrav (  Tree 、  [ Tree | TS ])  :-  bfgen (  1 、 [ Tree | TS ]、   TS )。

bfgen (  0 ,  _ ,    [])  :-  !.   % キューに 0 エントリ -- 停止してリストを閉じます
bfgen (  N ,  [ leaf ( _ )       | P ],    TS       )  :-  N2は N - 1です 、bfgen ( N2 , P , TS )。bfgen ( N , [ branch ( _ , L , R )| P ], [ L , R | TS ]) :- N2はN + 1です、bfgen ( N2 , P , TS )。%% ----read----- --write--      
               

別の特定の例は、幅優先ラベリングの問題に対する解決策を示しています。^[9]この関数は、label幅優先方式でバイナリツリーのすべてのノードを訪問し、各ラベルを整数に置き換えます。後続の各整数は、前の整数より1大きくなります。このソリューションは自己参照データ構造を採用しており、バイナリツリーは有限または無限にすることができます。

ラベル:: Tree a b -> Tree Int Intラベルt = tn where ( tn , ns ) = go t ( 1 : ns )         
   
  
       

  go :: Tree a b -> [ Int ] -> ( Tree Int Int , [ Int ]) go ( Leaf _ ) ( i : a ) = ( Leaf i , i + 1 : a ) go ( Branch _ l r ) ( i : a ) = ( Branch i ln rn , i + 1 : c )ただし( ln , b ) = go l a ( rn , c ) = go r b            
                       
             
       
            
            

あるいは比較のためにPrologでは、

ラベル(  Tree ,  Tn )  :- ラベル(  Tree ,  [ 1 | Ns ],    Tn ,  Ns )。

ラベル(  leaf ( _ ),       [ I | A ],    leaf (   I ),       [ I + 1 | A ]).
ラベル(  branch ( _ , L , R ), [ I | A ],    branch ( I , Ln , Rn ), [ I + 1 | C ])  :-
  ラベル(  L ,  A ,    Ln ,  B ),  
  ラベル(  R ,  B ,    Rn ,  C ).

アポモルフィズム(アナモルフィズム、unfoldなど)は、パラモルフィズム(カタモルフィズム、 foldなど) が再帰の形式であるのと同じように、コアカージョンの形式です。

Coq証明アシスタントは、CoFixpoint コマンドを使用して共帰と共帰をサポートします 。

循環プログラミングとも呼ばれる共帰は、少なくとも (Bird 1984) にまで遡り、John HughesとPhilip Wadler の功績を称えています。より一般的な形式は (Allison 1989) で開発されました。当初の動機には、より効率的なアルゴリズム (複数のパスを必要とする代わりに、場合によっては単一のデータ パスを可能にする) を作成することと、双方向リンク リストやキューなどの古典的なデータ構造を関数型言語で実装することが含まれていました。

• バイシミュレーション
• 共誘導
• 再帰
• アナモルフィズム