是否可以在Common Lisp中定义递归类型? [英] Is it possible to define a recursive type in Common Lisp?

问题描述

递归类型是具有基数和自身递归大小写的类型.

A recursive type is a type which has a base and a recursive case of itself.

我希望它实现类型列表"，即，其表仅允许相同元素类型或nil的列表.

I wanted this to implement "typed lists", i.e., lists whose conses only allow the same element type or nil.

我尝试了以下定义:

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

但是，由于编译器试图无限期地遍历list-of，因此这表示栈过高的问题(至少在SBCL上).可以定义这样的数据类型吗?

However, this signals an stack exausted problem (at least on SBCL) due to the compiler trying to recurse over list-of indefinitely. Is it possible to define such a data type?

推荐答案

这是不可能的.用DEFTYPE定义的类型是派生类型".派生类型被扩展(像宏一样)为真实"类型说明符，其中不能包含派生类型.扩展内部对派生类型(类型本身或其他类型)的所有引用也都得到扩展.因此，递归类型将进入无限循环以尝试扩展.

It's not possible. The types you define with DEFTYPE are "derived types". The derived type is expanded (like a macro) into a "real" type specifier, which can't contain derived types. All references to derived types (either the type itself or others) inside the expansion are also expanded. Thus the recursive type will go into an infite loop to try and expand.

临时类型为适当列表提供了一种类型，但是尽管采用了它，但实际上并不会检查元素类型作为一个论点.出于装饰性原因，就足够了.

Trivial Types provides a type for proper-lists, but that doesn't actually check the element types despite taking it as an argument. For cosmetic reasons that would be sufficient.

(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

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

Otherwise, you could define a type that checks if the first couple elements are correct type. That would at least catch the most obvious violations.

(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

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

If you want it to work for lists of any length, you'll have to define a type for each different list you need.

(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

这篇关于是否可以在Common Lisp中定义递归类型?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！