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

>>5
That expression of fix, however neat it may be, wont terminate when I try to use it. What exactly does x = f x do in haskell?

>>8
These types are finite and recursive. You just can't write them out in the simplistic way, like how you can't pin down a circle on a flat strip of tape. Haskell can't do recursive types. And I wish it could. The real y combinator would be:


let y f = f (y f)

Scheme has the flexibility of being untyped, but this isn't as short in scheme because of strict evaluation and no implicit currying.


(define (y f) (lambda args (apply f (cons (y f) args))))

>>12
And the not an instance of show ain't the error I'm gettin, which is why I don't try any further.