Пишем Y комбинатор в машинке / ракетке

Question

Допустим, у меня есть нетипизированная реализация Y-комбинатора в Racket.

версия pasterack.org

#lang racket

(define Y
  ((λ (f)
     (f f))
   (λ (z)
     (λ (f)
       (f (λ (x) (((z z) f) x)))))))

(define factorial
  (Y (λ (recursive-factorial)
       (λ (x)
         (if (<= x 0)
             1
             (* x (recursive-factorial (- x 1))))))))

(factorial 5)

Как мне перевести это на печатный / ракетку?

NB Я думаю, что это не канонический способ написания Y комбинатора, но он должен быть эквивалентным.

Answer 1

версия pasterack.org

#lang typed/racket

(define Y
  (;(ann ;; Not needed
    (λ (f)
      (f f))
   ;(All (A) (→ (Rec r (→ r A)) A))) ;; Not needed
   (ann
    (λ (z)
      (λ (f)
        (f (λ (x) (((z z) f) x)))))
    (Rec r (→ r (All (T R) (→ (→ (→ T R) (→ T R)) (→ T R))))))))

(: factorial (→ Real Real))
(define factorial
  (Y (λ ([recursive-factorial : (→ Real Real)])
       (λ ([x : Real])
         (if (<= x 0)
             1
             (* x (recursive-factorial (- x 1))))))))

(factorial 5)

Вы также можете включить определения, чтобы избежать необходимости (define Y …) а также (define factorial …):

версия pasterack.org

#lang typed/racket

((;; Y combinator
  (;(ann ;; Not needed
    (λ (f)
      (f f))
   ;(All (A) (→ (Rec r (→ r A)) A))) ;; Not needed
   (ann
    (λ (z)
      (λ (f)
        (f (λ (x) (((z z) f) x)))))
    (Rec r (→ r (All (T R) (→ (→ (→ T R) (→ T R)) (→ T R)))))))
  ;; Recursive function
  (λ ([recursive-factorial : (→ Real Real)])
    (λ ([x : Real])
      (if (<= x 0)
          1
          (* x (recursive-factorial (- x 1)))))))
 5)