Common Lispで再帰型を定義することはできますか？

Question

再帰型は、基底とそれ自身の再帰的な場合を持つ型です。

これは、「型付きリスト」を実装することを希望しました。つまり、コンマが同じ要素タイプまたはnilのみを許可するリストです。

私は次のように定義しようとした：

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

をしかし、これは、リストの無期限を超える再帰しようとしているコンパイラに（少なくとも、SBCL上）スタックexausted問題を通知します。そのようなデータ型を定義することは可能ですか？

Answer 1

これはできません。 DEFTYPEで定義するタイプは「派生タイプ」です。派生型は（マクロのように）派生型を含むことができない "実"型指定子に展開されます。展開内の派生型（型自体またはその他の型）への参照もすべて展開されます。したがって、再帰的な型は無限ループに入り拡張しようとします。

Trivial Typesは、適切なリストの型を提供しますが、それを引数としてとっても要素型を実際にチェックするわけではありません。美容上の理由から、それで十分でしょう。

(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 

そうでなければ、最初のカップル要素が正しい型かどうかをチェックする型を定義できます。それは少なくとも最も明白な違反をキャッチするだろう。

(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 

あなたはそれが任意の長さのリストのために仕事をしたい場合は、あなたが必要とする各別のリストの型を定義する必要があります。

(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

はい、私はだまさ;）

(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は、再帰的なタイプが好きではありません - その理由はよく別の答えによって説明されます。しかし、標準に固執して再帰型を定義したい場合は、トンネルの終わりにライトがあります。満足度をチェックする関数を定義することができます。