17

http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdfの 3 ページから:

カタモルフィズムが合成下で閉じているというのは一般に真実ではない

カタモルフィズムはどのような条件下でカタモルフィズムに合成されますか? より具体的には（ステートメントを正しく理解していると仮定して）：

それぞれに 2 つの基底関手FandGと フォールドがあるとします: foldF :: (F a -> a) -> (μF -> a)and foldG :: (G a -> a) -> (μG -> a).

ここで、2 つの代数a :: F μG -> μGとがあるとしb :: G X -> Xます。

組成(foldG b) . (foldF a) :: μF -> Xがカタモルフィズムになるのはいつですか?

編集: dblhelix の拡張された回答に基づいて、推測があります。それは、自然な変換outG . a :: F μG -> G μGのコンポーネントである必要があります。これが正しいかどうかはわかりません。(編集 2: colah が指摘するように、これで十分ですが、必須ではありません。)μGη :: F a -> G a

編集 3: Haskell-Cafe の Wren Thornton は次のように付け加えています。適切に関連するカテゴリの自然な変換; したがって、適切に関連するカテゴリが常に存在するかどうか、および「適切に関連する」が何を意味するかを形式化できるかどうかに問題を委ねます。」

4

4 に答える 4

5

構成はいつですか (fold2 g) . (fold1 f) :: μF1 -> A カタモルフィズム?

のようなF1代数が存在するとき。h :: F1 A -> Afold1 h = fold2 g . fold1 f

カタモルフィズムが合成の下で一般に閉じていないことを確認するには、型レベルの不動点、代数、およびカタモルフィズムの次の一般的な定義を検討してください。

newtype Fix f = In {out :: f (Fix f)}

type Algebra f a = f a -> a

cata :: Functor f => Algebra f a -> Fix f -> a
cata phi = phi . fmap (cata phi) . out

カタモルフィズムを構成するためには、

algcomp ::  Algebra f (Fix g) -> Algebra g a -> Algebra f a

この関数を書いてみてください。引数として 2 つの関数 (それぞれ と の型) と type の値を取り、 typef (Fix g) -> Fix gの値を生成する必要があります。どうやってそれをしますか？type の値を生成するには、type の関数を適用することが唯一の望みですが、それでは行き詰まります: type の値を type の値に変換する手段がありませんよね?g a -> af aaag a -> af ag a

これがあなたの目的に役立つかどうかはわかりませんが、カタモルフィズムを構成できる条件の例は、2 番目のカタの結果から 2 番目のファンクターの不動点への射がある場合です。

algcomp' :: (Functor f, Functor g) =>
            (a -> Fix g) -> Algebra f (Fix g) -> Algebra g a -> Algebra f a
algcomp' h phi phi' = cata phi' . phi . fmap h
于 2012-08-24T10:48:12.897 に答える
4

（免責事項：これは私の専門分野外です。私は正しいと思います（さまざまなポイントで警告が提供されています）が、...自分で確認してください。）

カタモルフィズムは、データ型のコンストラクターを他の関数に置き換える関数と考えることができます。

（この例では、次のデータ型を使用します。

data [a] = [] | a : [a]

data BinTree a = Leaf a | Branch (BinTree a) (BinTree a)

data Nat = Zero | Succ Nat

）。

例えば：

length :: [a] -> Nat
length = catamorphism
     []   -> 0
     (_:) -> (1+)

（残念ながら、catamorphism {..}Haskellでは構文が利用できません（Polaで似たようなものを見ました）。私はそれに対して準引用符を書くつもりでした。）

それで、何length [1,2,3]ですか？

length [1,2,3]
length (1 : 2 : 3 : [])
length (1:  2:  3:  [])
        1+ (1+ (1+ (0 )))
        3

とは言うものの、後で明らかになる理由のために、それを自明に同等であると定義する方が良いです：

length :: [a] -> Nat
length = catamorphism
     []   -> Zero
     (_:) -> Succ

さらにいくつかのカタモルフィズムの例を考えてみましょう。

map :: (a -> b) -> [a] -> b
map f = catamorphism
     []   -> []
     (a:) -> (f a :)

binTreeDepth :: Tree a -> Nat
binTreeDepth = catamorphism
     Leaf _ -> 0
     Branch -> \a b -> 1 + max a b

binTreeRightDepth :: Tree a -> Nat
binTreeRightDepth = catamorphism
     Leaf _ -> 0
     Branch -> \a b -> 1 + b

