形態論（コンピュータサイエンス）

コンピュータサイエンス、特に関数型プログラミングにおいて、ハイロモルフィズムは再帰関数であり、アナモルフィズム（最初に結果セットを構築する、「展開」とも呼ばれる）とそれに続くカタモルフィズム（次にこれらの結果を最終的な戻り値に折りたたむ）の組み合わせに対応する。これら 2 つの再帰計算を 1 つの再帰パターンに融合することで、中間データ構造の構築を回避できる。これは、プログラム最適化戦略である森林伐採の一例である。関連するタイプの関数にメタモルフィズムがあり、これはカタモルフィズムの後にアナモルフィズムが続くものである。

形質転換は、アナモルフィック部分とカタモルフィック部分という別々の部分によって定義できます。 ${\displaystyle h:A\rightarrow C}$

アナモルフィック部分は、繰り返し適用 ( 「展開」 )によって要素のリストを定義する単項関数と、終了条件を提供する 述語によって定義できます。${\displaystyle g:A\rightarrow B\times A}$${\displaystyle B}$ ${\displaystyle p:A\rightarrow {\text{ブール値}}}$

カタモルフィック部分は、フォールドの初期値とフォールドを実行するために使用される バイナリ演算子の組み合わせとして定義できます。${\displaystyle c\in C}$ ${\displaystyle \oplus :B\times C\rightarrow C}$

したがって、形態学的

${\displaystyle h\,a={\begin{cases}c&{\mbox{if }}p\,a\\b\oplus h\,a'\,\,\,where\,(b,a')=g\,a&{\mbox{otherwise}}\end{cases}}}$

定義される可能性があります ( &の適切な定義を前提としています)。 ${\displaystyle p}$${\displaystyle g}$

上記の形質形態​​論の省略表記は です。 ${\displaystyle h=[\![(c,\oplus ),(g,p)]\!]}$

リストは、線形計算プロセスを自然に反映するため、一般的なデータ構造です。これらのプロセスは、繰り返される (反復的な) 関数呼び出しで発生します。したがって、このリストを単一の結果に縮小する前に、中間結果の一時的なリストを生成する必要がある場合があります。

よく見られる形態論の一例は、標準階乗関数です。

階乗::整数->整数の階乗n | n == 0 = 1 | n > 0 = n *階乗( n - 1 )    
 
       
            

前の例では (純粋に関数的なプログラミング言語であるHaskellで記述)、この関数を任意の有効な入力に適用すると、リストと同型の線形呼び出しツリーが生成されることがわかります。たとえば、n = 5 の場合、次のものが生成されます。

5の階乗 = 5 * (4の階乗) = 120
4の階乗 = 4 * (3の階乗) = 24
3 の階乗 = 3 * (2 の階乗) = 6
2の階乗 = 2 * (1の階乗) = 2
階乗 1 = 1 * (階乗 0) = 1
階乗 0 = 1

この例では、プロセスのアナモルフィックな部分は、リスト と同型の呼び出しツリーの生成です[1, 1, 2, 3, 4, 5]。カタモルフィズムは、このリストの要素の積の計算です。したがって、上記の表記法では、階乗関数は と記述できます(ただし、 ) 。 ${\displaystyle {\text{factorial}}=[\![(1,\times ),(g,p)]\!]}$${\displaystyle g\ n=(n,n-1)}$${\displaystyle p\ n=(n=0)}$

ただし、「形態論」という用語は、リストの同型性に作用する関数にのみ適用されるわけではありません。たとえば、形態論は、非線形呼び出しツリーを生成し、それを折りたたむことによって定義することもできます。このような関数の例としては、フィボナッチ数列のn^番目 の項を生成する関数があります。

 フィボナッチ::整数- >整数フィボナッチ| n == 0 = 0 | n == 1 = 1 | n > 1 =フィボナッチ( n - 2 ) +フィボナッチ( n - 1 )    
  
        
        
                

この関数を任意の有効な入力に適用すると、非線形の呼び出しツリーが生成されます。右側の例では、fibonacci関数を入力に適用して生成された呼び出しツリーです4。

ここで、アナモルフィズムは、リーフ ノード を持つツリーと同型のコール ツリーを生成することで0, 1, 1, 0, 1あり、カタモルフィズムは、これらのリーフ ノードの合計を生成することです。

• モルフィズム
• F-代数の射影
  • 初期代数から代数へ:異形作用
  • 余代数から最終余代数へ:アナモルフィズム
  • 異形化の概念の拡張：異形化
  • アナモルフィズムの考え方の拡張：アポモルフィズム

• Erik Meijer、Maarten Fokkinga、Ross Paterson (1991)。「バナナ、レンズ、エンベロープ、有刺鉄線を使った関数型プログラミング」(PDF)。pp. 4、5。

• Haskell における形態論
• Haskell におけるさらなる形態論