Haskell 类型过于宽松：最多需要申请一次延续

Question

假设我有以下类型：

type Control a = (a -> a) -> a -> a

我希望在普遍量化时正好有两个值存在于此类型中：

break :: Control a
break = const id

continue :: Control a
continue = id

然而，精明的人会注意到 Control a 是 Church numerals 的类型，其中有无限多个。有什么方法可以限制这种类型，以便最多可以应用一次延续？也许使用依赖类型？

请注意，Control 可以出现在更大函数的上下文中。例如：

mult :: Int -> Control Int
mult 0 = \k a -> k 0
mult b = \k a -> k (b * a)

如您所见，\k a -> k (b * a) 既不是 break 也不是 continue，但仍然是 Control 的有效居民。但是，它不是 Control a 的居民。它是 Control Int.

的居民

因此，我真正想问的是，是否有一种方法可以检查在类型级别最多应用一次延续。

Answer 1

我们可能会认识到 const id 是 Church 零，而 id 是 Church 1，所以我们需要小于二的 Church naturals - 但如果你想要一个双元素类型，为什么不使用Bool？然后将 True 解释为 const id，将 False 解释为 id，或相反。我们也可以说 Control a 值是有效的，如果它们在解释的图像中。

所有具有两个居民的类型都是同构的，因此如果您限制 Control（您可以对某些依赖类型执行此操作），那将与 Bool 同构。当没有子集的紧凑独立特征时，定义类型的子集更有意义。

Answer 2

您可以为此编写自己的临时 class：

class HasId p where
  theId :: p a a
instance HasId (->) where
  theId = id

type B = forall p a. HasId p => p a a -> p a a

这绝对不应该有任何合法的额外值。

请注意，虽然 HasId 没有任何法则（实际上也不可能有任何法则），但它只允许 (->) 的一个实例，这是我们真正关心的唯一类型。

[编辑：随着我的想法的成熟，我已经完全改变了这个答案几次。]

Haskell 类型过于宽松：最多需要申请一次延续

Haskell type is too permissive: need to apply continuation at most once

haskell

types

dependent-type