Haskell 中是否有此 lambda 语句的任何有效定义？

Question

我对 Haskell 中的函数有以下定义。

> q7 :: forall a. forall b. ((a -> b) -> a) -> a

我被要求为它创建一个定义，或者说明为什么定义不存在。以下是我的想法：

q7 接受 a 和 b 的任何类型。语句 (a -> b) -> a 将通过获取两个项目并 returning 后者来实现。现在，如果我更进一步，我可以 return 同样的“a”来实现 ((a -> b) -> a) -> a。我发现 a 和 b 可以是任何类型的问题，因此对于 a 的每个实例，a 可以是不同的类型吗？例如，它可以是 ((Int -> Bool) -> [Char]) -> Int 之类的东西吗？我可能谋杀了那个语法。如果有人有任何提示，或者有人可以证实或否定我的想法，我将不胜感激！

Answer 1

不可能，除非使用无限递归或运行时间错误，所以无法终止。

我们可以利用理论计算机科学的一些结果证明这确实是不可能的。我不知道是否有更简单的方法来证明它确实是不可能的。

如果有一种方法可以通过 Curry-Howard correspondence 编写具有该类型的终止程序，我们将得到逻辑公式 ((a -> b) -> a) -> a（此处，将 -> 读作 "implies") 是命题直觉逻辑的一个定理。

这样的公式被称为 Peirce's Law，并且是在直觉逻辑中不可证明的公式的关键示例之一（相比之下，它是一个经典逻辑中的定理）。

作为证明皮尔斯定律不是直觉定理的一种相当简单的方法，可以运行命题直觉逻辑的决策程序，并观察它输出 "not a theorem"。作为这样的过程，我们可以在 Gentzen 的 LJ 相继演算中搜索无切割证明：这样我们只需要检查有限（和小）数量的可能证明，并观察每次尝试都失败。

Answer 2

The statement (a -> b) -> a would be implemented by taking two items and returning the latter.

你把它和 a -> b -> a 混淆了（也可以写成 a -> (b -> a)。这不一样。

(a -> b) -> a 是一个接受单个参数的函数，return 是一个 a 类型的值。参数的类型为 a -> b，这意味着它是一个函数，其值类型为 a，而 return 的值类型为 b。这与（例如）filter 函数没有什么不同：

filter :: (a -> Bool) -> [a] -> [a]

这需要两个参数，一个 a -> Bool 类型的谓词函数和一个 [a] 类型的列表，并且 return 通过传递每个列表来过滤新的 [a] 值谓词的项目。

I see an issue in that a and b can be any type, so for each instance of a, could a be a different type?

不，如果可以的话，它会有一个不同的名字。 a 可以是任何类型，但是一旦您为 a 选择了一种类型，该类型签名中的每个 a 都代表该类型。 b 是不同的字母，因此它可以是与 a 不同的类型。

因此，对于您的类型签名 ((a -> b) -> a) -> a，您将编写一个接受单个参数（另一个函数）和 return 一个 a 的函数。参数函数的类型为 (a -> b) -> a，这意味着它需要一个类型为 a -> b 的函数作为参数，并且 return 是一个 a.

func :: ((a -> b) -> a) -> a
func f = ...

参数 f，如果被调用，将 return 一个 a 然后你可以 return 从 func:

func :: ((a -> b) -> a) -> a
func f = f x
  where x :: a -> b
        x = ...

但是，要调用 f，您需要为所有类型 a 和 b 传递一个函数 a -> b。由于你没有这样的功能，而且一般也没有办法写这样的功能，所以我认为这是不可能实现的。

Answer 3

假设你有一个函数

pierce :: ((a -> b) -> a) -> a

导入

data Void

来自 Data.Void.

现在我们开始玩游戏了。我们可以将 pierce 类型的 a 和 b 实例化为我们喜欢的任何类型。让我们定义

type A p = Either p (p -> Void)

并用

实例化

a ~ A p
b ~ Void

所以

pierce :: ((A p -> Void) -> A p) -> A p

让我们写一个助手：

noNegate :: forall p r. (A p -> Void) -> r
noNegate apv = absurd (n m)
  where
    m :: p -> Void
    m = apv . Left

    n :: (p -> Void) -> Void
    n = apv . Right

现在我们可以开始杀戮了：

lem :: Either p (p -> Void)
lem = pierce noNegate

要是有这个功能就很奇怪了

lem @Void = Right id
lem @() = Left ()
lem @Int = Left ... -- some integer, somehow

这个函数的行为看起来很奇怪，因为它违反了参数化，Haskell 函数不能做到这一点，但事情只会变得更糟。

可以（但有点烦人）将任意图灵机编码为 Haskell 类型。并且可以设计一种类型来表示特定图灵机将停止的证明（基本上是类型索引的执行跟踪）。在这种跟踪类型上应用 lem 将解决停止问题。

由于 Haskell 的懒惰，一些 "impossible" 功能被证明是有用的，尽管是部分的。例如，

fix :: (a -> a) -> a

在形式上是荒谬的，因为 fix id 声称可以给你任何你想要的东西。 pierce 不是这样的函数。我们试着写一下：

pierce :: ((a -> b) -> a) -> a
pierce f = _

什么必须放在右边？仅制作 a 的方法是应用 f.

pierce f = f _

我们现在必须提供 a -> b 类型的东西。我们没有。我们不知道 b 是什么 ，因此我们无法采用通常的技巧，即从某些 b 构造函数开始获得先机。没有什么可以改善我们的 b。所以我们能做的最好的就是

pierce f = f (const undefined)

看起来没什么用。

Haskell 中是否有此 lambda 语句的任何有效定义？

Are there any valid definitions of this lambda statement in Haskell?

haskell

typing

lambda-calculus