Para que listas circulares são boas para (em lisp ou esquema)?

Question

Observo que o esquema e o Lisp (eu acho) suportam listas circulares, e usei listas circulares em C/C ++ para "simplificar" a inserção e a exclusão dos elementos, mas para que são bons?

O esquema garante que eles possam ser construídos e processados, mas para quê?

Existe uma estrutura de dados 'assassina' que precisa ser circular ou circular de traseira?

Answer 1

Dizer que suporta 'Listas circulares' é um pouco demais. Você pode criar todos os tipos de estruturas de dados circulares no LISP. Como em muitas linguagens de programação. Não há muito especial sobre o LISP a esse respeito. Pegue seu livro típico de 'algoritmos e dados' e implemente qualquer estrutura de dados circulares: gráficos, anéis, ... o que alguns Lisps oferecem é que se pode imprimir e ler estruturas de dados circulares. O suporte para isso ocorre porque, em domínios típicos de programação Lisp, as estruturas de dados circulares são comuns: analisadores, expressões relacionais, redes de palavras, planos, ...

É bastante comum que as estruturas de dados contenham ciclos. 'Listas circulares reais' não são usadas com frequência. Por exemplo, pense em um agendador de tarefas que executa uma tarefa e depois de algum tempo muda para o próximo. A lista de tarefas pode ser circular para que, após a 'última tarefa', o agendador pega a tarefa "primeira". De fato, não há 'último' e 'primeiro' - é apenas uma lista circular de tarefas e o agendador as executa sem fim. Você também pode ter uma lista de Windows em um sistema de janelas e, com algum comando de chave, mudaria para a próxima janela. A lista de janelas pode ser circular.

As listas são úteis quando você precisa de uma próxima operação barata e o tamanho da estrutura de dados é desconhecido com antecedência. Você sempre pode adicionar outro nó à lista ou remover um nó de uma lista. As implementações usuais de listas tornam a obtenção do próximo nó e adicionando/removendo um item barato. Obter o próximo elemento de uma matriz também é relativamente simples (aumente o índice, no último índice, vá para o primeiro índice), mas adicionar/remover elementos geralmente precisa de operações de mudança mais caras.

Além disso, como é fácil construir estruturas de dados circulares, apenas uma pode fazê -lo durante a programação interativa. Se você imprimir uma estrutura de dados circular com as rotinas internas, seria uma boa ideia se a impressora puder lidar com ela, pois, caso contrário, poderá imprimir uma lista circular para sempre ...

Answer 2

Você já jogou monopólio?

Sem jogar jogos com contadores e Modulo e tal, como você representaria o Conselho de Monopólio em uma implementação de computador do jogo? Uma lista circular é natural.

Answer 3

Por exemplo, uma estrutura de dados de lista dupla vinculada é "circular" no ponto de vista do esquema/Lisp, ou seja, se você tentar imprimir a estrutura de structure, obtém referências, ou seja, "ciclos". Portanto, não se trata de ter estruturas de dados que se parecem com "anéis", qualquer estrutura de dados em que você tenha algum tipo de backpointers é "circular" da perspectiva do esquema/Lisp.

Uma lista Lisp "normal" é única vinculada, o que significa que uma mutação destrutiva para remover um item de dentro da lista é uma operação O (n); Para listas duplas vinculadas, é O (1). Esse é o "recurso assassino" de listas duplas vinculadas, que são "circulares" no contexto do esquema/Lisp.

Answer 4

Adicionar e remover elementos ao início de uma lista é barato. Para adicionar ou remover um elemento do final de uma lista, você deve atravessar toda a lista.

Com uma lista circular, você pode ter uma espécie de fila de comprimento fixo.

Configure uma lista circular de comprimento 5:

> (import (srfi :1 lists))
> (define q (circular-list 1 2 3 4 5))

Vamos adicionar um número à lista:

 > (set-car! q 6)

Agora, vamos fazer esse último elemento da lista:

 > (set! q (cdr q))

Exibir a lista:

 > (take q 5)
 (2 3 4 5 6)

Assim, você pode ver isso como uma fila em que os elementos entram no final da lista e são removidos da cabeça.

Vamos adicionar 7 à lista:

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

Etc ...

De qualquer forma, essa é uma maneira de usar listas circulares.

Eu uso esta técnica em um Demo OpenGL que eu portei de um exemplo no Livro de processamento.

Ed

Answer 5

Um uso de listas circulares é "repetir" os valores ao usar a versão SRFI-1 do mapa. Por exemplo, para adicionar val para cada elemento de lst, poderíamos escrever:

(map + (circular-list val) lst)

Por exemplo:

(map + (circular-list 10) (list 0 1 2 3 4 5))

Retornos:

(10 11 12 13 14 15)

Claro, você pode fazer isso substituindo + com (lambda (x) (+ x val)), mas às vezes o idioma acima pode ser mais útil. Observe que isso funciona apenas com a versão SRFI-1 do mapa, que pode aceitar listas de tamanhos diferentes.