RankNTypes 和教会数字

Question

我正在尝试通过给数字一个这样的类型来研究 Haskell 中的教堂数字，我的想法是自然数 n 基本上是应用函数的表达式以下类型为类型 t 的值 n 次。

type Nat = forall t. (t -> t) -> t -> t

有了这个想法，我可以通过以下方式定义zero、successor、plus、mult：

zero :: Nat
zero = \f t -> t

succ :: Nat -> Nat
succ n = \f -> f . (n f)

plus :: Nat -> Nat -> Nat
plus m n = \f -> (m f) . (n f)

mult :: Nat -> Nat -> Nat
mult m n = \f -> m (n f) -- Equal to \f -> (m . n) f

-- Pointfree version
mult' :: Nat -> Nat -> Nat
mult' = (.)

当我尝试定义求幂时，我想尝试应用允许我定义乘法的相同推理，即 应用 mult m n 次 1.

这导致以下代码

exp' :: Nat -> Nat -> Nat
exp' m n = n (mult m) (succ zero)

但这确实进行了类型检查，并出现以下来自 GHC 的错误：

  Couldn't match type ‘t’ with ‘t1’
  ‘t’ is a rigid type variable bound by
    the type signature for:
      exp' :: forall t. Nat -> Nat -> (t -> t) -> t -> t
    at church.lhs:44:3
  ‘t1’ is a rigid type variable bound by
    a type expected by the context:
      forall t1. (t1 -> t1) -> t1 -> t1
    at church.lhs:44:17
  Expected type: ((t -> t) -> t -> t) -> (t -> t) -> t -> t
    Actual type: Nat -> Nat

错误似乎是说类型检查器没有正确实例化 n 的类型，理想情况下类型 t 应该用另一个 (t -> t) 实例化，以便表达式去通过.

同样让我困惑的是，下面的代码类型检查：

exp :: Nat -> Nat -> Nat
exp m n = n ((.) m) (succ zero) -- replace mult by (.)

有人介意解释一下这里的问题是什么吗？为什么 exp' 的第一个定义不是类型检查，而第二个 exp 是类型检查？

谢谢！

Answer 1

它不起作用的原因是它涉及几个非谓语实例化，这在 Haskell 中通常是不允许的。如果你打开-XImpredicativeTypes，你可以让它编译：

{-# LANGUAGE ImpredicativeTypes #-} 

...

exp' :: Nat -> Nat -> Nat
exp' m n = n (mult m) (succ zero)

第二个版本进行类型检查，因为 mult' 具有更高级别的类型，即使它在定义上等于 (.)，所以类型检查的进行方式不同。由于 (.) 的类型更简单（等级 1），类型检查会更频繁地成功。

GHC 文档警告 ImpredicativeTypes 不起作用，所以我会警告不要使用它。解决这个问题的典型方法是简单地使用 newtype:

newtype Nat' = N { instN :: Nat } 

exp'' :: Nat -> Nat -> Nat
exp'' m n = instN $ n (\(N q) -> N $ mult m q) (N $ succC zero)

要查看实际的谓词实例化，您可以使用类型化孔：

exp' :: Nat -> Nat -> Nat
exp' m n = _ (mult m) (succC zero)

这将报告类型 forall a . (Nat -> Nat) -> Nat -> (a -> a) -> a -> a，与 (Nat -> Nat) -> Nat -> Nat 相同。由于您将 n 放在那里，您必须将此类型与 forall a . (a -> a) -> a -> a 统一，这涉及使用多类型 Nat 实例化类型变量 a。

RankNTypes 和教会数字

RankNTypes and Church numerals

haskell

types

type-theory

higher-rank-types