假设我有一个如下所示的类型：

data Term a = Terminal a
| Application (Term a) (Term a)
| Abstraction String (Term a)

现在，我想绘制地图Term a to Term b。理想情况下，我可以使用函数来做到这一点(a -> b)并执行fmap。但是，这对我不起作用。地图来自Terminal a to Terminal b不仅取决于值a，也是祖先的价值观Terminal a（例如深度Terminal a）。所以它更像是[Term a] -> b这很混乱，所以我试图将其分解为更干净的东西。

所以实际上，我需要的是 2 个函数和一个初始值：(c -> Term a -> c)可以召唤每一个祖先来积累我们想要的东西。 （我想这相当于([Term a] -> c)但我不确定这是否会让情况变得混乱或有帮助。）(c -> a -> b)可以映射Terminal a to Terminal b。 （我们还需要一个类型的初始值c)

所以我定义了一个具有以下类型签名的函数：

notQuiteANatTrans :: (c -> Term a -> c) -> (c -> a -> b) -> c -> Term a -> Term b

这不是自然的转变。 （我不认为）或者如果是的话，它正在映射类似的东西[Term a] -> [Term b]其中每一个都是从树的根到Terminal。这个有名字吗？是否有不同的方法来分解我的箭头以获得更干净的东西？

我不确定我完全理解这个问题，所以如果以下内容偏离了不相关的切线，我深表歉意......

地图来自Terminal a to Terminal b不仅取决于值a，也是祖先的价值观Terminal a（例如深度Terminal a).

这听起来让人想起必须检查一棵树才能找到它的深度等。对于一棵树，你可以用它的变态作用- 参见例如FoldTree 的示例 https://hackage.haskell.org/package/containers/docs/Data-Tree.html#v:foldTree.

一般来说，如果您知道数据类型的变形，您可以从中派生出大多数其他（也许全部？）有用的函数。那么变形现象是为了什么Term a?

F-代数

你可以从F-代数 https://bartoszmilewski.com/2017/02/28/f-algebras/。我将遵循我使用过的流程我自己的关于变态现象的文章系列 https://blog.ploeh.dk/2019/04/29/catamorphisms.

像这样定义底层的endofunctor：

data TermF a c =
    TerminalF a
  | ApplicationF c c
  | AbstractionF String c
  deriving (Eq, Show)

instance Functor (TermF a) where
  fmap _ (TerminalF a) = TerminalF a
  fmap f (ApplicationF x y) = ApplicationF (f x) (f y)
  fmap f (AbstractionF s x) = AbstractionF s (f x)

这使您能够通过使用来找出变形现象型孔 https://wiki.haskell.org/GHC/Typed_holes:

termF = cata alg
  where alg      (TerminalF x) = _
        alg (ApplicationF x y) = _
        alg (AbstractionF s c) = _

如果您尝试编译此草图，编译器将抱怨类型漏洞并告诉您需要什么。我使用这个过程来实现这个函数：

termF :: (a -> c) -> (c -> c -> c) -> (String -> c -> c) -> Fix (TermF a) -> c
termF t appl abst = cata alg
  where alg      (TerminalF x) = t x
        alg (ApplicationF x y) = appl x y
        alg (AbstractionF s x) = abst s x

变形需要底层类型的映射器a -> c，以及每个递归节点的“累加器”。

同构

Fix (TermF a)同构于Term a，正如这两个转换函数所证明的：

toTerm :: Fix (TermF a) -> Term a
toTerm = termF Terminal Application Abstraction

fromTerm :: Term a -> Fix (TermF a)
fromTerm = ana coalg
  where coalg      (Terminal x) = TerminalF x
        coalg (Application x y) = ApplicationF x y
        coalg (Abstraction s x) = AbstractionF s x

这意味着您可以轻松定义变形Term a利用变形论Fix (TermF a)。我们就这样称呼它吧foldTerm，因为这可能更惯用一点：

foldTerm :: (a -> c) -> (c -> c -> c) -> (String -> c -> c) -> Term a -> c
foldTerm t appl abst = termF t appl abst . fromTerm

现在您知道了类型foldTerm，你可以扔掉所有的TermF机械并直接实施。

直接实施

同样，您可以使用类型化孔来实现更简单、更直接的实现：

foldTerm :: (a -> c) -> (c -> c -> c) -> (String -> c -> c) -> Term a -> c
foldTerm t appl abst      (Terminal x) = _
foldTerm t appl abst (Application x y) = _
foldTerm t appl abst (Abstraction s x) = _

编译器会告诉你需要什么，而且很明显，实现必须是这样的：

foldTerm :: (a -> c) -> (c -> c -> c) -> (String -> c -> c) -> Term a -> c
foldTerm t appl abst      (Terminal x) = t x
foldTerm t appl abst (Application x y) = appl (recurse x) (recurse y)
  where recurse = foldTerm t appl abst
foldTerm t appl abst (Abstraction s x) = abst s (foldTerm t appl abst x)

请记住，输出foldTerm可以是任何类型c， 包括Term b: c ~ Term b。这能让你做你所要求的事情吗？