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

Wait a minute what the fuck am I saying. y f = f (y f) doesn't give a recursive type and it works perfectly fine in haskell.


Prelude> let y f = f (y f)
Prelude> let fac = y (\f n -> if n == 0 then 1 else n * f(n-1))
Prelude> fac 5
120