是否可以在现代 Haskell 中定义 Omega 组合器 (λx.xx)？

Question

堆栈！是否可以在现代 Haskell 中定义 Omega 组合器 (λx.xx)？我想，Haskell98 的类型系统旨在让这种事情变得不可能，但是现代扩展呢？

Answer 1

嗯，你可以定义：

{-# LANGUAGE Rank2Types #-}

omega :: (forall a . a) -> b
omega x = x x

然而这几乎没有用，因为唯一可以作为参数传递的值是 undefined，所以你根本不能将它用作组合器。即使 omega omega 无法键入检查。

要注意的是，为了让 x x 进行类型检查，您必须使用类型 T = t -> s 键入 x，并且 t 与 [=17 统一=] （这样你就可以将 x 传递给它自己）。但这基本上意味着 t 必须是类型变量并且参数必须是完全多态的，从而使函数无用。

Answer 2

您不能在 Haskell 中直接代表 omega。能够代表自应用的类型系统非常少，Haskell的类型系统不是其中之一。但是您可以像这样对无类型的 lambda 演算进行编码并模拟 omega 和自我应用程序：

data Scott = Scott { apply :: Scott -> Scott }

omega = Scott $ \x -> apply x x

现在您可以说 apply omega omega 并进行不终止计算。如果你想在 GHCi 中尝试它，你可能需要以下 Show 实例

instance Show Scott where
  show (Scott _) = "Scott"

Answer 3

不，但有点。这里要注意的是 Haskell 支持 newtype 声明中的无限制递归。根据 Haskell 的语义，newtype 是被定义类型与其实现类型之间的同构。例如这个定义：

newtype Identity a = Identity { runIdentity :: a }

...断言类型 Identity a 和 a 是同构的。根据定义，构造函数 Identity :: a -> Identity a 和观察者 runIdentity :: Identity a -> a 是相反的。

所以借用svenningsson的回答中的Scott类型名，定义如下：

newtype Scott = Scott { apply :: Scott -> Scott }

...断言类型 Scott 与 Scott -> Scott 同构。因此，虽然您不能直接将 Scott 应用于自身，但您可以使用同构来获得其 Scott -> Scott 对应物并将其应用于原始对象：

omega :: Scott -> Scott
omega x = apply x x

或者稍微有点意思的：

omega' :: (Scott -> Scott) -> Scott
omega' f = f (Scott f)

...这是一个定点组合器类型！这个技巧可以改编为在 Haskell:

中编写 Y 组合子的一个版本

module Fix where

newtype Scott a = Scott { apply :: Scott a -> a }

-- | This version of 'fix' is fundamentally the Y combinator, but using the
-- 'Scott' type to get around Haskell's prohibition on self-application (see
-- the expression @apply x x@, which is @x@ applied to itself).  Example:
--
-- >>> take 15 $ fix ([1..10]++)
-- [1,2,3,4,5,6,7,8,9,10,1,2,3,4,5]
fix :: (a -> a) -> a
fix f = (\x -> f (apply x x)) (Scott (\x -> f (apply x x)))

是否可以在现代 Haskell 中定义 Omega 组合器 (λx.xx)？

Is it possible to define Omega combinator (λx.xx) in modern Haskell?

haskell

lambda-calculus