types - 是否可以在 Common Lisp 中定义递归类型？

Question

递归类型是一种类型，它具有自身的基和递归案例。

我希望它实现“类型化列表”，即其 conses 仅允许相同元素类型或 nil 的列表。

我尝试了以下定义:

(deftype list-of (a) `(or null
                          (cons ,a (list-of ,a))))

但是，由于编译器试图无限期地递归列表，这表明堆栈耗尽问题(至少在 SBCL 上)。是否可以定义这样的数据类型？

Answer 1

这是不可能的。您使用 DEFTYPE 定义的类型是“派生类型”。派生类型被扩展(如宏)为“真实”类型说明符，它不能包含派生类型。扩展中对派生类型(类型本身或其他类型)的所有引用也会被扩展。因此，递归类型将进入无限循环以尝试扩展。

Trivial Types为正确列表提供了一种类型，但尽管将其作为参数，但它实际上并没有检查元素类型。出于美观的原因，这就足够了。

(ql:quickload :trivial-types)
(use-package :trivial-types)
(typep '("qwe" "asd" "zxc") '(proper-list string)) ;=> T
(typep '("qwe" "asd" "zxc" 12) '(proper-list string)) ;=> T

否则，您可以定义一个类型来检查前几个元素是否是正确的类型。这至少会发现最明显的违规行为。

(deftype list-of (a)
  `(or null (cons ,a (or null (cons ,a (or null (cons ,a list)))))))
(typep '("asd") '(list-of string)) ;=> T
(typep '("asd" 12) '(list-of string)) ;=> NIL
(typep '("asd" "qwe") '(list-of string)) ;=> T
(typep '("asd" "qwe" 12) '(list-of string)) ;=> NIL
(typep '("asd" "qwe" "zxc") '(list-of string)) ;=> T
(typep '("asd" "qwe" "zxc" 12) '(list-of string)) ;=> T

如果您希望它适用于任何长度的列表，则必须为所需的每个不同列表定义一个类型。

(defun list-of-strings-p (list)
  (every #'stringp list))
(deftype list-of-strings ()
  `(or null (satisfies list-of-strings-p)))
(typep '("qwe" "asd" "zxc" "rty" "fgh") 'list-of-strings) ;=> T
(typep '("qwe" "asd" "zxc" "rty" "fgh" 12) 'list-of-strings) ;=> NIL