binTreeLeaves :: Tree a -> Nat
binTreeLeaves = catamorphism
     Leaf _ ->  1
     Branch -> (+)

double :: Nat -> Nat
double = catamorphism
     Succ -> Succ . Succ
     Zero -> Zero

これらの多くは、新しいカタモルフィズムを形成するためにうまく構成することができます。例えば：

double . length . map f = catamorphism
     []   -> Zero
     (a:) -> Succ . Succ

double . binTreeRightDepth = catamorphism
     Leaf a -> Zero
     Branch -> \a b -> Succ (Succ b)

double . binTreeDepth動作しますが、ある意味ではほとんど奇跡です。

double . binTreeDepth = catamorphism
     Leaf a -> Zero
     Branch -> \a b -> Succ (Succ (max a b))

doubleこれは、分散するためにのみ機能しmaxます...これはまったくの偶然です。（同じことが当てはまりますdouble . binTreeLeaves。）ダブリングではうまく機能しないものに置き換えた場合max...まあ、新しい友達を定義しましょう（他の友達とうまくいきません）。double分散しない二項演算子には、を使用します(*)。

binTreeProdSize :: Tree a -> Nat
binTreeProdSize = catamorphism
     Leaf _ -> 0
     Branch -> \a b -> 1 + a*b

2つのカタモルフィズムが構成するための十分条件を確立してみましょう。明らかに、カタモルフィズムは非常に幸福にで構成されます。これはlength、子の結果を見ずにデータ構造を生成するためです。たとえば、の場合は、好きなものに置き換えるだけで、新しいカタモルフィズムが得られます。doublemap flengthSuccZero

  1. 最初のカタモルフィズムがその子に何が起こるかを見ずにデータ構造を生成する場合、2つのカタモルフィズムがカタモルフィズムに構成されます。

これを超えると、事態はさらに複雑になります。通常のコンストラクター引数と「再帰的引数」（％記号でマークします）を区別してみましょう。したがってLeaf a、再帰的な引数はありませんが、再帰的な引数はBranch %a %bあります。コンストラクターの「再帰的固定性」という用語を使用して、コンストラクターが持つ再帰的引数の数を参照してみましょう。（私はこれらの用語を両方とも作成しました！適切な用語があれば、それが何であるかわかりません！他の場所でそれらを使用することに注意してください！）

最初のカタモルフィズムが何かをゼロ再帰固定コンストラクターにマップする場合、すべてが良好です！

               a               |            b            |     cata(b.a)
===============================|=========================|================
       F a %b %c .. -> Z       |      Z -> G a b ..      |      True

子を新しいコンストラクターに直接マップすれば、それも良いことです。

               a               |            b            |     cata(b.a)
===============================|=========================|=================
   F a %b %c .. -> H %c %d ..  |   H %a %b -> G a b ..   |       True

再帰的なfixityにマップする場合、1つのコンストラクター...

               a               |            b            |     cata(b.a)
===============================|=========================|=================
 F a %b %c .. -> A (f %b %c..) |     A %a -> B (g %a)    |    Implied by g
                               |                         | distributes over f

しかし、それは違いではありません。たとえば、そのg1 g2ようなものが存在する場合g (f a b..) = f (g1 a) (g2 b) ..、それも機能します。

ここから、ルールはもっと乱雑になると思います。

于 2012-08-26T00:36:22.693 に答える
3

カタモルフィズムは、データ構造を結果値に分解します。したがって、一般に、カタモルフィズムを適用すると、結果はまったく異なるものになり、別のカタモルフィズムを適用することはできません。

たとえば、 のすべての要素を合計する関数[Int]はカタモルフィズムですが、結果はIntです。それに別のカタモルフィズムを適用する方法はありません。

ただし、一部の特殊なカタモルフィズムでは、入力と同じ型の結果が作成されます。そのような例の1つはmap f（特定の関数の場合f）です。元の構造を分解する一方で、その結果として新しいリストも作成します。（実際には、カタモルフィズムとアナモルフィズムmap fの両方と見なすことができます。）したがって、そのようなクラスの特別なカタモルフィズムがある場合は、それらを構成できます。

于 2012-08-24T06:42:00.670 に答える
2

意味的等価性を考慮すると、最初のカタモルフィズムがハイロモルフィズムである場合、2 つのカタモルフィズムの構成はカタモルフィズムです。

cata1 . hylo1 = cata2

例（Haskell）：

sum . map (^2) = foldl' (\x y -> x + y^2) 0
于 2012-08-24T07:37:50.663 に答える