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

Question

Stack! Is it possible to define Omega combinator (λx.xx) in modern Haskell? I suppose, Haskell98's type system is designed to make things like this impossible, but what about modern extensions?

Answer 1

You cannot represent omega directly in Haskell. There are very few typesystems that can represent self-applications and the type system of Haskell is not one of them. But you can encode the untyped lambda calculus and simulate omega and self application like so:

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

omega = Scott $ \x -> apply x x

Now you can say apply omega omega and get a non-terminating computation. If you want to try it out in GHCi, you probably want the following Show instance

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

Answer 2

No, but sort of. The thing to appreciate here is that Haskell supports unrestricted recursion in newtype declarations. By the semantics of Haskell, a newtype is an isomorphism between the type being defined and its implementation type. So for example this definition:

newtype Identity a = Identity { runIdentity :: a }

...asserts that the types Identity a and a are isomorphic. The constructor Identity :: a -> Identity a and the observer runIdentity :: Identity a -> a are inverses, by definition.

So borrowing the Scott type name from svenningsson's answer, the following definition:

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

...asserts that the type Scott is isomorphic to Scott -> Scott. So you while you can't apply a Scott to itself directly, you can use the isomorphism to obtain its Scott -> Scott counterpart and apply that to the original:

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

Or slightly more interesting:

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

...which is a fixpoint combinator type! This trick can be adapted to write a version of the Y combinator in Haskell:

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)))