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。我知道这些值确实有效，但我只是不明白类型 - 树叶中会发生什么？这确实是一个谜...

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

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

• 将 fmap f 应用于叶子。
• 现在我有了 Expr Int，我可以调用 fmap f 到我拥有的节点并向上移动。

当我应用 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诠释。这是一个简单的转换，因为 Literal n::Expr a 用于任何 a。