假设我有一个看起来像这样的类型：
data Term a = Terminal a
| Application (Term a) (Term a)
| Abstraction String (Term a)现在，我想将 Term a 映射到 Term b。理想情况下，我可以使用函数 (a -> b) 来实现这一点，并且只需实现 fmap。但是，这对我不起作用。从 Terminal a 到 Terminal b 的映射不仅取决于 a 的 value，还取决于 Terminal a 的祖先的 values（例如 Terminal a 的深度）。所以它更像是混乱的 [Term a] -> b ，所以我试图将它分解成更干净的东西。
所以真的，我需要的是像 2 个函数和一个初始的 value: (c -> Term a -> c) 可以在每个祖先上调用，以便积累我们想要的任何东西。 （我想它相当于 ([Term a] -> c)，但我不确定这是否会混淆情况或有帮助。） (c -> a -> b) 可以将 Terminal a 映射到 Terminal b。 （我们还需要一个 c 类型的初始 value）
所以我定义了一个具有以下类型签名的函数：
notQuiteANatTrans :: (c -> Term a -> c) -> (c -> a -> b) -> c -> Term a -> Term b这不是自然的转变。 （我不这么认为）或者，如果是这样，它会映射类似于 [Term a] -> [Term b] 的东西，其中每一个都是从树根到 Terminal 的路径。有这个名字吗？是否有不同的方法来分解我的箭头以获得更清洁的东西？
回答1
我不确定我是否完全理解这个问题，所以如果以下内容与不相关的切线发生关系，我们深表歉意......
从
Terminal a到Terminal b的映射不仅取决于a的 value，还取决于Terminal a的祖先的 values（例如Terminal a的深度）。
这听起来让人想起必须检查一棵树才能找到它的深度。对于一棵树，您可以通过它的变质来做到这一点 - 参见例如https://hackage.haskell.org/package/containers/docs/Data-Tree.html#v:foldTree。
一般来说，如果您知道数据类型的 catamorphism，您可以从中派生大多数其他（也许是全部？）有用的函数。那么 Term a 的变质是什么？
F-代数
您可以从 https://bartoszmilewski.com/2017/02/28/f-algebras/ 推导出变质。我将按照我在https://blog.ploeh.dk/2019/04/29/catamorphisms 中使用的过程进行操作。
像这样定义底层的内函子：
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 xcatamorphism 需要底层类型 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这意味着您可以使用 Fix (TermF a) 的 catamorphism 轻松定义 Term a 的 catamorphism。我们称它为 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。这能让你做你所要求的吗？