Haskell 中是否存在映射？

Question

我有一些GADT，代表着lambda演算中的术语。

data Term a = 
      Var a
    | Lambda a (Term a)
    | Apply (Term a) (Term a)

我想做的是为该类型创建一个通用的转换接口。它的类型签名应该类似于这个：

(Term a -> Term a) -> Term a -> Term a

编写这个函数非常简单：

fmap' :: (Term a → Term a) → Term a → Term a 
fmap' f (Var v) = f (Var v)
fmap' f (Lambda v t) = Lambda v (fmap' f t)
fmap' f (Apply t1 t2) = Apply (fmap' f t1) (fmap' f t2)

因此，我的问题是在Haskell（或Haskell库）中是否有某种通用结构来进行这种转换（类似于Functor，它可能应该被称为morphism）？

- Andrew

---

所以你的问题基本上是在问是否已经存在像 class Morphism m where fmap' :: (m a → m a) → m a → m a 这样的类型类（但可能有不同的名称）？ - stakx - no longer contributing

@stakx，没错，这正是我在寻找的。 - Andrew

我不太明白 fmap' 的目的是什么... 给定签名的最简单实现不就是 id 吗？ - Matthias Benkard

@Matthias，id只接受一个参数，而fmap'是一个二元操作。重要的一点似乎是fmap'仅对一个类型的值进行操作并返回；这就是它与例如($)的区别所在。 - stakx - no longer contributing

@stakx: fmap'和其他Haskell函数一样是一元的。(m a → m a) → m a → m a与(m a → m a) → (m a → m a)相同，后者是id类型的一个实例。 - Matthias Benkard

@Matthias，嗯...有趣。我没有考虑过Curry先生。需要考虑一下。不过，似乎id并不是该签名下唯一合理的函数。 - stakx - no longer contributing

Answer 1

供参考，以下是相关术语...

data Term a = 
      Var a
    | Lambda a (Term a)
    | Apply (Term a) (Term a)

我注意到变量的表示是抽象的，这通常是一个好的计划。

...这里是提议的函数。

fmap' :: (Term a → Term a) → Term a → Term a 
fmap' f (Var v) = f (Var v)
fmap' f (Lambda v t) = Lambda v (fmap' f t)
fmap' f (Apply t1 t2) = Apply (fmap' f t1) (fmap' f t2)

我对这个定义感到困惑的是，f 只应用于形式为 (Var v) 的术语，因此您可能需要实现替换。

subst :: (a → Term a) → Term a → Term a 
subst f (Var v) = f v
subst f (Lambda v t) = Lambda v (subst f t)
subst f (Apply t1 t2) = Apply (subst f t1) (subst f t2)

如果你稍微注意区分绑定变量和自由变量，那么你就能使用替换实现Term的Monad，实现(>>=)。通常，术语可以具有Functor结构用于重命名和Monad结构用于替换。有一篇很棒的论文讲述了这一点，作者是Bird和Paterson，您可以在这里查看：Bird and Paterson，但我偏离主题了。

同时，如果你确实想要对变量以外的东西进行操作，一种常见的方法是使用像uniplate这样的通用遍历工具包，就像augustss建议的那样。另一个可能，也许稍微更加纪律严明的方法，是使用您类型的‘fold’。

tmFold :: (x -> y) -> (x -> y -> y) -> (y -> y -> y) -> Term x -> y
tmFold v l a (Var x)       = v x
tmFold v l a (Lambda x t)  = l x (tmFold v l a t)
tmFold v l a (Apply t t')  = a (tmFold v l a t) (tmFold v l a t')

这里，v、l和a定义了一个替代的代数，用于你的Term形成操作，只作用于y，而不是Term x，解释如何处理变量、lambda和应用程序。你可以选择y为某个适当的单子（例如，为变量线程化环境的m(Term x)），而不仅仅是Term x本身。每个子项都被处理以给出一个y，然后选择适当的函数来产生整个术语的y。折叠捕获标准递归模式。

普通一阶数据类型（以及一些行为良好的高阶数据类型）都可以配备折叠运算符。虽然会降低可读性，但您甚至可以一劳永逸地编写折叠运算符。

data Fix f = In (f (Fix f))

fixFold :: Functor f => (f y -> y) -> Fix f -> y
fixFold g (In xf) = g (fmap (fixFold g) xf)

data TermF a t
  = VarF a
  | LambdaF a t
  | ApplyF t t

type Term a = Fix (TermF a)

与您的递归术语Term a不同，这个TermF a t解释了如何制作一个术语的一层，其中子术语位置有个元素。我们通过使用递归Fix类型来获得递归Term结构。在美学上我们会失去一点，因为每一层都有一个额外的包装它。我们可以定义：

var x      = In (VarF x)
lambda x t = In (LambdaF x t)
apply t t' = In (Apply x t t')

