Is it possible to define a recursive type in Common Lisp?

Question

A recursive type is a type that has a base and a recursive case in itself.

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

I tried the following definition:

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

However, this signals a stack-related issue (at least on SBCL) due to the compiler trying to list the list indefinitely. Is it possible to define this type of data?

Answer 1

It's impossible. The types that you define with DEFTYPE are "derived types". A derived type expands (like a macro) into a specifier of the "real" type, which cannot contain derived types. All references to derived types (either the type itself or others) inside the extension are also extended. Thus, the recursive type will go into an infinite loop to try to expand.

Trivial types provides a type for valid lists, but does not actually check element types without accepting it as an argument. For cosmetic reasons, this will be enough.

 (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 can determine the type that validates the type of the first pair. This 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 will need to determine the type for each other list that 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 

Answer 2

Yes, but I cheated;)

 (defun satisfication (a) (if a (and (integerp (car a)) (satisfication (cdr a))) T)) (deftype my-list () `(satisfies satisfication)) (typep (cons 1 (cons 2 (cons 3 nil))) 'my-list) > T (typep (cons 1 (cons 2 (cons 3.2 nil))) 'my-list) > NIL 

SBCL does not seem to like recursive types - the reason is well explained by a different answer. But if you want to stick to the standard and still define recursive types, there is light at the end of the tunnel: you can define any function to check for satisfaction.