tree - resueltos - Definición de la estructura del árbol en Lisp

listas en lisp ejemplos

Question

Del glosario Common Lisp HyperSpec:

árbol n. 1. una estructura de datos recursiva binaria compuesta de conses y átomos: los conses también son árboles (a veces llamados "subárboles" o "ramas"), y los átomos son nodos terminales (a veces llamados hojas). Típicamente, las hojas representan datos mientras que las ramas establecen alguna relación entre esos datos. 2. en general, cualquier estructura recursiva de datos que tenga alguna noción de "ramas" y hojas.

estructura de árbol n. (de un árbol) el conjunto de conses que componen el árbol. Tenga en cuenta que aunque el componente de automóvil [1b] de cada uno de estos contras es parte de la estructura del árbol, los objetos que son los automóviles de cada uno de ellos en el árbol no son parte de la estructura de su árbol a menos que también lo sean.

La última oración en la definición de estructura de árbol plantea una pregunta, que es, ¿puede decirse lo mismo acerca de los CDD también?

El uso de la palabra binario en la definición de "árbol" parece sugerir que no hay diferencia entre automóvil y cdr para los fines de los árboles, pero la definición de "estructura de árbol" parece tratar a los automóviles como especiales, así que estoy confundido.

Answer 1

Tenga en cuenta que aunque el componente de automóvil [1b] de cada uno de estos contras es parte de la estructura del árbol, los objetos que son los automóviles de cada uno de ellos en el árbol no son parte de la estructura de su árbol a menos que también lo sean.

Hasta donde puedo ver, el autor de esta definición intenta trazar la línea entre la construcción del árbol y sus objetos. Por lo tanto, establece que solo los conceptos pueden constituir la estructura del árbol.

Considera este ejemplo:

(1 2 (3 "string") 4)

Mientras que el objeto "string" es parte del árbol (y es car de ("string") ), no es parte de la estructura de árbol, porque las cadenas no consisten en celdas cons.

Supongo que el autor de la definición tenía en mente las listas adecuadas, porque para ellos cada elemento es car :

(cons "foo" (cons "bar" (cons "baz" nil)))
;     ^car^       ^car^       ^car^

cdr más bien define la estructura del árbol en caso de una lista adecuada.

Pero también podrías considerar lo siguiente como árbol:

("foo" . "bar")

En este caso, cdr no sería parte de la estructura de árbol.

Answer 2

Respuesta corta

La última oración en la definición de estructura de árbol plantea una pregunta, que es, ¿puede decirse lo mismo acerca de los CDD también?

Creo que la respuesta es sí." Hay una definición similar para la estructura de la lista con una redacción casi idéntica. Hay más posibilidades de confusión sobre la estructura de la lista sobre si el valor de un coche de contras es parte de la estructura de la lista, ya que las preguntas pueden tratarse, por ejemplo, "¿qué significa reemplazar X en la lista (X (X) Y)? " El cdr no está realmente en duda, ya que el cdr es el resto de la lista; es obviamente parte de la estructura de la lista.

Para la estructura del árbol , creo que hay menos ambigüedad; contras en el coche o el cdr es un subárbol. Las definiciones de estructura de árbol y lista son casi idénticas en algunos lugares, y no me sorprendería que alguien escribiera la definición de estructura de lista y luego la copiara para la estructura de árbol , haciendo que el número mínimo de cambios sea preciso. Eso dejaría la parte de autos allí, aunque la pregunta que responde probablemente no surja en la práctica.

Respuesta más larga

Veamos la definición de estructura de listas y compare:

lista estructura n. (de una lista) el conjunto de conceptos que componen la lista. Tenga en cuenta que aunque el componente automóvil de cada uno de estos contras es parte de la estructura de la lista, los objetos que son elementos de la lista (es decir, los objetos que son los coches de cada uno de los contras en la lista) no son parte de su estructura de listas. incluso si son conses, excepto en el caso (circular) donde la lista contiene realmente una de sus colas como un elemento. (La estructura de listas de una lista se denomina a veces redundantemente como su "estructura de lista de nivel superior" para enfatizar que no se trata de ninguna consigna que sea un elemento de la lista).

Tenga en cuenta los lugares específicos donde estos difieren:

(Estructura de lista) Tenga en cuenta que aunque el componente de automóvil de cada uno de estos contras es parte de la estructura de lista, los objetos que son elementos de la lista (es decir, los objetos que son los coches de cada uno de ellos en la lista) no son parte de la lista su estructura de lista, incluso si son conses.

(Estructura de árbol) Tenga en cuenta que aunque el componente de automóvil de cada uno de estos contras es parte de la estructura del árbol, los objetos que son los coches de cada uno de ellos en el árbol no son parte de la estructura de árbol a menos que también sean consensos.

Eso significa que en

(1 (2) 3) == (cons 1 (cons (cons 2 nil) (cons 3 nil)))

hay tres celdas cons en la estructura de la lista, y cuatro celdas cons en la estructura del árbol.

¿Dónde realmente importa esto? Es importante definir estos términos de forma precisa para que la especificación pueda definir fácilmente qué partes de una lista o árbol son atravesadas o modificadas por funciones particulares.

nsubst puede modificar la estructura del árbol

Por ejemplo, las funciones nsubst y friends , cuya documentación indica:

nsubst, nsubst-if y nsubst-if-not pueden alterar la estructura de árbol del árbol.

Una definición específica de estructura de árbol nos permite comprender qué cosas pueden o no pueden ser cambiadas por nsubst .

estructura de árbol n. (de un árbol) el conjunto de conses que componen el árbol. Tenga en cuenta que si bien el componente de automóvil de cada uno de estos contras es parte de la estructura del árbol, los objetos que son los automóviles de cada uno de ellos en el árbol no son parte de la estructura de árbol, a menos que también lo sean.

Entonces, lo que esto nos dice es que para cualquier cons cell x en el árbol, nsubst podría hacer (setf (car x) ...) , de modo que el (carro x) podría ser algo diferente más adelante, pero no modificará el objeto real que sería devuelto por (carro x) (a menos que sea un inconveniente, por supuesto). Esto podría ser importante en casos donde el valor de (carro x) es un objeto que podría tener árboles dentro de él. Entonces, por ejemplo, nsubst no descenderá en vectores, pero reemplazará vectores:

(let* ((l (list 1 2 3))     ; a list
       (v (vector 0 l 4))   ; a vector that contains the list (and other elements)
       (tree (cons l v)))   ; a tree containing the list and the vector
  (nsubst ''x l tree))       ; replace the list in the tree with X
;=> (X . #(0 (1 2 3) 4))    ; nsubst doesn''t descend into the vector, because it''s
                            ; not tree structure

eliminar-duplicados puede modificar la estructura de la lista

Por otro lado, delete-duplicates solo modificará la estructura de la lista:

eliminar-duplicados, cuando la secuencia es una lista, se permite establecer cualquier parte, carro o cdr, de la estructura de la lista de nivel superior en esa secuencia. Cuando la secuencia es un vector, se permite que delete-duplicates cambie las dimensiones del vector y deslice sus elementos en nuevas posiciones sin permutarlos para producir el vector resultante.