Haskell 系统 F 中的绑定运算符，包括种类

Question

我需要知道 Haskell 绑定类型 (>>=) 运算符的 System F 类型是什么。

到目前为止我是这样写的：

(M::*->* A::*) -> (A::* -> (M::*->* B::*)) -> (M::*->*  B:*)

对吗？如果正确，我如何找到最终结果？

谢谢！

Answer 1

你快到了。为类型变量添加显式量词，并删除每个变量使用的类型注释。

∀M:*->*. ∀A:*. ∀B:*. M A -> (A -> M B) -> M B

我使用了更传统的 : 而不是 Haskell 的 ::。

但是请注意，系统 F 没有更高种类（例如 *->*），因此上面的类型只能在更强大的类型系统（例如 System Fω）中找到。

此外，上面我 "conveniently" 省略了对 M 的类型类限制，这使得类型接近但不完全是 >>= 的 Haskell 类型. （另请参阅@DanielWagner 的评论）。

这个不为人知的细节很重要。否则，上面的类型太普遍以至于无人居住——没有 lambda 项具有该类型。实际上，通过矛盾假设 f 具有上述一般类型。那么，

f (λt:*. t->⊥) : ∀A,B:* . (A -> ⊥) -> (A -> B -> ⊥) -> B -> ⊥

其中 ⊥ 是任何空类型（例如 Void，在 Haskell 中）。但是，将 ⊤ 取为任何非空类型（例如 ()，在 Haskell 中），其中居民 u，我们得到

f (λt:*. t->⊥) ⊥ : ∀B:* . (⊥ -> ⊥) -> (⊥ -> B -> ⊥) -> B -> ⊥
f (λt:*. t->⊥) ⊥ ⊤ : (⊥ -> ⊥) -> (⊥ -> ⊤ -> ⊥) -> ⊤ -> ⊥
f (λt:*. t->⊥) ⊥ ⊤ (λx:⊥. x) : (⊥ -> ⊤ -> ⊥) -> ⊤ -> ⊥
f (λt:*. t->⊥) ⊥ ⊤ (λx:⊥. x) (λx:⊥. λy:⊤. x) : ⊤ -> ⊥
f (λt:*. t->⊥) ⊥ ⊤ (λx:⊥. x) (λx:⊥. λy:⊤. x) u : ⊥

所以⊥有人居住--矛盾。

更通俗地说，以上仅证明 data T a = T (a -> Void) 不能是 monad。

Haskell 系统 F 中的绑定运算符，包括种类

Haskell bind operator in System F including kinds

lambda

haskell

system-f