3

在阅读（并实现） http://blog.sumtypeofway.com/recursion-schemes-part-2/的一部分之后， 我仍然想知道cata函数中的类型是如何工作的。cata函数定义为：

mystery :: Functor f => (f a -> a) -> Term f -> a
mystery f = f . fmap (mystery f) . unTerm

我有类似的东西Term Expr。打开包装后我得到Expr (Term Expr). 代数 ( f) 被定义为f :: Expr Int -> Int。我知道我可以轻松调用以下命令：

x = Literal "literal" :: Expr a
f :: Expr Int -> Int
f x :: Int

我也可以想象：

x = Literal "literal" :: Expr (Term Expr)
f :: Expr a -> Int
f x :: Int

但我认为以下内容行不通：

x = Literal "literal" :: Expr (Term Expr)
f :: Expr Int -> Int
f x :: ???

但是，我仍然不明白它在cata函数中的工作原理 - 我如何从Expr (Term Expr)to获取Expr a. 我知道这些值确实有效，但我只是没有得到类型 - 树的叶子会发生什么？这确实是一个mystery...

编辑：我会尝试更清楚地说明我不明白的内容。

在精神上，cata似乎是这样工作的：

  • 适用fmap f于叶子。
  • 现在我有了Expr Int，我可以调用fmap f我拥有的节点并继续前进。

在我申请时，它显然不是这样工作的fmap (cata f)。但是，最终该函数f被Expr Int作为参数调用（在叶子中）。这种类型是如何从Expr (Term Expr)以前的类型中产生的？

4

1 回答 1

2

这就是cata对叶子的操作方式。

假设f :: Expr Int -> Int。然后：

cata f :: Term Expr -> Int
fmap (cata f) :: Expr (Term Expr) -> Expr Int

现在，对于任何函数g :: a -> b，我们有

fmap g :: Expr a -> Expr b
fmap g (Literal n) = Literal n
...

所以，在字面上，g是无关紧要的。这意味着，选择，a ~ Term Expr我们有b ~ Intg = cata f

fmap (cata f) (Literal n) = Literal n  :: Term Int
f (fmap (cata f) (Literal n)) = f (Literal n) :: Int

所以，粗略地说，在叶子上fmap (cata f)是一个空操作，但它会将类型从 更改Expr (Term Expr)为Expr Int。这是一个微不足道的转换，因为Literal n :: Expr a对于任何a.

于 2015-11-12T12:17:58.960 回答