使用多态联合类型的出现类型

Question

假设我想把下面的无类型代码转换成有类型的代码。这些函数的灵感来自 SICP，它们展示了如何完全从函数构造数据结构。

(define (make-pair x y)
    (lambda (c)
        (cond
            ((= c 1) x)
            ((= c 2) y)
            (error "error in input, should be 1 or 2"))))

(define (first p) (p 1))
(define (second p) (p 2))

要直接将其转换为类型球拍，make-pair 函数的 return 值似乎是 (: make-pair (All (A B) (-> A B (-> Number (U A B)))))。然后，first 的类型应该是 (: first (All (A B) (-> (-> Number (U A B)) A)))。但是，在实现该函数时，我们现在不能直接调用 (p 1)，因为我们需要某种事件类型来确保 first return 仅属于 A 类型。将 first 的 return 类型更改为 (U A B) 是可行的，但随后输入的负担将由用户承担，而不是 API。那么在这种情况下，我们如何在 first 中使用出现类型（即如何对类型变量 A 使用谓词），以便我们可以安全地 return 只有第一个组件一对？

更新

我尝试了一种与上述略有不同的方法，它要求将 A 和 B 的谓词作为参数提供给 make-pair 函数。下面是代码：

#lang typed/racket


(define-type FuncPair (All (A B) (List (-> Number (U A B)) (-> A Boolean) (-> B Boolean))))

(: make-pair (All (A B) (-> A B (-> A Boolean) (-> B Boolean) (FuncPair A B))))
(define (make-pair x y x-pred y-pred)
    (list
        (lambda ([c : Number])
            (cond
                ((= c 1) x)
                ((= c 2) y)
                (else (error "Wrong input!"))))
        x-pred
        y-pred))

(: first (All (A B) (-> (FuncPair A B) Any)))
(define (first p)
    (let ([pair-fn (car p)]
          [fn-pred (cadr p)])
        (let ([f-value (pair-fn 1)])
            (if (fn-pred f-value)
                f-value
                (error "Cannot get first value in pair")))))

但是，这在检查 (fn-pred f-value) 条件时失败并出现错误 expected: A given: (U A B) in: f-value

Answer 1

从你问题开头的未键入代码来看，一对 A 和 B 似乎是一个函数，给定 1，返回 A，给定 2，返回B、这种函数的表达方式是用case->类型：

#lang typed/racket

(define-type (Pairof A B)
  (case-> [1 -> A] [2 -> B]))

访问器的定义方式与原始无类型代码相同，只需添加类型注释即可：

(: first : (All (A B) [(Pairof A B) -> A]))
(define (first p) (p 1))
(: second : (All (A B) [(Pairof A B) -> B]))
(define (second p) (p (ann 2 : 2)))

构造函数的类型应该是：

(: make-pair : (All (A B) [A B -> (Pairof A B)]))

但是构造函数并不能按原样工作。有一点是错误的，即您的 else 子句缺少其中的 else 部分。修复给你：

(: make-pair : (All (A B) [A B -> (Pairof A B)]))
(define (make-pair x y)
  (lambda (c)
    (cond
      [(= c 1) x]
      [(= c 2) y]
      [else (error "error in input, should be 1 or 2")])))

这几乎是正确的，如果打字球拍足够棒的话，那就对了。 Typed racket 将 equal? 专门用于出现类型，但它不会为 = 做同样的事情。将 = 更改为 equal? 修复它。

(: make-pair : (All (A B) [A B -> (Pairof A B)]))
(define (make-pair x y)
  (lambda (c)
    (cond
      [(equal? c 1) x]
      [(equal? c 2) y]
      [else (error "error in input, should be 1 or 2")])))

理想情况下，出现类型应该与 = 一起使用，但也许 (= 2 2.0) return 之类的事实使得它既难以实现又不太有用。

使用多态联合类型的出现类型

Occurrence typing with polymorphic union types

racket

typed-racket