Observo que Scheme y Lisp (supongo) admiten listas circulares, y he usado listas circulares en C/C++ para 'simplificar' la inserción y eliminación de elementos, pero ¿para qué sirven?¿Para qué sirven las listas circulares (en Lisp o Scheme)?
Scheme asegura que se pueden construir y procesar, pero ¿para qué?
¿Existe una estructura de datos "asesina" que debe ser circular o de cola circular?
Decir que es compatible con 'listas circulares' es un poco demasiado. Puede construir todo tipo de estructuras de datos circulares en Lisp. Como en muchos lenguajes de programación. No hay mucho especial sobre Lisp a este respecto. Tome su libro típico 'Algorithms and Datastructure' e implemente cualquier estructura circular de datos: gráficos, anillos, ... Lo que algunos Lisps ofrecen es que uno puede imprimir y leer estructuras de datos circulares. El soporte para esto es porque en los típicos dominios de programación Lisp las estructuras de datos circulares son comunes: analizadores, expresiones relacionales, redes de palabras, planos, ...
Es bastante común que las estructuras de datos contengan ciclos. Las 'listas circulares' reales no son tan usadas. Por ejemplo, piense en un programador de tareas que ejecuta una tarea y luego de un tiempo pasa al siguiente. La lista de tareas puede ser circular para que después de la "última" tarea el planificador tome la "primera" tarea. De hecho, no hay "último" y "primer", es solo una lista circular de tareas y el planificador las ejecuta sin fin. También podría tener una lista de ventanas en un sistema de ventanas y con algunos comandos de tecla cambiaría a la siguiente ventana. La lista de ventanas podría ser circular.
Las listas son útiles cuando necesita una próxima operación barata y el tamaño de la estructura de datos se desconoce de antemano. Siempre puede agregar otro nodo a la lista o eliminar un nodo de una lista. Las implementaciones habituales de listas hacen que obtener el siguiente nodo y agregar/eliminar un elemento sea barato. Obtener el siguiente elemento de una matriz también es relativamente simple (aumentar el índice, en el último índice ir al primer índice), pero agregar/eliminar elementos generalmente requiere operaciones de cambio más costosas.
Además, dado que es fácil construir estructuras de datos circulares, uno podría hacerlo durante la programación interactiva. Si luego imprime una estructura de datos circular con las rutinas incorporadas, sería una buena idea si la impresora puede manejarlo, ya que de lo contrario puede imprimir una lista circular para siempre ...
Con 'asistencia' me refería a la sintaxis específica para describir listas circulares para leer y escribir (como dices). p.ej. '(# 0 = (1 2) (x y. # 0 #))'; también el predicado 'list?' del esquema especifica que una lista circular no es una lista, ¿o es esta implementación específica? – philcolbourn
Ok, puedo ver que un programador de tareas es una lista circular. Un buen ejemplo. En LISP o Scheme, ¿cómo insertarías o eliminarías una tarea? – philcolbourn
@philcolbourn La sintaxis específica que menciona funciona en Lisp para todo tipo de estructuras de datos con ciclos. No solo listas circulares. Puede usar operaciones de listas destructivas para agregar un objeto a una lista circular. Es un ejercicio de programación típico en Lisp y/o cursos de programación ... –
Por ejemplo, una estructura de datos de lista de doble enlace es "circular" en el punto de vista Esquema/LISP, es decir, si intenta imprimir la estructura de contras, obtendrá referencias, es decir, "ciclos". Por lo tanto, no se trata de tener estructuras de datos que parecen "anillos", cualquier estructura de datos donde tenga algún tipo de contratipo es "circular" desde la perspectiva del Esquema/LISP.
Una lista LISP "normal" tiene un solo enlace, lo que significa que una mutación destructiva para eliminar un elemento de la lista es una operación O (n); para las listas de doble enlace es O (1). Esa es la "característica principal" de las listas de doble enlace, que son "circulares" en el contexto del Esquema/LISP.
Usted dice que las listas LISP 'normales' tienen un solo enlace, lo entiendo. ¿Pero también está diciendo que las listas circulares en LISP/Scheme están doblemente vinculadas? – philcolbourn
Creo que lo que estaba diciendo era "si tienes una lista de doble enlace, es circular". En el lenguaje de lisp/esquema, una lista circular solo significa que hay al menos una referencia más abajo en la lista para al menos una celda más cercana al comienzo. – Vatine
Sí, él está diciendo que las listas doblemente enlazadas cumplen con los requisitos para ser 'circular'. – Cam
¿Alguna vez ha jugado Monopoly?
Sin jugar juegos con contadores y módulo y tal, ¿cómo representarías al tablero de Monopoly en una implementación de computadora del juego? Una lista circular es un natural.
'¿cómo representarías al tablero de Monopoly en una implementación de computadora del juego?' ... Como una matriz, para que no tenga que repetir cada cuadrado de la tabla en cada movimiento. – Cam
Para ser honesto, solo mantendría un puntero al cuadrado actual, por lo que no tendría que hacerlo. –
Con una lista regular, debería escribir lógica para indicarle a la posición en la matriz que se mueva de principio a fin. Con una lista circular, simplemente usaría la misma lógica sin importar qué: mueva las posiciones X de la actual. La lista circular de hecho sería algo natural aquí. – Dave
Agregar y quitar elementos al comienzo de una lista es barato. Para agregar o quitar un elemento del final de una lista, debe atravesar toda la lista.
Con una lista circular, puede tener un tipo de cola de longitud fija.
instalación de una lista circular de longitud 5:
> (import (srfi :1 lists))
> (define q (circular-list 1 2 3 4 5))
Vamos a añadir un número a la lista:
> (set-car! q 6)
Ahora, vamos a hacer que el último elemento de la lista:
> (set! q (cdr q))
Mostrar la lista:
> (take q 5)
(2 3 4 5 6)
Para que pueda ver esto como una cola donde los elementos entran al final de la lista y se eliminan del encabezado.
Vamos a añadir a la lista 7:
> (set-car! q 7)
> (set! q (cdr q))
> (take q 5)
(3 4 5 6 7)
Etc ...
De todas formas, esta es una manera que he utilizado las listas circulares.
Utilizo esta técnica en un OpenGL demo que porté de un ejemplo en el Processing book.
Ed
¿No sería más fácil usar una matriz para esto? – philcolbourn
Un uso de listas circulares es "repetir" valores cuando se utiliza la versión SrfI-1 de mapa. Por ejemplo, para agregar val a cada elemento de lst, podríamos escribir:
(map + (circular-list val) lst)
Por ejemplo:
(map + (circular-list 10) (list 0 1 2 3 4 5))
devuelve:
(10 11 12 13 14 15)
Por supuesto, se puede hacer esto mediante la reemplazando + con (lambda (x) (+ x val)), pero a veces la expresión anterior puede ser más útil. Tenga en cuenta que esto solo funciona con la versión srfi-1 del mapa, que puede aceptar listas de diferentes tamaños.
He aprendido que el modelo de entorno de Scheme requiere (¿demasiado fuerte?) Listas circulares: un procedimiento asignado en un entorno 'puntos' a su entorno: una lista circular. – philcolbourn