复合多个“猫amorphism”时，何时为“猫amorphism”？

Question

复合多个“猫amorphism”时，何时为“猫amorphism”？

haskellfunctional-programmingcompositionfoldcatamorphism

17

从http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf第3页可知:

一般情况下，猫态射并不满足合成的封闭性。

在什么条件下，猫态射才能组合成一个猫态射？更具体地（假设我正确理解了该陈述）：

假设我有两个基础函子F和G，以及每个函子的折叠函数：foldF :: (F a -> a) -> (μF -> a)和foldG :: (G a -> a) -> (μG -> a)。

现在假设我有两个代数：a :: F μG -> μG和b :: G X -> X。

当且仅当以下情况时，组合(foldG b) . (foldF a) :: μF -> X是猫态射：

编辑: 我有一个猜测，基于dblhelix的扩展答案: outG . a :: F μG -> G μG必须是某个自然变换η :: F a -> G a在μG的分量。我不知道这是否正确。（编辑2：如colah所指出的那样，这是充分但不必要的）

编辑3：Haskell-Cafe的Wren Thornton补充道：“如果你拥有正确类型的分配律属性（如colah所建议的），则特定情况下事情会顺利进行。但是，拥有正确类型的分配律属性通常意味着在某个相关类别中是一个自然变换；因此，这只是将问题推迟到是否始终存在一个适当相关的类别，以及我们是否可以形式化“适当相关”的含义。”

- Sebastien

4个回答

4

免责声明：这超出了我的专业范围。我相信我的翻译是正确的（在不同的点提供了警告），但请自己验证。

一个“catamorphism”可以被视为一种函数，用其他函数替换数据类型的构造函数。

（在本例中，我将使用以下数据类型：

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+)

很遗憾，在Haskell中没有可用的catamorphism {..}语法（我在Pola中看到了类似的东西）。我一直想为它编写一个quasiquoter。

那么，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

让我们来看一些更多的例子：

关于"catamorphisms"：

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

让我们来尝试建立两个折叠的足够条件以进行组合。显然，任何一个折叠都可以和length、double和map f进行组合，因为它们会在不查看子结果的情况下产生它们的数据结构。例如，在length的情况下，您只需将Succ和Zero替换为您想要的内容即可获得新的折叠。

如果第一个折叠在不查看其子级结果的情况下生成数据结构，则两个折叠将组成一个折叠。

除此之外，事情变得更加复杂。让我们区分常规构造函数参数和“递归参数”（我们将使用％符号标记）。因此，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

如果我们将一个构造函数映射到递归的固定性中...

               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) ..，那么也可以使用。

从这里开始，规则会变得更加混乱，我预计会出现这种情况。

- colah

3

Catamorphisms将数据结构拆分成一个结果值。因此，一般情况下，当您应用catamorphism时，结果完全不同，您无法再对其应用另一个catamorphism。

例如，将所有[Int]元素求和的函数是一个catamorphism，但结果是Int。没有办法在它上面应用另一个catamorphism。

然而，一些特殊的catamorphisms创建与输入相同类型的结果。其中一个例子是map f（对于给定的函数f）。虽然它会解构原始结构，但它也会创建一个新列表作为结果。（实际上，map f既可以视为catamorphism，也可以视为anamorphism。）因此，如果您有这样一类特殊的catamorphisms，则可以将它们组合起来。

- Petr

2

如果我们考虑语义等价性，当第一个是hylomorphism时，两个catamorphisms的组合是一个catamorphism：

cata1 . hylo1 = cata2

例如（Haskell）：

sum . map (^2) = foldl' (\x y -> x + y^2) 0

- ertes

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stefan Holdermans · Accepted Answer

什么情况下，组合（fold2 g）.（fold1 f）::μF1-> A成为一个catamorphism？

当存在一个F1-代数h :: F1 A -> A，使得fold1 h = fold2 g . fold1 f。

为了看到catamorphism通常不是封闭的组合，请考虑类型级别固定点、代数和catamorphism的以下通用定义：

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

为了让catamorphisms组合，我们需要：

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

现在尝试编写这个函数。它需要两个函数作为参数（类型分别为f（Fix g） -> Fix g和g a -> a），以及一个类型为f a的值，并且需要生成一个类型为a的值。你会怎么做呢？要生成类型为a的值，你唯一的希望是应用类型为g a -> a的函数，但是我们陷入了困境：我们没有办法将类型为f a的值转换为类型为g a的值，对吧？

我不确定这是否对您有用，但如果我们从第二个cata的结果到第二个functor的不动点具有一个morphism，则可以组合两个catamorphisms。

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