haskell - 是否有基于终端及其祖先映射递归数据类型的名称？

Question

假设我有一个看起来像这样的类型:

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

现在，我要映射 Term a至 Term b .理想情况下，我可以使用函数 (a -> b) 来做到这一点。并执行 fmap .但是，这对我不起作用。来自 Terminal a的 map 至 Terminal b不仅取决于 a 的值, 也是 Terminal a 的祖先的值(例如 Terminal a 的深度)。所以它更像 [Term a] -> b这很乱，所以我试图把它分解成更干净的东西。
所以真的，我需要的是 2 个函数和一个初始值: (c -> Term a -> c)可以调用每个祖先来积累我们想要的任何东西。 (我猜它相当于 ([Term a] -> c) 但我不确定这是否会混淆情况或有帮助。) (c -> a -> b)可图 Terminal a至 Terminal b . (我们还需要 c 类型的初始值)
所以我定义了一个具有以下类型签名的函数:

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

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

Answer 1

我不确定我是否完全理解这个问题，所以如果以下内容与不相关的切线发生关系，我们深表歉意......

The map from Terminal a to Terminal b is dependent not just on the value of a, but also the values of the ancestors of Terminal a (e.g. the depth of Terminal a).

这听起来让人想起必须检查一棵树才能找到它的深度。对于一棵树，您可以通过它的变质来做到这一点 - 参见例如 the examples for foldTree .
一般来说，如果您知道数据类型的 catamorphism，您可以从中派生大多数其他(也许是全部？)有用的函数。那么 Term a 的变质是什么？ ?
F-代数
您可以从 F-Algebras 推导出变质现象。 .我将按照我在 my own article series on 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)

这使您可以通过使用 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

catamorphism 需要一个底层类型的映射器 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 .这能让你做你所要求的吗？