Có thể định nghĩa kiểu đệ quy trong Common Lisp không?

Question

Loại đệ quy là loại có cơ sở và trường hợp đệ quy của chính nó.

Tôi muốn điều này triển khai "danh sách đã nhập", tức là danh sách có đối thủ chỉ cho phép cùng loại phần tử hoặc số không.

tôi đã cố gắng định nghĩa sau đây:

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

Tuy nhiên, điều này báo hiệu một vấn đề ngăn xếp exausted (ít nhất là trên SBCL) do trình biên dịch cố gắng để recurse qua danh sách-of vô thời hạn. Có thể định nghĩa một kiểu dữ liệu như vậy không?

Answer 1

Không thể thực hiện được. Các loại bạn xác định với DEFTYPE là "các loại có nguồn gốc". Kiểu dẫn xuất được mở rộng (như macro) thành một bộ định kiểu kiểu "thực", không thể chứa các kiểu có nguồn gốc. Tất cả các tham chiếu đến các kiểu dẫn xuất (chính là kiểu hoặc các kiểu khác) bên trong phần mở rộng cũng được mở rộng. Vì vậy, kiểu đệ quy sẽ đi vào một vòng lặp infite để thử và mở rộng.

Trivial Types cung cấp loại cho danh sách phù hợp, nhưng điều đó không thực sự kiểm tra các loại phần tử mặc dù lấy nó làm đối số. Vì lý do thẩm mỹ mà sẽ là đủ.

(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 

Nếu không, bạn có thể xác định loại kiểm tra xem các phần tử cặp đầu tiên có đúng loại hay không. Điều đó ít nhất sẽ bắt được những vi phạm rõ ràng nhấ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 

Nếu bạn muốn nó hoạt động trong danh sách có độ dài bất kỳ, bạn sẽ phải xác định loại cho từng danh sách khác nhau mà bạn cần.

(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

Có, nhưng tôi đã lừa dối;)

(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 

Rõ ràng SBCL không thích loại đệ quy - lý do được giải thích cũng bằng câu trả lời khác. Nhưng nếu bạn muốn gắn bó với tiêu chuẩn và vẫn định nghĩa các kiểu đệ quy thì có một ánh sáng ở cuối đường hầm: bạn có thể định nghĩa bất kỳ chức năng nào để kiểm tra sự hài lòng.