¿Cuáles son las listas circular bueno para (en Lisp o Scheme)?

Question

observo que el Esquema y Lisp (supongo) de apoyo listas circulares, y he utilizado listas circulares en C / C ++ para 'simplificar' la inserción y eliminación de elementos, pero lo que son buenas?

asegura esquema que se pueden construir y procesado, pero para qué?

¿Hay una estructura de datos 'asesino' que necesita ser circular o de cola circular?

Answer 1

diciendo que apoya los 'listas circulares' es un poco mucho. Usted puede construir todo tipo de estructuras circulares de datos en Lisp. Al igual que en muchos lenguajes de programación. No hay mucho de especial en Lisp a este respecto. Tome su libro 'Algoritmos y estructura de datos' típico e implementar cualquier estructura circular de datos: gráficos, anillos, ... Lo que algunos ofrecen Lisps es que se puede imprimir y leer estructuras de datos circulares. El apoyo de esto es porque en dominios típicos de programación Lisp estructuras circulares de datos comunes son: programas de análisis, expresiones relacionales, redes de palabras, planes, ...

Es bastante común que las estructuras de datos contienen ciclos. Reales '' listas circulares que no son de uso frecuente. Por ejemplo pensar en un programador de tareas que se ejecuta una tarea y después de algún tiempo cambia a la siguiente. La lista de tareas puede ser tan circular que después de la tarea 'última' el programador toma la 'primera' tarea. De hecho no hay un 'último' y 'primero' - es sólo una lista circular de las tareas y el planificador de ellas se ejecuta sin fin. También podría tener una lista de ventanas en un sistema de ventana y con un poco de comando de teclado que le pasará a la siguiente ventana. La lista de ventanas podría ser circular.

Las listas son útiles cuando se necesita una próxima operación barata y el tamaño de la estructura de datos es desconocido de antemano. Siempre se puede añadir otro nodo a la lista o eliminar un nodo de una lista. implementaciones habituales de las listas, los desplazamientos al siguiente nodo y la adición / eliminación de un elemento barato. Obtener el siguiente elemento de una matriz también es relativamente simple (aumentar el índice, en el último índice de ir al primer índice), pero la adición / eliminación de elementos por lo general necesita operaciones de desplazamiento más caros.

Además, ya que es fácil de construir estructuras de datos circulares, uno sólo puede hacerlo durante la programación interactiva. Si a continuación, imprime una estructura de datos circular con el incorporado en las rutinas que sería una buena idea si la impresora puede manejar la situación, ya que de lo contrario puede imprimir una lista circular para siempre ...

Answer 2

¿Alguna vez ha jugado al Monopoly?

Sin jugar juegos con los contadores y de módulo y tal, ¿cómo representar el tablero de Monopoly en una aplicación de ordenador del juego? Una lista circular es un producto natural.

Answer 3

Por ejemplo, una estructura de datos de lista enlazada es doble "circular" en el punto de vista, es decir, Esquema / LISP si intenta imprimir el contra-estructura cabo a obtener referencias hacia atrás, "ciclos" es decir. Así que no es realmente acerca de tener estructuras de datos que se ven como "anillos", cualquier estructura de datos donde se tiene algún tipo de backpointers es "circular" desde la perspectiva de los Regímenes / LISP.

Una lista LISP "normal" es única vinculada, lo que significa que una mutación destructivo para eliminar un elemento desde dentro de la lista es un O (n) la operación; para las listas de dobles enlaces es O (1). Esa es la "función única" de las listas enlazadas dobles, que son "circular" en el contexto de los Regímenes / LISP.

Answer 4

Añadir y eliminar elementos al principio de una lista es barato. A añadir o eliminar un elemento de la final de la lista, usted tiene que atravesar toda la lista.

Con una lista circular, puede tener una especie de cola de longitud fija.

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

Así se puede ver esto como una cola donde los elementos entran al final de la lista y se quitan de la cabeza.

Vamos a añadir a la lista de 7:

> (set-car! q 7)
> (set!     q (cdr q))
> (take q 5)
(3 4 5 6 7)

etc ...

En cualquier caso, esta es una manera que he utilizado las listas circulares.

Me utilizar esta técnica en un OpenGL demostración cuales porté de un ejemplo en el Procesamiento libro .

Ed

Answer 5

Un uso de listas circulares es a valores de "repetición" 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))

retornos:

(10 11 12 13 14 15)

Por supuesto, usted puede hacer esto mediante la sustitución de + con (lambda (x) (+ x val)), pero a veces por encima de la expresión idiomática puede ser más práctico. Tenga en cuenta que esto sólo funciona con la versión SrfI-1 de mapa, que puede aceptar listas de diferentes tamaños.