主页 / coding / 问题 / 79322925
Accepted
Wheat Wizard
Asked: 2025-01-02 14:20:53 +0800 CST

Fix 的 Böhm-Beraducci 编码

  • 772

我有如下定义的不动点函子：

newtype Fix f =
  Fix
    { unfix ::
      f (Fix f)
    }

我想定义一个函数，它接受 aFix f并给出其 Böhm-Beraducci 编码。因此它应该具有以下类型：

cata :: Fix f -> (forall a. (f a -> a) -> a)

我可以轻松定义像这样的函数但带有额外的约束f，Functor但没有这个限制我就很挣扎。

直观地讲，我想采用 AST 并Fix用输入函数替换构造函数的所有实例，但实际上这似乎需要一个Functor实例F。但据我了解，即使f不是， Böhm-Beraducci 编码也应该存在Functor。

我觉得我在这里遗漏了一些简单的东西。我遗漏了什么定义吗？如果Functor确实需要，为什么？Böhm-Beraducci 编码何时需要像这样的额外约束？

haskell

1 个回答

  1. Best Answer

    快速浏览原始论文，似乎 Böhm-Berarducci 编码使用系统 F 类型表示项代数。

    项代数本质上涉及一个隐式函数f，它始终是一个函子。

    Haskell 超越了这一点，允许在任何 上存在类型级别的固定点f，甚至那些不能转换成函子的固定点。

    一个著名的例子是负递归类型newtype R a = R { unR :: R a -> a }。Haskell 类型系统允许这种类型定义。R a仅使用这个，并且没有术语级递归，我们就可以推导出fix :: forall a . (a -> a) -> a（顺便说一下，这是一个简短但并不平凡的练习）。

    相比之下，系统 F 就不能那么通用。如果我们R a在系统 F 中有，我们也会有fix，因此fix id :: forall a . a可以用于任何系统 F 类型。但我们知道系统 F 是一致的，所以这不可能发生。

    • 2

相关问题