Selbstreferentielle Datenstrukturen in Lisp/Scheme

Question

Gibt es eine Möglichkeit, eine selbstreferentielle Datenstruktur (sagen wir ein Diagramm mit Zyklen) in Lisp oder Schema zu konstruieren? Ich hätte nie darüber nachgedacht, aber herumspielen kann ich keinen direkten Weg finden, einen daraus zu machen, weil es keine Möglichkeit gibt, destruktive Modifikationen vorzunehmen. Ist das nur ein wesentlicher Fehler funktionaler Sprachen, und wenn ja, was ist mit faulen funktionalen Sprachen wie Haskell?

Answer 1

In Schema, können Sie es leicht tun mit set!, set-car! und set-cdr! (und alles, was in einem Knall ('!') endet, die Änderung angibt):

(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 unterstützt Modifikation von Datenstrukturen mit setf.

Sie können eine kreisförmige Datenstruktur in Haskell von tying the knot bauen.

Answer 3

In Common Lisp Sie Listeninhalte, Array-Inhalt ändern können, Slots von CLOS Instanzen usw.

Common Lisp erlaubt auch kreisförmige Datenstrukturen zu lesen und zu schreiben. Verwenden

? (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) 
? 

reine funktionalen Programmiersprachen Sogenannter keine Nebenwirkungen ermöglichen. Die meisten Lisp-Dialekte sind nicht rein. Sie erlauben Nebenwirkungen und erlauben es, Datenstrukturen zu modifizieren.

Siehe Lisp Einführung Bücher für mehr darüber.

Answer 4

1. Sie benötigen keine destruktive Modifikation, um selbstreferenzielle Datenstrukturen zu konstruieren; z.B. in Common Lisp, '#1=(#1#) ist eine Cons-Zelle, die sich selbst enthält.

2. Scheme und Lisp sind in der Lage destruktive Änderungen machen: Sie können die Kreis Nachteile oben alternativ wie folgt konstruieren: (let ((x (cons nil nil))) (rplaca x x) x)

Können Sie uns wissen lassen, welches Material Sie verwenden, während Lisp Lernen/Planen? Ich erstelle eine Zielliste für unsere schwarzen Helikopter; Diese Verbreitung von Fehlinformationen über Lisp und Scheme muss gestoppt werden.

Answer 5

CLOS Beispiel:

 
(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

Ja, und sie können nützlich sein. Einer meiner College-Professoren schuf einen Scheme-Typ, den er Medusa Numbers nannte. Sie waren willkürliche Präzisions-Gleitkommazahlen, die sich wiederholende Dezimalzahlen enthalten könnten. Er hatte eine Funktion:

(create-medusa numerator denominator) ; or some such 

die die Medusa Zahl geschaffen, die die rationale vertreten. Als Ergebnis:

(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 

wie gesagt, dies ist mit vernünftigen Anwendung von Set-Car getan! und set-cdr!

Answer 7

Nicht nur ist es möglich, es ist ziemlich zentral für das Common Lisp Object System: Standard-Klasse ist eine Instanz für sich!

Answer 8

Ich upvoted die offensichtlichen Scheme Techniken; Diese Antwort adressiert nur Haskell.

In Haskell können Sie dies rein funktional mit let tun, die als guter Stil gilt. Ein schönes Beispiel ist die Regexp-NFA-Konvertierung. Sie können es auch zwingend mit IORef s tun, was als schlechter Stil gilt, da er Ihren gesamten Code in die IO-Monade zwingt.

Im Allgemeinen eignet sich die Lazy-Evaluierung von Haskell hervorragend für funktionale Implementierungen von zyklischen und unendlichen Datenstrukturen. In jeder komplexen let Bindung können alle gebundenen Dinge in allen Definitionen verwendet werden. Zum Beispiel ist das Übersetzen eines bestimmten endlichen Automaten in Haskell ein Kinderspiel, egal wie viele Zyklen es haben mag.

Answer 9

Hmm, selbst referentielle Datenstrukturen in Lisp/Scheme und SICP-Streams werden nicht erwähnt? Nun, um es zusammenzufassen, Streams == lazily ausgewerteten Liste. Es könnte genau die Art von Selbstreferenz sein, die Sie beabsichtigt haben, aber es ist eine Art Selbstreferenz.

Also, cons-stream in SICP ist eine Syntax, die ihre Argumente zu bewerten verzögert. (cons-stream a b) kehrt sofort ohne oder b Auswertung und wertet nur a oder b, wenn Sie car-stream oder cdr-stream

Von SICP aufrufen, 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)))) 

Diese Definition besagt, dass fibs ist ein Strom beginnend mit 0 und 1, wie , dass der Rest des Streams erzeugt werden kann durch Hinzufügen von fabs zu sich selbst um einen Platz verschoben:

In diesem Fall ‚fibs‘ ist ein Objekt, dessen Wert definiert lazily hinsichtlich vergessen zu erwähnen

Almost ‚fibs‘ zugeordnet, leben lazy Ströme in den allgemein verfügbaren Bibliotheken auf SRFI-40 oder SRFI -41. Einer dieser beiden sollte in den meisten populären Schemata zur Verfügung stehen, denke ich

Answer 10

Tying the Knot (circular data structures in Haskell) auf Stackoverflow

Siehe auch die Haskell Wiki-Seite: Tying the Knot

Answer 11

ich auf diese Frage gestolpert, während für die Suche „CIRCULAR LISTEN LISP SCHEMA ". Diese

ist, wie ich kann man machen (in STk Scheme):

Zuerst

(define a '(1 2 3)) 

An dieser Stelle eine Liste machen, STk meint eine Liste ist.

(list? a) 
> #t 

nächstes gehe zum letzten Element (die 3 in diesem Fall) und die cdr ersetzen, die momentan nil mit einem Zeiger auf sich enthält.

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

Nun, STk denkt, a ist keine Liste.

(list? a) 
> #f 

(Wie es dies nicht klappt?)

Nun, wenn Sie a drucken Sie eine unendlich lange Liste von (1 2 3 1 2 3 1 2 ... finden und Sie werden das Programm töten müssen. In Stk können Sie control-z oder control-\ beenden.

Aber wofür sind Ringlisten gut?

Ich kann an obskure Beispiele für Modulo-Arithmetik denken, wie eine kreisförmige Liste der Wochentage (M T W T F S S M T W ...), oder eine kreisförmige Liste von ganzen Zahlen, die durch 3 Bits (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..) dargestellt werden.

Gibt es Beispiele aus der Praxis?