catamorphisms的构成何时是一个变形？

Question

来自http://research.microsoft.com/en-us/um/people/emeijer/Papers/meijer94more.pdf的第3页:

一般情况下,catamorphisms在组成下是封闭的

在什么条件下,catamorphisms构成了一个catamorphism？更具体地说(假设我正确地理解了陈述):

假设我有两个基础仿函数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必须是?G一些自然转换的组成部分? :: F a -> G a.我不知道这是否正确.(编辑2:正如科拉指出的那样,这已足够,但并非必要.)

编辑3: Haskell-Cafe上的Wren Thornton补充说:"如果你有正确的分配属性(正如科拉所说的那样),那么事情就会适用于特定情况.但是,拥有正确的分配属性通常相当于在一些适当相关的类别中进行自然变换;因此,只是将问题推迟到一个适当相关的类别是否总是存在,以及我们是否可以正式化"适当相关"的含义."

Answer 1

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

当存在一个F1代数h :: F1 A -> A这样fold1 h = fold2 g . fold1 f.

要看到catamorphisms一般不在组合下关闭,请考虑以下类型级别定点,代数和变形的一般定义:

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

对于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

现在尝试编写这个函数.它需要两个函数作为参数(类型f (Fix g) -> Fix g和g a -> a分别)和一个类型的值f a,它需要生成一个类型的值a.你会怎么做？要产生类型的值,a你唯一的希望是应用类型的函数g a -> a,但是我们被卡住:我们无法将类型f a的值转换为类型的值g a,对吗？

我不确定这是否对你的目的有用,但是一个条件的例子,一个人可以组成catamorphisms是如果我们有从第二个cata的结果到第二个仿函数的固定点的态射:

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

Answer 2

变形将数据结构解构为结果值。所以，一般来说，当你应用一种变形论时，结果是完全不同的，并且你不能对其应用另一种变形论。

例如，对 的所有元素求和的函数[Int]是一个变形函数，但结果是Int。无法对其应用另一种变形。

然而，一些特殊的变形会创建与输入相同类型的结果。一个这样的例子是map f（对于某些给定的函数f）。在解构原始结构的同时，它还创建一个新列表作为其结果。（实际上，map f可以将其视为变形和变形。）因此，如果您有一类特殊的变形，您可以组合它们。