Haskell


Prelude> \x -> x x

<interactive>:2:9:
    Occurs check: cannot construct the infinite type: t1 = t1 -> t0
    In the first argument of `x', namely `x'
    In the expression: x x
    In the expression: \ x -> x x

Prelude> let y f = \x -> f f x

<interactive>:2:19:
    Occurs check: cannot construct the infinite type:
      t1 = t1 -> t2 -> t0
    In the first argument of `f', namely `f'
    In the expression: f f x
    In the expression: \ x -> f f x


​> (lambda (x) (x x))
#<CLOSURE <anon> (x) (x x)>
​> (define (y f) (lambda (x) (f f x)))
#<unspecified>
​> (define factorial (y (lambda (f n) (if (= n 0) 1 (* n (f f (- n 1)))))))
#<unspecified>
​> (factorial 5)
120

>>3
Everyone knows y is cannot be directly expressed with Hindley-Milner types. You are not working in an untyped lambda calculus. 

Use fix for you fixpoints:


fix :: (a -> a) -> a
fix f = let x = f x in x

Expansion:


let x = f x =>
let x = f (f x) =>
let x = f (f (f x)) ..