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

Question

假设我有一种看起来像这样的类型：

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

现在，我想将术语 术语b 映射。理想情况下，我将能够使用函数（a - ＆gt; b）进行此操作，并且只需实现 fmap 。但是，这对我不起作用。 终端A 到终端B 的地图不仅取决于 a 的值，还取决于祖先的值终端A （例如终端A 的深度）。因此，它更像是 [术语A] - ＆gt; b 是凌乱的，所以我试图将其分解为更清洁的东西。

因此，实际上，我需要的是两个功能和一个初始值：（c - ＆gt;术语a - ＆gt; c）可以在每个祖先上调用，以累积我们想要的任何东西。 （我猜这相当于（[[术语a] - ＆gt; c），但我不确定是混淆情况还是有帮助的。）（c - ＆gt; a - ＆gt; b）可以映射终端a <代码>终端b 。 （我们还需要类型 c 的初始值）

因此，我定义具有以下类型签名的函数：

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

这​​不是自然转换。 （我不认为）或者，它正在映射 [术语A] - ＆GT之类的内容； [术语B] 其中每个是从树的根到终端的路径。有这个名字吗？是否有一种分解我的箭头以获取更清洁的方法？

Answer 1

我不确定我是否完全理解这个问题，所以很抱歉，如果以下情况下有无关紧要的切线...

终端A to 终端B 的地图不仅取决于 a 的值，还取决于祖先的祖先值终端A （例如终端A 的深度）。

这听起来让人想起必须检查一棵树才能找到它的深度。对于一棵树，您可以使用其 catamormathism - 请参阅Eg foldtree的示例。

通常，如果您知道数据类型的血统，则可以从中得出大多数其他（也许全部？）有用的功能。那么术语a 的血统是什么？

f-algebra

您可以从。

定义基本的内函数：

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 - ＆gt; C 以及每个递归节点的“累加器”。

同构

fix（termf a）是同构的，术语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

这意味着您可以轻松地定义术语a 术语的垂直态/code>使用 fix 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 ，包括术语b ： c〜项b 。这使您可以做您要问的事情吗？