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