Estructuras de datos autorreferenciales en Lisp/Scheme

Question

¿Existe alguna manera de construir una estructura de datos autorreferencial (por ejemplo, un gráfico con ciclos) en lisp o esquema? Nunca había pensado en eso antes, pero jugando no puedo encontrar una manera directa de hacerlo debido a la falta de una manera de hacer modificaciones destructivas. ¿Es esto solo un defecto esencial de los lenguajes funcionales, y si es así, qué hay acerca de los lenguajes funcionales perezosos como haskell?

Answer 1

En el esquema, puede hacerlo fácilmente con set!, set-car!, y set-cdr! (y cualquier otra cosa que termina en una explosión ('!'), lo que indica la modificación):

(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 soporta la modificación de las estructuras de datos con setf.

Puede construir una estructura de datos circular en Haskell por tying the knot.

Answer 3

En Common Lisp puede modificar contenido de la lista, contenido de la matriz, ranuras de casos Clos, etc.

Common Lisp también permite leer y escribir estructuras de datos circulares. Utilice

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

, los denominados puros lenguajes de programación funcionales no permiten efectos secundarios. La mayoría de los dialectos Lisp son no puros. Permiten efectos secundarios y permiten modificar las estructuras de datos.

Consulte los libros de introducción de Lisp para obtener más información al respecto.

Answer 4

1. No necesita 'modificación destructiva' para construir estructuras de datos autorreferenciales; por ejemplo, en Common Lisp, '#1=(#1#) es una celda de cons que se contiene a sí misma.

2. Esquema Lisp y son capaces de hacer modificaciones destructivas: se pueden construir los contras circulares anteriormente, alternativamente, como esto: (let ((x (cons nil nil))) (rplaca x x) x)

¿Puede hacernos saber qué material está utilizando, mientras que el aprendizaje de Lisp/¿Esquema? Estoy compilando una lista de objetivos para nuestros helicópteros negros; esta propagación de desinformación sobre Lisp y Scheme tiene que ser detenida.

Answer 5

ejemplo CLOS:

 
(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í, y pueden ser útiles. Uno de mis profesores de la universidad creó un tipo de esquema que llamó Medusa Numbers. Eran números de coma flotante de precisión arbitraria que podrían incluir decimales repetidos. Tenía una función:

(create-medusa numerator denominator) ; or some such 

que creaba el número de Medusa que representaba el racional. Como resultado:

(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 

como se dijo antes, esto se hace con la aplicación juiciosa de set-car! y set-cdr!

Answer 7

No solo es posible, es bastante central para el sistema de objetos Common Lisp: ¡la clase estándar es una instancia de sí mismo!

Answer 8

Volví a subir las técnicas obvias de Scheme; esta respuesta solo se dirige a Haskell.

En Haskell puede hacer esto de manera puramente funcional usando let, que se considera un buen estilo. Un buen ejemplo es la conversión de expresiones regulares a NFA. También puede hacerlo de manera imperativa con IORef s, que se considera de estilo pobre, ya que fuerza a todo su código a la mónada IO.

En general, la evaluación perezosa de Haskell se presta a implementaciones funcionales encantadoras de estructuras de datos cíclicas e infinitas. En cualquier enlace complejo let, todo lo vinculado puede utilizarse en todas las definiciones. Por ejemplo, traducir una máquina particular de estados finitos a Haskell es muy fácil, sin importar cuántos ciclos tenga.

Answer 9

Hmm, ¿no se mencionan las estructuras de datos autorreferenciales en Lisp/Scheme y las transmisiones SICP? Bueno, para resumir, las transmisiones == la lista evaluada de forma perezosa. Puede ser exactamente el tipo de autorreferencia que pretendes, pero es una especie de auto referencia.

Por lo tanto, cons-stream en SICP es una sintaxis que retrasa la evaluación de sus argumentos. (cons-stream a b) volverá inmediatamente sin evaluar aob, y sólo evalúa aob cuando se invoca car-stream o cdr-stream

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

Esta definición dice que mentiras es un la secuencia comienza con 0 y 1, tal que el resto de la secuencia puede ser generado al agregarse fibs a sí mismo desplazado por un lugar:

En este caso, 'mentiras' se le asigna un objeto cuyo valor se define con pereza en términos de 'mentiras'

olvidaba mencionar, arroyos perezosos viven en las bibliotecas comúnmente disponibles SRFI-40 o SRFI -41. Uno de estos dos deben estar disponibles en los esquemas más populares, creo que

Answer 10

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

Ver también la página de Haskell Wiki: Tying the Knot

Answer 11

me topé con esta pregunta durante la búsqueda de "listas CIRCULAR Lisp ESQUEMA ".

Esta es la forma en que puedo realizar una (STK en Scheme):

En primer lugar, hacer una lista

(define a '(1 2 3)) 

En este punto, STK piensa que a es una lista.

(list? a) 
> #t 

A continuación, ir al último elemento (del 3 en este caso) y reemplazar el cdr que contiene actualmente nil con un puntero a sí mismo.

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

Ahora, STk piensa que a no es una lista.

(list? a) 
> #f 

(¿Cómo funciona esto?)

Ahora si imprime a se encuentra un infinitamente larga lista de (1 2 3 1 2 3 1 2 ... y tendrá que cerrar el programa. En Stk puede control-z o control-\ para salir.

Pero, ¿para qué sirven las listas circulares?

puedo pensar en ejemplos oscuros que hacer con la aritmética de módulo, como una lista circular de los días de la semana (M T W T F S S M T W ...), o una lista circular de números enteros representados por 3 bits (0 1 2 3 4 5 6 7 0 1 2 3 4 5 ..).

¿Hay ejemplos del mundo real?