how to deftype for a list all of whose members are of a given type

Question

I am a bit new to the CL type system but I thought something like the following could work.

(deftype list-of (type)
       `(labels ((check-all (l)
              (every
               (lambda (item)
             (typep item ,type)) l)))
          (and list (satisfies 'check-all))))

However when I try it I get a failure.

(typep '(1 3 3) '(list-of 'int))

because it tries to take the labels as part of type specifier. So would it be better to define that returns a type specifier somehow or is there a better way? I tried using an inline lambda but deftype expects a symbol when satisfies is used.

Answer 1

This is something which is extremely painful in CL because of the lack of recursive types and the requirement that in type specifiers like (satisfies <x>), <x> must be a symbol which names a global function.

Here is something which generally works and avoids inventing a potentially endless sequence of identical functions:

(defun make-lot (type)
  ;; Return a function which checks something is a proper list whose
  ;; elements are of type TYPE.  Note this will not terminate if the
  ;; list is circular.
  (labels ((lot (l)
             (typecase l
               (null t)
               (cons
                (and (typep (car l) type)
                     (lot (cdr l))))
               (t nil))))
    #'lot))

(defvar *lot-name-cache* (make-hash-table :test #'equal))

(deftype list-of (type)
  (let ((predicate-name
         (or (gethash type *lot-name-cache*)
             (let ((pn (make-symbol (with-standard-io-syntax
                                     (format nil "LIST-OF-~S" type)))))
               (setf (symbol-function pn) (make-lot type)
                     (gethash type *lot-name-cache*) pn)))))
    `(satisfies ,predicate-name)))

And now for instance calling (typep x '(list-of integer)) multiple times will create only one function.

Notes.

1. The answer in the question which some people have suggested is a duplicate doesn't work, because it is not sufficient to check that an object is of type list to know that is is in fact a proper list and every will work on it: (typep '(2 4 . a) 'list) is true but (every #'evenp '(2 4 . a)) is an error, so the type check will signal an error, which it should not: (2 4 . a) is simply not a list of even numbers.
2. The function returned by make-lot will not terminate if the list is circular, so checking the type of circular lists will fail to terminate. That could be fixed.
3. In multithreaded implementations this assumes that hashtables are thread-safe enough.