Structures de données auto-référentielles dans le Lisp / Scheme

dans le Lisp commun vous pouvez modifier le contenu de la liste, le contenu du tableau, les fentes des instances de CLOS, etc.

Common Lisp permet également de lire et d'écrire des structures de données circulaires. Utilisez

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

soi-disant pure les langages de programmation fonctionnels ne permettent pas les effets secondaires. La plupart des dialectes du Lisp sont pure. Ils permettent des effets secondaires et permettent de modifier les structures de données.

voir les livres D'introduction du Lisp pour plus de détails à ce sujet.

dans Scheme, vous pouvez le faire facilement avec set!,set-car! et set-cdr! (et rien d'autre, se terminant dans un bang ('!'), qui indique modification):

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

Common Lisp supporte la modification des structures de données avec setf.

Vous pouvez construire une structure de données circulaire dans Haskell par d'attacher le noeud.

1. vous n'avez pas besoin de 'modification destructive' pour construire des structures de données auto-référentielles; par exemple, dans le Lisp commun,'#1=(#1#) est une contre-cellule qui se contient elle-même.

2. Scheme et Lisp sont capables de faire des modifications destructives: vous pouvez construire les cons circulaires ci-dessus alternativement comme ceci: (let ((x (cons nil nil))) (rplaca x x) x)

pouvez-vous nous dire quel matériel vous utilisez pour apprendre le Lisp/Scheme? Je compile une liste de cibles pour nos hélicoptères noirs; cette propagation de la désinformation sur le Lisp et le schéma doit être stoppée.

Oui, et ils peuvent être utiles. Un de mes professeurs d'université a créé un type de schéma qu'il a appelé les nombres de Méduse. Il s'agissait de nombres flottants de précision arbitraires qui pouvaient inclure la répétition de décimales. Il avait une fonction:

(create-medusa numerator denominator) ; or some such

qui a créé le nombre Méduse qui a représenté le rationnel. Comme résultat:

(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

comme dit plus haut, ceci est fait avec l'application judicieuse de set-car! et set-cdr!

non seulement c'est possible, c'est assez central dans le système D'objets Lisp: la classe standard est une instance de lui-même!

je upvoted l'évidence Régime techniques; cette réponse ne traite que Haskell.

dans Haskell vous pouvez faire ceci purement fonctionnellement en utilisant let, qui est considéré comme un bon style. Un bel exemple est la conversion regexp-en-NFA. Vous pouvez également le faire impérativement en utilisant IORef s, qui est considéré comme de mauvais style car il force tout votre code dans la monade IO.

en général, L'évaluation paresseuse de Haskell se prête à de jolies implémentations fonctionnelles des systèmes cycliques et structures de données infinies. Dans n'importe quel complexe let liaison, toutes les choses liées peuvent être utilisés dans toutes les définitions. Par exemple, traduire une machine à état fini en Haskell est un claquement, peu importe le nombre de cycles qu'elle peut avoir.

CLOS exemple:

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

attacher le noeud (structures de données circulaires à Haskell) sur StackOverflow

Voir aussi la page Wiki de Haskell: attacher le noeud

Hmm, auto-référentiel des structures de données en Lisp/Scheme, et SICP les flux ne sont pas mentionnés? En résumé, streams = = liste évaluée paresseusement. C'est peut-être le genre d'auto-référence que vous avez voulu, mais c'est une sorte d'auto-référence.

Donc, cons-stream dans SICP est une syntaxe qui retarde l'évaluation de ses arguments. (cons-stream a b) retourne immédiatement, sans évaluer a ou b, et évalue seulement a ou b lorsque vous appelez car-stream ou cdr-stream

à Partir de 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))))

Cette définition dit que bobards est un flux commençant par 0 et 1, tel que que le reste du ruisseau peut être généré par l'ajout de fibres à lui-même déplacé en un seul endroit:

dans ce cas, 'fibs' est assigné à un objet dont la valeur est définie par Fibs en termes de 'fibs'

presque oublié de mentionner, les cours d'eau paresseux vivent sur dans les bibliothèques disponibles: SRFI-40 ou SRFI-41. Un de ces deux devrait être disponible dans la plupart des régimes populaires, je pense

je suis tombé sur cette question en cherchant "CIRCULAR listes LISP SCHEME".

C'est comment je peux faire (STk):

tout d'abord, faites une liste

(define a '(1 2 3))

À ce stade, STk pense un une liste.

(list? a)
> #t

Ensuite, allez dans le dernier élément (3 dans ce cas), et remplacer le cdr qui contient actuellement nil avec un pointeur à lui-même.

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

maintenant, STk pense que a n'est pas un liste.

(list? a)
> #f

(Comment ça marche?)

Maintenant, si vous imprimez a vous trouverez une liste infinie de (1 2 3 1 2 3 1 2 ... et vous aurez besoin de tuer le programme. Dans Stk vous pouvez control-z ou control-\ pour arrêter de fumer.

mais à quoi servent les listes circulaires?

je ne peux penser à d'obscurs exemples à voir avec l'arithmétique modulo comme une circulaire de la liste des jours de la semaine (M T W T F S S M T W ...), ou une liste circulaire d'entiers représentés par 3 bits (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..).

y a-t-il des exemples concrets?