Cấu trúc dữ liệu tự tham chiếu trong Lisp/Scheme

Question

Có cách nào để xây dựng cấu trúc dữ liệu tự tham chiếu (nói đồ thị có chu kỳ) trong lisp hoặc lược đồ không? Tôi chưa bao giờ nghĩ về nó trước đây, nhưng chơi xung quanh tôi có thể tìm thấy không có cách đơn giản để làm cho một do thiếu một cách để thực hiện sửa đổi phá hoại. Đây có phải chỉ là một lỗ hổng thiết yếu của các ngôn ngữ chức năng, và nếu có, những ngôn ngữ chức năng lười biếng như haskell thì sao?

Answer 1

Trong Scheme, bạn có thể làm điều đó một cách dễ dàng với set!, set-car!, và set-cdr! (và bất cứ điều gì khác kết thúc bằng một tiếng nổ ('!'), mà chỉ sửa đổi):

(let ((x '(1 2 3))) 
    (set-car! x x) 
    ; x is now the list (x 2 3), with the first element referring to itself 
) 

Answer 2

Common Lisp hỗ trợ sửa đổi cấu trúc dữ liệu với setf.

Bạn có thể tạo cấu trúc dữ liệu hình tròn trong Haskell theo tying the knot.

Answer 3

Trong Common Lisp bạn có thể sửa đổi nội dung danh sách, nội dung mảng, khe của trường Clos vv

Common Lisp cũng cho phép đọc và viết cấu trúc dữ liệu hình tròn. Sử dụng

? (setf *print-circle* t) 
T 

; a list of two symbols: (foo bar) 

? (defvar *ex1* (list 'foo 'bar)) 
*EX1* 

; now let the first list element point to the list, 
; Common Lisp prints the circular list 

? (setf (first *ex1*) *ex1*) 
#1=(#1# BAR) 

; one can also read such a list 

? '#1=(#1# BAR) 
#1=(#1# BAR) 

; What is the first element? The list itself 

? (first '#1=(#1# BAR)) 
#1=(#1# BAR) 
? 

Cái gọi là tinh khiết Ngôn ngữ lập trình chức năng không cho phép tác dụng phụ. Hầu hết các phương ngữ Lisp là không phải là thuần túy. Chúng cho phép các hiệu ứng phụ và chúng cho phép sửa đổi cấu trúc dữ liệu.

Xem sách giới thiệu Lisp để biết thêm về điều đó.

Answer 4

1. Bạn không cần `sửa đổi phá hoại 'để xây dựng cấu trúc dữ liệu tự tham chiếu; ví dụ: trong Common Lisp, '#1=(#1#) là một ô điều khiển chứa chính nó.

2. Đề án và Lisp có khả năng làm thay đổi phá hoại: bạn có thể xây dựng các khuyết điểm tròn trên cách khác như thế này: (let ((x (cons nil nil))) (rplaca x x) x)

Bạn có thể cho chúng tôi biết những gì tài liệu mà bạn đang sử dụng trong khi học tập Lisp/Kế hoạch? Tôi đang biên soạn một danh sách mục tiêu cho những chiếc trực thăng màu đen của chúng tôi; sự lan truyền thông tin sai lạc về Lisp và Đề án này phải dừng lại.

Answer 5

Clos dụ:

 
(defclass node() 
    ((child :accessor node-child :initarg :child))) 

(defun make-node-cycle() 
    (let* ((node1 (make-instance 'node)) 
     (node2 (make-instance 'node :child node1))) 
    (setf (node-child node1) node2))) 

Answer 6

Vâng, và họ có thể có ích. Một trong những giáo sư đại học của tôi đã tạo ra một loại Scheme mà ông gọi là Medusa Numbers. Chúng là các số dấu chấm động chính xác tùy ý có thể bao gồm các số thập phân lặp lại. Anh có chức năng:

(create-medusa numerator denominator) ; or some such 

tạo số Medusa đại diện cho lý trí. Kết quả là:

(define one-third (create-medusa 1 3)) 
one-third => ; scheme hangs - when you look at a medusa number you turn to stone 
(add-medusa one-third (add-medusa one-third one-third)) => 1 

như đã nói trước đây, điều này được thực hiện với ứng dụng cẩn thận của xe hơi được đặt! và set-cdr!

Answer 7

Không chỉ có thể, nó còn là trung tâm của Hệ thống đối tượng chung của Lisp: lớp tiêu chuẩn là một thể hiện của chính nó!

Answer 8

Tôi đã bỏ phiếu cho các kỹ thuật Đề án rõ ràng; câu trả lời này chỉ địa chỉ Haskell.

Trong Haskell, bạn có thể thực hiện điều này một cách hoàn toàn có chức năng sử dụng let, được coi là kiểu tốt. Một ví dụ điển hình là chuyển đổi regexp-to-NFA. Bạn cũng có thể làm điều đó một cách bất hợp pháp bằng cách sử dụng IORef s, được coi là kiểu kém vì nó buộc tất cả mã của bạn vào đơn nguyên IO.

Nói chung, đánh giá lười biếng của Haskell cho phép tự triển khai chức năng đáng yêu của cả cấu trúc dữ liệu tuần hoàn và vô hạn. Trong bất kỳ ràng buộc phức tạp let, tất cả mọi thứ ràng buộc có thể được sử dụng trong tất cả các định nghĩa. Ví dụ, dịch một máy hữu hạn trạng thái cụ thể vào Haskell là một snap, cho dù có bao nhiêu chu kỳ nó có thể có.

Answer 9

Hmm, cấu trúc dữ liệu tự tham chiếu trong các luồng Lisp/Scheme và SICP không được đề cập? Vâng, để tóm tắt, dòng == lazily đánh giá danh sách. Nó có thể là chính xác loại tự tham khảo bạn đã dự định, nhưng đó là một loại tham chiếu tự.

Vì vậy, cons-stream trong SICP là cú pháp làm chậm trễ việc đánh giá các đối số của nó. (cons-stream a b) sẽ trở lại ngay lập tức mà không cần đánh giá một hoặc b, và chỉ đánh giá a hoặc b khi bạn gọi car-stream hoặc cdr-stream

Từ SICP, http://mitpress.mit.edu/sicp/full-text/sicp/book/node71.html: >

(define fibs 
    (cons-stream 0 
       (cons-stream 1 
          (add-streams (stream-cdr fibs) 
             fibs)))) 

Định nghĩa này nói rằng fibs là một luồng bắt đầu bằng 0 và 1, chẳng hạn rằng phần còn lại của luồng có thể là được tạo bằng cách thêm các nguyên tử vào chính nó được dịch chuyển bởi một địa điểm:

Trong trường hợp này, 'fibs' được gán một đối tượng có giá trị được định nghĩa một cách lười biếng về

Hầu như quên đề cập đến, suối lười biếng sống trong các thư viện thường có sẵn SRFI-40 hoặc SRFI 'fibs' -41. Một trong hai người nên có sẵn trong Đề án phổ biến nhất, tôi nghĩ rằng

Answer 10

Tying the Knot (circular data structures in Haskell) trên StackOverflow

Xem thêm trang Haskell Wiki: Tying the Knot

Answer 11

tôi stumbled khi câu hỏi này trong khi tìm kiếm "DANH MỤC THÔNG TƯ LISP Đề án ".

Đây là cách tôi có thể làm một (trong STK Scheme):

Thứ nhất, lập danh sách

(define a '(1 2 3)) 

Tại thời điểm này, STK nghĩ a là một danh sách.

(list? a) 
> #t 

Tiếp theo, đi tới phần tử cuối cùng (3 trong trường hợp này) và thay thế cdr hiện chứa nil với một con trỏ đến chính nó.

(set-cdr! (cdr (cdr a)) a) 

Bây giờ, STk cho rằng không phải là danh sách.

(list? a) 
> #f 

(Làm thế nào để cho nó hoạt động này ra?)

Bây giờ nếu bạn in a bạn sẽ tìm thấy một danh sách dài vô hạn của (1 2 3 1 2 3 1 2 ... và bạn sẽ cần phải tiêu diệt các chương trình. Trong Stk, bạn có thể control-z hoặc control-\ để thoát.

Nhưng danh sách vòng tròn phù hợp nhất là gì?

Tôi có thể nghĩ các ví dụ tối nghĩa để làm với số học modulo như danh sách vòng tròn các ngày trong tuần (M T W T F S S M T W ...) hoặc danh sách số nguyên tròn được biểu thị bằng 3 bit (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..).

Có bất kỳ ví dụ thực tế nào không?