Strutture dati autoreferenziali in Lisp/Scheme

Question

Esiste un modo per costruire una struttura di dati autoreferenziale (ad esempio un grafico con cicli) in lisp o schema? Non ci avevo mai pensato prima, ma giocando non riesco a trovare un modo semplice per crearne uno a causa della mancanza di un modo per apportare modifiche distruttive. Questo è solo un difetto essenziale dei linguaggi funzionali, e se sì, che dire dei linguaggi funzionali pigri come haskell?

Answer 1

In Scheme, lo si può fare facilmente con set!, set-car!, e set-cdr! (e qualsiasi altra cosa che termina in un botto ('!'), che indica la modifica):

(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 supporta modifica delle strutture di dati con setf.

È possibile creare una struttura dati circolare in Haskell entro tying the knot.

Answer 3

In Common Lisp è possibile modificare il contenuto della lista, il contenuto di array, slot di istanze CLOS, ecc

Common Lisp permette anche di leggere e scrivere le strutture di dati circolari. Utilizzare

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

cosiddetto puri funzionale Linguaggi di programmazione non permettono effetti collaterali. La maggior parte dei dialoghi Lisp è non puro. Consentono effetti collaterali e consentono di modificare le strutture dei dati.

Vedere libri introduttivi Lisp per ulteriori informazioni.

Answer 4

1. Non è necessario "modifica distruttiva" per costruire strutture di dati autoreferenziali; ad esempio, in Common Lisp, '#1=(#1#) è una cella di controllo che contiene se stessa.

2. Scheme e Lisp sono in grado di apportare modifiche distruttive: è possibile costruire il cons circolari sopra alternativamente come questo: (let ((x (cons nil nil))) (rplaca x x) x)

Puoi farci sapere quale materiale che si sta utilizzando, mentre l'apprendimento Lisp/Schema? Sto compilando una lista di obiettivi per i nostri elicotteri neri; questa diffusione della disinformazione su Lisp e Scheme deve essere fermata.

Answer 5

CLOS esempio:

 
(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

Sì, e possono essere utili. Uno dei miei professori universitari ha creato un tipo Scheme che ha chiamato Medusa Numbers. Erano numeri arbitrari di virgola mobile di precisione che potevano includere numeri decimali ripetuti. Aveva una funzione:

(create-medusa numerator denominator) ; or some such 

che ha creato il numero di Medusa che rappresentava il razionale. Come risultato:

(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 

come detto prima, questo viene fatto con applicazione giudiziosa di set-car! e set-cdr!

Answer 7

Non solo è possibile, è piuttosto centrale per il Common Lisp Object System: la classe standard è un'istanza di per sé!

Answer 8

Ho svalutato le ovvie tecniche Scheme; questa risposta si rivolge solo a Haskell.

In Haskell si può fare questo puramente funzionalmente utilizzando let, che è considerato di buon stile. Un buon esempio è la conversione regexp-to-NFA. Puoi anche farlo imperativamente usando IORef s, che è considerato di cattivo gusto in quanto forza tutto il tuo codice nella monade IO.

In generale, la valutazione lenta di Haskell si presta a implementazioni funzionali incantevoli di strutture dati cicliche e infinite. In qualsiasi complesso let associazione, tutte le cose legate possono essere utilizzate in tutte le definizioni. Ad esempio, tradurre una particolare macchina a stati finiti in Haskell è un gioco da ragazzi, indipendentemente dal numero di cicli che può avere.

Answer 9

Hmm, strutture di dati autoreferenziali in Lisp/Scheme e flussi SICP non sono menzionati? Bene, per riassumere, flussi == lista ponderata ponderata. Potrebbe essere esattamente il tipo di riferimento personale che hai inteso, ma è una sorta di auto-riferimento.

Quindi, cons-stream in SICP è una sintassi che ritarda la valutazione dei suoi argomenti. (cons-stream a b) restituirà immediatamente senza valutare a o b, e valuta solo o b quando si richiama car-stream o cdr-stream

Da 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)))) 

Questa definizione dice che bugie è un flusso che inizia con 0 e 1, tale che il resto del flusso può essere generato aggiungendo fibs a se stesso spostato di un posto:

In questo caso, 'fibs' viene assegnato un oggetto il cui valore è definito pigramente in termini di 'fibs'

Quasi dimenticato di menzionare, flussi pigri vivono nelle librerie di comune reperibilità SRFI-40 o SRFI -41. Uno di questi due dovrebbero essere disponibili in Organismi più popolari, penso

Answer 10

Tying the Knot (circular data structures in Haskell) su StackOverflow

Vedere anche la pagina Haskell Wiki: Tying the Knot

Answer 11

sono incappato in questo problema durante la ricerca di "liste circolari Lisp SCHEMA ".

Questo è come posso fare una (in STK Scheme):

In primo luogo, fare una lista

(define a '(1 2 3)) 

A questo punto, stk pensa a è una lista.

(list? a) 
> #t 

Andare quindi l'ultimo elemento (la 3 in questo caso) e sostituire il cdr che contiene attualmente nil con un puntatore a se stesso.

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

Ora, STk ritiene che non sia un elenco.

(list? a) 
> #f 

(Come funziona questo fuori?)

Ora se si stampa a troverete infinitamente lunga lista di (1 2 3 1 2 3 1 2 ... e sarà necessario per uccidere il programma. In Stk puoi control-z o control-\ per uscire.

Ma a cosa servono le liste circolari?

Mi vengono in mente esempi oscuri da eseguire con l'aritmetica modulo come un elenco circolare dei giorni della settimana (M T W T F S S M T W ...) o un elenco circolare di numeri interi rappresentati da 3 bit (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..).

Esistono esempi reali?