星期三, 三月 21, 2007

The Y Combinator


I Tested the Y Combinator in the Lazy Scheme:

;The Y Combinator
(define Y (lambda (F) (define (tempF f) (F (f f)))(tempF tempF)))

;A factorial function,it is unrecursive,but if we apply Y to this function,the (Y X) is recursive.
(Y X) is the fix-point of X,that is to say "(Y X)=(X (Y X))"
(define X (lambda (self) (lambda (n)(if (= n 1) 1 (* n (self (- n 1)))))))

;Apply
(Y X) to 10
((Y X) 10)
;The output is 3628800

;The recursive factorial function without the Y combinator may be defined like this:

(define X1 (lambda (self n)(if (= n 1) 1 (* n (self self (- n 1))))))
(X1 X1 10)


I referred to this article:
The Y Combinator

btw:the Y combinator must run in the lazy scheme

没有评论: