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