racket - 多态函数 `car' 无法应用于参数

Question

我想在eopl中使用typed/racket实现“LET”语言，但遇到问题:我尝试实现三个函数(empty-env、extend-env、apply-env)，但我不知道如何标记类型信息，并且racket无法自动推断这三个函数的类型。我尝试使用any，但仍然遇到问题:

(: empty-env (-> Any))
(define empty-env
  (lambda () (list 'empty-env)))

(: extend-env (-> Any Any Any Any))
(define extend-env
  (lambda (var val env)
    (list 'extend-env var val env)))

(: apply-env (-> Any Any Any))
(define apply-env
  (lambda (env search-var)
    (cond [(eqv? (car env) 'empty-env) (None)]
          [(eqv? (car env) 'extend-env)
           (let ([saved-var (cadr env)]
                 [saved-val (caddr env)]
                 [saved-env (cadddr env)])
             (if (eqv? search-var saved-var)
                 saved-val
                 (apply-env saved-env search-var)))]
          [else (None)])))

racket提示的错误是:

Type Checker: Polymorphic function `car' could not be applied to arguments:Domains: (Listof a)(Pairof a b)Arguments: Anyin: (car env)

如何正确标注类型信息

Answer 1

#lang typed/racket

(define-type EmptyEnv '(empty-env))
(define-type Env      (U EmptyEnv
                         (List 'extend-env Any Any Env)))

(define (None) 'None)

(: empty-env (-> Env))
(define empty-env
  (lambda () (list 'empty-env)))

(: extend-env (-> Any Any Env Env))
(define extend-env
  (lambda (var val env)
    (list 'extend-env var val env)))

(: apply-env (-> Env Any Any))
(define apply-env
  (lambda (env search-var)
    (cond [(eqv? (car env) 'empty-env) (None)]
          [(eqv? (car env) 'extend-env)
           (let ([saved-var (cadr env)]
                 [saved-val (caddr env)]
                 [saved-env (cadddr env)])
             (if (eqv? search-var saved-var)
                 saved-val
                 (apply-env saved-env search-var)))]
          [else (None)])))

(define env (extend-env 'a 42 (empty-env)))
env
(apply-env env 'a)