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一定是μG一些自然转换的组件η :: F a -> G a。我不知道这是否正确。（编辑 2：正如 colah 指出的那样，这已经足够但不是必需的。）

编辑 3： Haskell-Cafe 上的 Wren Thornton 补充道：“如果你有正确的分配属性（正如 colah 建议的那样），那么事情就会针对特定情况解决。但是，拥有正确的分配属性通常相当于在某个适当相关的类别中进行自然转换；所以这只是将问题推迟到适当相关的类别是否总是存在，以及我们是否可以形式化“适当相关”的含义。”

4

4 回答 4

5

组成 (fold2 g) 是什么时候。(fold1 f) :: μF1 -> A 变质？

当存在一个F1- 代数h :: F1 A -> A使得fold1 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

现在尝试编写这个函数。它需要两个函数作为参数（分别是类型f (Fix g) -> Fix g和类型g a -> a）和一个类型的值f a，它需要产生一个类型的值a。你会怎么做？要产生一个 type 的值，a你唯一的希望是应用 type 的函数g a -> a，但是我们被困住了：我们没有办法将 typef a的值变成 type 的值g a，不是吗？

我不确定这对您的目的是否有用，但是一个可以组合成变态的条件的例子是，如果我们有从第二个 cata 的结果到第二个函子的不动点的态射：

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

（免责声明：这超出了我的专业领域。我相信我是正确的（在不同的地方提供了警告），但是......请自己验证。）

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

（遗憾的是，该catamorphism {..}语法在 Haskell 中不可用（我在 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

让我们再考虑几个变态的例子：

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

让我们尝试建立两个变质两个组成的充分条件。显然，任何 catamorphism 都会很高兴地由 组成length，double并且map f因为它们在不查看子结果的情况下产生它们的数据结构。例如，在 的情况下length，您可以将Succand替换Zero为您想要的任何内容，并且您拥有新的 catamorphism。

  1. 如果第一个 catamorphism 产生一个数据结构而不看它的孩子发生了什么，那么两个 catamorphism 将组成一个 catamorphism。

除此之外，事情变得更加复杂。让我们区分普通的构造函数参数和“递归参数”（我们将用 % 符号标记）。所以Leaf a没有递归参数，但是Branch %a %b有。让我们使用构造函数的术语“递归固定性”来指代它具有的递归参数的数量。（我已经编造了这两个术语！我不知道合适的术语是什么，如果有的话！小心在其他地方使用它们！）

如果第一个 catamorphism 将某些东西映射到零递归固定构造函数中，那么一切都很好！

               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

但这不是iff。例如，如果存在g1 g2这样的g (f a b..) = f (g1 a) (g2 b) ..，那也有效。

我预计，从这里开始，规则会变得更加混乱。

于 2012-08-26T00:36:22.693 回答
3

Catamorphisms 将数据结构解构为结果值。所以，一般来说，当你应用一个变质时，结果是完全不同的，你不能对它应用另一个变质。

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

但是，一些特殊的变态会产生与输入相同类型的结果。一个这样的例子是map f（对于某些给定的函数f）。在解构原始结构的同时，它还创建了一个新列表作为其结果。（实际上，map f既可以看作变质，也可以看作变形。）所以如果你有这样一类特殊的变质，你可以组合它们。

于 2012-08-24T06:42:00.670 回答
2

如果我们考虑语义等价，两个变态的组合是变态，当第一个是变态时：

cata1 . hylo1 = cata2

例如（哈斯克尔）：

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