アナモルフィズム

コンピュータ プログラミングにおいて、アナモルフィズムとは、関数を前の結果に繰り返し適用することでシーケンスを生成する関数です。まず、ある値 A に関数 f を適用して B を取得します。次に、f を B に適用して C を取得し、これを終了条件に達するまで繰り返します。アナモルフィズムは、A、B、C などのリストを生成する関数です。アナモルフィズムは、初期値をシーケンスに展開するものと考えることができます。

上記の素人向けの説明は、圏論でより正式に述べることができます。共帰納的型のアナモルフィズムは、自己関数子の最終的な余代数へのその唯一の射への余代数への割り当てを表します。これらのオブジェクトは、関数型プログラミングで展開として使用されます。

アナモルフィズムのカテゴリカルな双対（つまり反対）はカタモルフィズムです。

関数型プログラミングにおいて、アナモルフィズムは、共帰的リスト上の展開の概念を一般化したものです。正式には、アナモルフィズムは、特定のタイプの結果を共帰的に構築できる汎用関数であり、構築の次の単一のステップを決定する関数によってパラメーター化されます。

問題のデータ型は、関数Fの最大不動点ν X . FXとして定義されます。最終コ代数の普遍的性質により、他の任意のF -コ代数a : A → FAに対して、一意のコ代数射A → ν X . FX が存在します。したがって、 A上のコ代数構造aを指定することにより、型Aからコインダクティブデータ型への関数を定義できます。

例として、潜在的に無限のリスト（固定型valueの要素を持つ）の型は、固定点[value] = ν X . value × X + 1として与えられます。つまり、リストは値とさらなるリストから構成されるか、空です。（疑似）Haskell定義は次のようになります。

データ[値] = (値: [値]) | []     

これは関数の不動点でありF value、次のようになります。

データたぶんa =ただa |何もないデータF値x =たぶん(値, x )       
       

型が[value]と同型であり F value [value]、したがって[value]不動点であることは簡単に確認できます。(また、Haskell では、関数の最小不動点と最大不動点は一致するため、帰納的リストは、余帰納的、潜在的に無限のリストと同じであることに注意してください。)

リストのアナモルフィズム(当時はunfoldと呼ばれていました)は、状態値から (潜在的に無限の) リストを構築します。通常、 unfold は状態値と、値と新しい状態のペアを生成する関数、またはリストの終わりを示すシングルトンを受け取ります。アナモルフィズムは最初のシードから開始し、リストが続くか終了するかを計算し、空でないリストの場合は、計算された値をアナモルフィズムへの再帰呼び出しの先頭に追加します。 xf

リストの展開、またはアナモルフィズムの Haskell 定義は、 と呼ばれana、次のようになります。

ana :: ( state -> Maybe ( value , state )) -> state -> [ value ] ana f stateOld = case f stateOld of Nothing -> [] Just ( value , stateNew ) -> value : ana f stateNew          
       
                             
                    

ana を使用して、カウントダウンなどの 非常に一般的な関数を実装できるようになりました。

f :: Int -> Maybe ( Int , Int ) f current = let oneSmaller = current - 1 in if oneSmaller < 0 then Nothing else Just ( oneSmaller , oneSmaller )      
        
                  
                    
                      

この関数は整数を減算し、それが負になるまで同時にそれを出力します。負になった時点でリストの終わりがマークされます。同様に、ana f 3はリストを計算します[2,1,0]。

アナモルフィズムは、一般的なパターンに従って、リストの anaの 2 番目のバージョンを一般化して、任意の再帰型に対して定義できます。

例えば、ツリーデータ構造の展開

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

は次の通り

 ana :: ( b -> Either a ( b , a , b )) -> b -> Tree a ana unspool x = case unspool x of Left a -> Leaf a Right ( l , x , r ) -> Branch ( ana unspool l ) x ( ana unspool r )             
        
                                
                               