但是我们不能在模式匹配中使用这些定义。然而，好处是我们可以无需额外费用使用通用的fixFold函数。要从一个术语计算出y，我们只需要提供一个类型为

TermF a y -> y

这个函数（就像上面的v、l和a一样）解释了如何处理任何子项已经被转换为y类型值的术语。通过在类型上明确表达每一层包含什么，我们可以利用逐层工作的通用模式。

- pigworker

Answer 2

请查看uniplate包。它可以执行您所说的类型的转换，但适用于任意数据结构。

- augustss

---

具体来说，这种类型的转换可以使用一个名为transform的uniplate函数来完成。文档甚至提供了一个非常类似于问题中代码的示例！ - C. A. McCann

同样地，我建议阅读“几乎组合函数的模式”：http://www.cse.chalmers.se/alumni/bringert/projects.html -- 描述的组合运算符基本上与transform/transformM相同 -- 但是论文如何得出这一结论非常简单明了。 - sclv

Answer 3

在你提出的问题中，使用了fmap'。通过这个函数，转换函数f只能将Var值转换为不同的lambda表达式。由于在fmap'函数中硬编码了这些构造函数保持不变的规则，它不能将Lambda或Apply转换成其他内容。

例如，您的fmap'可以将Var 1转换为Lambda 1 (Var 1)，但无法反过来实现相同的转换。这确实是您的意图吗？

如果fmap'应该允许任意的转换，那么结果会是这样：

fmap' :: (Term a → Term a) → Term a → Term a 
fmap' f t = f t

这与$相同。

(另一方面，如果fmap'只允许更改表达式中的值而不改变其结构，那么你将回到通常的fmap。)

- sth

Answer 4

首先，我没有对你实际问题的答案，但我有一些想法可能对你有用，不确定。

在我看来，这似乎比它本应该更具体，我希望你使用类似以下的东西：

fmap' :: (Term a → Term a) → Term a → Term a 
fmap' f (Var v) = f $ Var v
fmap' f (Lambda v t) = f $ Lambda v (fmap' f t)
fmap' f (Apply t1 t2) = f $ Apply (fmap' f t1) (fmap' f t2)

这个函数仍然可以提供相同的功能，只需在f本身内进行模式匹配。我认为这个函数可以用于像lambda演算的评估之类的事情（尽管，你需要带着一些状态）。

未来对你可能更有用的是：

fmapM :: Monad m => (Term a -> m (Term a)) -> Term a -> m (Term a)
fmapM f (Var v)         = f (Var v)
fmapM f (Lambda v t)    = do
    t' <-fmapM f t
    f (Lambda v t')
fmapM f (Apply t1 t2)   = do
    t1' <- fmapM f t1
    t2' <- fmapM f t2
    f (Apply t1' t2')

您可以使用 State monad 来跟踪来自 lambda 的绑定，并在以后使用它。当您使用 Identity monad 时，此函数与上面的函数相同。您可以编写一个简单的函数 f :: (Term a -> Term a)，并使用 fmap' f = fmapM (f.(return :: -> Identity a))。

如果这对您有帮助，请告诉我 :)

- Axman6

Answer 5

你可能会发现unbound包很有用，尤其是其中的substs函数。

- Daniel Wagner