Haskell如何写自助申请功能？

Question

我尝试了以下代码，但它产生了类型错误。

sa f = f f

• Occurs check: cannot construct the infinite type: t ~ t -> t1
• In the first argument of ‘f’, namely ‘f’
  In the expression: f f
  In an equation for ‘sa’: sa f = f f
• Relevant bindings include
    f :: t -> t1
      (bound at fp-through-lambda-calculus-michaelson.hs:9:4)
    sa :: (t -> t1) -> t1
      (bound at fp-through-lambda-calculus-michaelson.hs:9:1)

Answer 1

使用新类型构造无限类型。

newtype Eventually a = NotYet (Eventually a -> a)

sa :: Eventually a -> a
sa eventually@(NotYet f) = f eventually

在 GHC 中，eventually 和 f 将是内存中的同一个对象。

Answer 2

我不认为存在适用于 Haskell 中所有术语的单一自助应用功能。自应用程序是类型化 lambda 演算中的一个奇特事物，它通常会逃避类型化。这与这样一个事实有关，即通过自应用我们可以表达定点组合器，当将其视为逻辑系统时，它会在类型系统中引入不一致（参见 Curry-Howard 对应关系）。

您问及将其应用于 id 函数。自申请id id中，两个id的类型不同。更明确地说，它是 (id :: (A -> A) -> (A -> A)) (id :: A -> A)（对于任何类型 A）。我们可以制作一个专门为id功能设计的自助应用程序：

sa :: (forall a. a -> a) -> b -> b
sa f = f f

ghci> :t sa id
sa id :: b -> b

效果很好，但受其类型的限制。

使用RankNTypes你可以创建这样的自应用函数系列，但是你无法创建一个通用的自应用函数，这样sa t就可以了-typed iff t t 类型正确（至少在 System Fω ("F-omega") 中不是，GHC 的核心演算基于此）。

原因是，如果你正式（可能）计算出来，那么我们可以得到 sa sa，它没有范式，并且已知 Fω 是归一化的（直到我们添加 fix当然）。

Answer 3

这是因为无类型 lambda 演算在某种程度上比 Haskell更强大。或者，换句话说，无类型 lambda 演算没有类型系统。因此，它没有完善的类型系统。而 Haskell 确实有一个。

这不仅出现在自我应用程序中，而且出现在涉及无限类型的任何情况下。试试这个，例如：

i x = x
s f g x = f x (g x)
s i i

令人惊讶的是类型系统如何发现看似无害的表达式 s i i 不应被合理的类型系统所允许。因为，如果允许，则可以自行申请。

Haskell如何写自助申请功能？

How can I write self-application function in Haskell?

haskell

lambda-calculus