異形作用

関数型プログラミングにおいて、カタモルフィズムの概念(古代ギリシャ語のκατά「下向き」とμορφή「形、形状」に由来)は、初期代数から他の代数へ の一意の準同型性を表します。

カタモルフィズムは、リストのフォールドを任意の代数データ型に一般化したものを提供します。これは、初期代数として記述できます。双対概念は、展開を一般化するアナモルフィズムです。ヒュロモルフィズムは、アナモルフィズムとそれに続くカタモルフィズムの組み合わせです。

何らかのカテゴリの何らかの自己関数子からそれ自身への初期 -代数を考えてみましょう。から への射があります。 これは初期なので、 が別の-代数、つまりからへの射である場合はいつでも、から への一意の準同型が存在することがわかります。 -代数のカテゴリの定義により、これはからへの射に対応し、慣例的に とも表記され、 となります。 -代数のコンテキストでは、初期オブジェクトからの一意に指定された射は で表され、したがって次の関係によって特徴付けられます。 ${\displaystyle F}$ ${\displaystyle (A,in)}$ ${\displaystyle F}$${\displaystyle 中}$${\displaystyle FA}$${\displaystyle A}$${\displaystyle (X,f)}$${\displaystyle F}$${\displaystyle f}$${\displaystyle FX}$${\displaystyle X}$ ${\displaystyle h}$${\displaystyle (A,in)}$${\displaystyle (X,f)}$${\displaystyle F}$${\displaystyle h}$${\displaystyle A}$${\displaystyle X}$${\displaystyle h}$${\displaystyle h\circ in=f\circ Fh}$${\displaystyle F}$${\displaystyle \mathrm {cata} \ f}$

• ${\displaystyle h=\mathrm {cata} \ f}$
• ${\displaystyle h\circ in=f\circ Fh}$

文献に見られる別の表記法は です。使用されている開き括弧はバナナ括弧として知られており、それにちなんでカタモルフィズムはバナナと呼ばれることもあります。これはErik Meijerら^[1]で言及されています。プログラミングの文脈でカタモルフィズムの概念を紹介した最初の出版物の 1 つは、Erik Meijerら^[1]による論文「バナナ、レンズ、エンベロープ、有刺鉄線を使用した関数型プログラミング」であり、これはSquiggol形式の文脈でした。一般的なカテゴリカル定義は Grant Malcolm によって与えられました。 ^{[2] [3]}${\displaystyle (\!|f|\!)}$

一連の例を示し、次にHaskellプログラミング言語でのカタモルフィズムに対するよりグローバルなアプローチを示します。

Maybe以下の Haskell コードで定義されている 関数を考えてみましょう。

データMaybe a = Nothing | Just a -- Maybe タイプ        

class Functor f where -- 関数のクラスfmap :: ( a -> b ) -> ( f a -> f b ) -- 関数の射に対する作用    
                

インスタンスFunctor Maybeで、 Maybe を functor に変換します。fmap g Nothing = Nothing fmap g ( Just x ) = Just ( g x )    
        
           

Maybe-Algebraの初期オブジェクトは、自然数型のすべてのオブジェクトの集合Natと、ini以下に定義される射である: ^{[4] [5]}

data Nat = Zero | Succ Nat -- 自然数型       

ini :: Maybe Nat -> Nat -- Maybe 代数の初期オブジェクト (表記法を少し乱用) ini Nothing = Zero ini ( Just n ) = Succ n      
   
     

マップcataは次のように定義されます: ^[5]

cata :: ( Maybe b -> b ) -> ( Nat -> b ) cata g Zero = g ( fmap ( cata g ) Nothing ) -- 注意: fmap (cata g) Nothing = g Nothing かつ Zero = ini(Nothing) cata g ( Succ n ) = g ( fmap ( cata g ) ( Just n )) -- 注意: fmap (cata g) (Just n) = Just (cata gn) かつ Succ n = ini(Just n)         
        
            

例として、次の射を考えてみましょう。

g :: Maybe String -> String g Nothing = "go!" g ( Just str ) = "wait..." ++ str      
   
      

次に、cata g ((Succ. Succ . Succ) Zero)「待って...待って...待って...行く!」と評価します。

固定型の場合、次のように定義される a関数を考えます。MaybeProd a

data MaybeProd a b = Nothing | Just ( a , b ) -- (a,b) は a と b の積型です          

class Functor f where -- 関数のクラスfmap :: ( a -> b ) -> ( f a -> f b ) -- 関数の射に対する作用    
                

instance Functor ( MaybeProd a ) where -- MaybeProd a を関数に変換します。関数性は 2 番目の型にのみ存在します。 variable fmap g Nothing = Nothing fmap g ( Just ( x , y )) = Just ( x , g y )     
        
            

の初期代数は、MaybeProd a型を持つ要素のリストaと、以下に定義される射によって与えられるini: ^[6]

データリストa = EmptyList | Cons a (リストa )         

ini :: MaybeProd a ( List a ) -> List a -- MaybeProd a の初期代数ini Nothing = EmptyList ini ( Just ( n , l )) = Cons n l         
   
      

マップcataは次のように定義できます。

cata :: ( MaybeProd a b -> b ) -> ( List a -> b ) cata g EmptyList = g ( fmap ( cata g ) Nothing ) -- 注: ini Nothing = EmptyList cata g ( Cons s l ) = g ( fmap ( cata g ) ( Just ( s , l ))) -- 注: Cons sl = ini (Just (s,l))           
        
             

また、 であることにも注意してくださいcata g (Cons s l) = g (Just (s, cata g l))。例として、次の射を考えてみましょう。

g :: MaybeProd Int Int -> Int g Nothing = 3 g ( Just ( x , y )) = x * y      
   
    

