Haskell 目录类型

Question

阅读（并实现）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) 到 Expr a。我知道这些值确实有效，但我只是不明白类型 - 树叶中会发生什么？这确实是一个mystery...

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

在心理上，cata 似乎是这样工作的：

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

Answer 1

这就是 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 ~ Int 和 g = 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.

Haskell cata types