In Common Lisp, how to define a generic data type specifier (like list of integers)?

Question

I would like to define a type specifier that describes a list of things of the same type. So I would like to have (list-of integer) similar to (array integer) (which is built-in). I am able to create it for a specific type, like this:

(defun elements-are-integer (seq) 
  (every #'(lambda (x) (typep x 'integer)) seq))
(deftype list-of-integer ()
  '(and list (satisfies elements-are-integer)))

However, this means I have to do this for every possible type. How can I change this code so that the type would take another type as an argument, and construct the satisfies predicate on the fly? The problem is that the satisfies requires a global symbol, and I don't know how to define the predicate function in proper context (I guess I need to gensym it somehow, but how?). Also, the solution should work so that the type could be created inside another package.

Intrust

Answer 1

Try this:

(defun elements-are-of-type (seq type)
  (every #'(lambda (x) (typep x type)) seq))

(deftype list-of-type (type)
  (let ((predicate (gensym)))
    (setf (symbol-function predicate)
      #'(lambda (seq) (elements-are-of-type seq type)) )
    `(and list (satisfies ,predicate)) ))

(typep '(1 2 3) '(list-of-type integer))
; -> T

(typep '(1 2 a) '(list-of-type integer))
; -> NIL

(typep '(a b c) '(list-of-type symbol))
; -> T

Southsouthwest

Close, but and doesn't short-circuit, so (typep 5 '(list-of-type t)) can throw an error because the satisfies runs before the list check #69817352 – Tank

@MichaelBurge It would be obnoxious for an implementation to check the value space before it has checked the type space, particularly since types are generally checked at compile time and values at runtime. But typep is just a regular runtime function, and a fringe one at that, so it probably shoudn't surprise us that implementations might be a bit lax. The defensive thing to do would be to add a guard like (and (listp seq) ...) to the predicate. – Southsouthwest

Nice. I changed it slightly to have outer function return a function for the sequence for my own use. – Reconstructionist

See https://mcmap.net/q/1162895/-how-to-deftype-for-a-list-all-of-whose-members-are-of-a-given-type for a solution that avoids to create a symbol each time you call list-of-type for the same type. – Deccan

This does not work as a type. In particular (typep '(1 . 2) '(list-of integer)) will signal an error, which it should not. At the risk of blowing my own trumpet, https://mcmap.net/q/1162895/-how-to-deftype-for-a-list-all-of-whose-members-are-of-a-given-type is more nearly correct (it still has termination problems) – Duwalt