Y Combinator in Haskell

Question

Is it possible to write the Y Combinator in Haskell?

It seems like it would have an infinitely recursive type.

 Y :: f -> b -> c  where f :: (f -> b -> c) 

or something. Even a simple slightly factored factorial

factMaker _ 0 = 1 factMaker fn n = n * ((fn fn) (n -1)  {- to be called as (factMaker factMaker) 5 -} 

fails with "Occurs check: cannot construct the infinite type: t = t -> t2 -> t1"

(The Y combinator looks like this

(define Y     (lambda (X)       ((lambda (procedure)          (X (lambda (arg) ((procedure procedure) arg))))        (lambda (procedure)          (X (lambda (arg) ((procedure procedure) arg))))))) 

in scheme) Or, more succinctly as

(λ (f) ((λ (x) (f (λ (a) ((x x) a))))         (λ (x) (f (λ (a) ((x x) a)))))) 

For the applicative order And

(λ (f) ((λ (x) (f (x x)))         (λ (x) (f (x x))))) 

Which is just a eta contraction away for the lazy version.

If you prefer short variable names.

Answer 1

Here's a non-recursive definition of the y-combinator in haskell:

newtype Mu a = Mu (Mu a -> a) y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x) 

hat tip

Answer 2

The Y combinator can't be typed using Hindley-Milner types, the polymorphic lambda calculus on which Haskell's type system is based. You can prove this by appeal to the rules of the type system.

I don't know if it's possible to type the Y combinator by giving it a higher-rank type. It would surprise me, but I don't have a proof that it's not possible. (The key would be to identify a suitably polymorphic type for the lambda-bound x.)

If you want a fixed-point operator in Haskell, you can define one very easily because in Haskell, let-binding has fixed-point semantics:

fix :: (a -> a) -> a fix f = f (fix f) 

You can use this in the usual way to define functions and even some finite or infinite data structures.

It is also possible to use functions on recursive types to implement fixed points.

If you're interested in programming with fixed points, you want to read Bruce McAdam's technical report That About Wraps it Up.