È possibile definire un tipo ricorsivo in Common Lisp?

Question

Un tipo ricorsivo è un tipo che ha una base e un caso ricorsivo di se stesso.

Volevo che questo implementasse "elenchi digitati", cioè liste le cui conse consentono solo lo stesso tipo di elemento o nil.

Ho provato la seguente definizione:

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

Tuttavia, questo segnala un problema pila esaurita (almeno SBCL) dovuto al compilatore cercando di ricorsione over-elenco dei indefinitamente. È possibile definire un tale tipo di dati?

Answer 1

Non è possibile. I tipi definiti con DEFTYPE sono "tipi derivati". Il tipo derivato viene espanso (come una macro) in un identificatore di tipo "reale", che non può contenere tipi derivati. Vengono inoltre espansi tutti i riferimenti ai tipi derivati ​​(sia il tipo stesso che altri) all'interno dell'espansione. Quindi il tipo ricorsivo entrerà in un ciclo di infetti per tentare di espandersi.

Trivial Types fornisce un tipo per gli elenchi corretti, ma che in realtà non controlla i tipi di elemento nonostante lo assuma come argomento. Per ragioni estetiche sarebbe sufficiente.

(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 

In caso contrario, è possibile definire un tipo che verifica se i primi elementi della coppia sono di tipo corretto. Ciò catturerebbe almeno le violazioni più evidenti.

(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 

Se si desidera lavorare per le liste di qualsiasi lunghezza, si dovrà definire un tipo per ogni lista diversa è necessario.

(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

Sì, ma ho barato;)

(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 

Apparentemente SBCL non piace tipi ricorsivi - il motivo è ben spiegato da un'altra risposta. Ma se vuoi seguire lo standard e definire ancora i tipi ricorsivi, c'è una luce alla fine del tunnel: puoi definire qualsiasi funzione per verificare la soddisfazione.