cata g (Cons 10 EmptyList)は 30 と評価されます。これは を展開するとわかります cata g (Cons 10 EmptyList)=g (Just (10,cata g EmptyList)) = 10* cata g EmptyList=10* g Nothing=10*3。

同じように表示すれば、 cata g (Cons 10 (Cons 100 (Cons 1000 EmptyList)))10*(100*(1000*3))=3.000.000 と評価されます。

この写像はリストの右折り畳み（Fold（高階関数）を参照）と cata密接に関係しているfoldrList。lift

持ち上げる:: ( a -> b -> b ) -> b -> ( MaybeProd a b -> b )持ち上げるg b0何もしない= b0持ち上げるg b0 (ただ( x , y )) = g x y              
     
        

リストの cata右側の折り返しに関連します:foldrList

foldrList :: ( a -> b -> b ) -> b -> List a -> b foldrList fun b0 = cata ( lift fun b0 )            
       

の定義はcata、foldrList左折りではなく右折りであることを意味します。例: はfoldrList (+) 1 (Cons 10 ( Cons 100 ( Cons 1000 EmptyList)))1111 と評価され、foldrList (*) 3 (Cons 10 ( Cons 100 ( Cons 1000 EmptyList)))3.000.000 と評価されます。

固定型 について、の各項のコピーと のすべてのペア(型 の 2 つのインスタンスの積型の項) を含む型にa型をマッピングする関数を考えます。代数は、項または 2 つの項に作用するへの関数で構成されます。このペアのマージは、 それぞれ型の 2 つの関数としてエンコードできます。babbbaba -> bb -> b -> b

type TreeAlgebra a b = ( a -> b , b -> b -> b ) -- 「2 つのケース」関数は (f, g) としてエンコードされます。data Tree a = Leaf a | Branch ( Tree a ) ( Tree a ) -- これは初期代数になります。foldTree :: TreeAlgebra a b -> ( Tree a -> b ) -- カタモルフィズムは (Tree a) から b にマップされます。foldTree ( f , g ) ( Leaf x ) = f x foldTree ( f , g ) ( Branch left right ) = g ( foldTree ( f , g ) left ) ( foldTree ( f , g ) right )             
 
            
 
          
                  
               

treeDepth :: TreeAlgebra a Integer -- 数値の f-代数。任意の入力タイプで機能します。treeDepth = ( const 1 , \ i j -> 1 + max i j ) treeSum :: ( Num a ) => TreeAlgebra a a -- 数値の f-代数。任意の数値タイプで機能します。treeSum = ( id , ( + ))     
           
 
        
   

初期代数のより深いカテゴリ理論的研究により、関数をそれ自身の初期代数に適用して得られる F 代数は、それと同型であることが明らかになりました。

強い型システムにより、関数の初期代数をfその不動点a = faとして抽象的に指定できます。再帰的に定義されたカタモルフィズムは、ケース分析 (上記のさまざまな例のように) が fmap によってカプセル化されている 1 行でコーディングできるようになりました。後者のドメインは のイメージ内のオブジェクトであるため、カタモルフィズムの評価はとfの間を行ったり来たりします。 af a

型代数f a = f a -> a -- 汎用f代数         

newtype Fix f = Iso { invIso :: f ( Fix f ) } -- 関数 f の初期代数を与える            

cata :: Functor f => Algebra f a -> ( Fix f -> a ) -- Fix f から a への異相写像cata alg = alg . fmap ( cata alg ) . invIso -- invIso と alg は反対方向にマップされることに注意してください             
          

ここで、再び最初の例ですが、今度は Maybe 関数を Fix に渡します。Maybe 関数を繰り返し適用すると型のチェーンが生成されますが、これは不動点定理の同型性によって結合できます。Maybezeroから生じる という項を導入しNothing、 を繰り返し適用した後継関数を特定しますJust。このようにして自然数が生成されます。

type Nat = Fix Maybe zero :: Nat zero = Iso Nothing -- すべての「Maybe a」には Nothing という項があり、Iso はそれを後続項にマッピングします:: Nat -> Nat successor = Iso . Just -- Just は a を「Maybe a」にマッピングし、Iso は新しい項にマッピングし直します    
  
    
    
     

pleaseWait :: Algebra Maybe String -- 再び、上記の愚かな f 代数の例pleaseWait ( Just string ) = "wait.. " ++ string pleaseWait Nothing = "go!"     
      
   

再び、以下は「wait.. wait.. wait.. wait.. go!」と評価されます。cata pleaseWait (successor.successor.successor.successor $ zero)

ここで再びツリーの例を示します。このためには、ツリー コンテナー データ型を提供して、設定できるようにする必要がありますfmap(これは標準のプレリュードの一部であるため、ファンクタに対して行う必要はありませんでしたMaybe)。

データTcon a b = TconL a | TconR b bインスタンスFunctor ( Tcon a )ここで、fmap f ( TconL x ) = TconL x fmap f ( TconR y z ) = TconR ( f y ) ( f z )          
    
            
              

type Tree a = Fix ( Tcon a ) -- 初期代数end :: a -> Tree a end = Iso . TconL meet :: Tree a -> Tree a -> Tree a meet l r = Iso $ TconR l r       
     
    
         
        

treeDepth :: Algebra ( Tcon a ) Integer -- 再び、treeDepth f-代数の例treeDepth ( TconL x ) = 1 treeDepth ( TconR y z ) = 1 + max y z      
      
         

次の結果は 4 になります。cata treeDepth $ meet (end "X") (meet (meet (end "YXX") (end "YXY")) (end "YY"))

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

• HaskellWiki の異形性
• エドワード・クメットの「カタモルフィズム」
• F#におけるカタモルフィズム(パート 1、2、3、4、5、6、7) by Brian McNamara
• Haskell における異形作用