在 typed/racket 中编写 Y 组合器

Question

假设我在 Racket 中有一个 Y 组合器的无类型实现。

#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)

如何将其翻译成 typed/racket？

N.B。我认为这不是编写 Y 组合子的规范方式，但它应该是等价的。

Answer 1

pasterack.org version

#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 version

#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)

在 typed/racket 中编写 Y 组合器

Writing the Y combinator in typed/racket

y-combinator

racket

typed-racket