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

Question

假设我有一种类似这样的类型：

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的值，还取决于Terminal a祖先的值(例如Terminal a的深度)。所以它更像[Term a] -> b，它是混乱的，所以我试图把它分解成更干净的东西。

所以，实际上，我需要的是类似于两个函数和一个初始值的东西:可以对每个祖先调用(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

我不确定我是否完全理解这个问题，所以如果下面的事情发生在不相关的切线上，我很抱歉.

从Terminal a到Terminal b的映射不仅取决于a的值，还取决于Terminal a祖先的值(例如Terminal a的深度)。

这听起来让人联想到必须检查一棵树来寻找，例如，它的深度。对于一棵树，你可以用它的变态作用来完成它--例如，参见foldTree的例子。

通常，如果您知道数据类型的变形，您可以派生出大多数其他类型(可能全部？)有用的功能。那么Term a的变态作用是什么呢？

F-代数

你可以从F-代数中得到变质作用。我将遵循我在我自己的关于变态的系列文章中使用的过程。

像下面这样定义底层的内皮功能：

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)

这使您能够使用类型孔计算出变质作用。

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。这能让你做你想做的事吗？