再帰型とそのアナモルフィズムの関係をよりよく理解するために、Treeと はList次のように定義できることに注目してください。

 newtype List a = List { unCons :: Maybe ( a , List a )}          

 newtype Tree a = Tree { unNode :: Either a ( Tree a , a , Tree a ))}             

との類似性は、そのタイプの ana名前を変更することによって現れます。b

 newtype List a = List { unCons :: Maybe ( a , List a )} anaList :: ( list_a -> Maybe ( a , list_a )) -> ( list_a -> List a )          
                        

 newtype Tree a = Tree { unNode :: Either a ( Tree a , a , Tree a ))} anaTree :: ( tree_a -> Either a ( tree_a , a , tree_a )) -> ( tree_a -> Tree a )             
                          

これらの定義により、 のコンストラクタへの引数は の最初の引数の戻り値の型と同じ型になりana、 型の再帰的な言及は に置き換えられますb。

プログラミングの文脈でアナモルフィズムの概念を紹介した最初の出版物の1つは、Erik MeijerらによるSquiggolプログラミング言語の文脈での論文「バナナ、レンズ、エンベロープ、有刺鉄線を使った関数型プログラミング」 [ ^1]でした。

zipやのような関数iterateはアナモルフィズムの例です。 zipはリストのペア、たとえば ['a','b','c'] と [1,2,3] を受け取り、ペアのリスト [('a',1),('b',2),('c',3)] を返します。Iterateは物 x と、そのような物からそのような物への関数 f を受け取り、f を繰り返し適用して得られる無限リスト、つまりリスト [x, (fx), (f (fx)), (f (f (fx))), ...] を返します。

 zip ( a : as ) ( b : bs ) = if ( as == [] ) || ( bs == [] ) -- || は「または」を意味し、then [( a , b )] else ( a , b ) : ( zip as bs ) iterate f x = x : ( iterate f ( f x ))           
                       
                          
 
        

anaこれを証明するには、単純な再帰ルーチンを使用して、 汎用の unfold を使用して両方を実装します。

 zip2 = ana unsp finただしfin ( as 、bs ) = ( as == [] ) || ( bs == [] ) unsp (( a : as )、( b : bs )) = (( a 、b )、( as 、bs ))    
    
           
        

 iterate2 f = ana ( \ a -> ( a 、f a )) ( \ x -> False )      

Haskell のような言語では、上記の定義からわかるように、 抽象関数fold、unfold、でさえも、単に定義された用語です。ana

圏論では、アナモルフィズムはカタモルフィズムの圏的双対です(そしてカタモルフィズムはアナモルフィズムの圏的双対です)。

これは次のことを意味します。 ( A , fin )が、何らかのカテゴリの何らかの自己関数子Fの、それ自体への最終的な F余代数であると仮定します。したがって、 fin はAからFAへの射であり、最終的であると想定されているため、 ( X、f ) が別のF余代数（ XからFXへの射f ）である場合はいつでも、 ( X、f )から( A、fin ) への一意の準同型h 、つまりfin . h = Fh . fとなるようなXからAへの射hが存在することがわかります。次に、そのようなfごとに、一意に指定された射h をana fで表します。

言い換えると、上記のように F、A、およびfin が固定されている場合、次の定義関係が成り立ちます。

• ${\displaystyle h=\mathrm {アナ} \ f}$
• ${\displaystyle \mathrm {fin} \circ h=Fh\circ f}$

文献で見られるana fの表記は です。使用されるブラケットはレンズ ブラケットと呼ばれ、これにちなんでアナモルフィズムはレンズと呼ばれることもあります。 ${\displaystyle [\!(f)\!]}$

• モルフィズム
• F-代数の射影
  • 初期代数から代数へ:異形作用
  • 異形化現象の後に起こる異形化現象：形質転換現象
  • 異形化の概念の拡張：異形化
  • アナモルフィズムの考え方の拡張：アポモルフィズム

• Haskell におけるアナモルフィズム