Las dos listas son estructuralmente iguales si poseen la misma estructura de lista, aun cuando sus elementos sean diferentes. Por lo tanto, vamos a elaborar un programa que verifica si los elementos en ambas listas, en la misma posición, son átomos o no. Si es así, debería retornar verdadero; de lo contrario, falso.
Programa:
(define (structurally-equal l1 l2)
(cond (?; si ambas listas son nulas #t)
(?; si una de las listas es nula pero la otra no #f)
(?; si la parte 'car' de ambas listas es un átomo
(structurally-equal (cdr l1) (cdr l2)))
(?; si la parte 'car' de una de las listas es un átomo pero la otra no #f)
(else
(and (structurally-equal??); recurrir sobre el 'car' de cada lista
(structurally-equal??))))); recurrir sobre el 'cdr' de cada lista
Explicación:
Existen dos maneras de abordar este problema. El primer enfoque consiste en utilizar una función que genere un resultado que represente la estructura de la lista.
1. Podríamos representar la estructura de cualquier lista como una cadena o número único, de tal forma que cualquier lista con una estructura idéntica tendría la misma representación y ninguna otra lista generaría la misma salida.
2. Escribir una función que analice la estructura de cualquier lista y genere esa salida.
3. Ejecutar ambas listas a través de la función y comparar la salida. Si son iguales, tienen la misma estructura.
El segundo enfoque, que es el utilizado por Oscar, consiste en recurrir a través de ambas listas simultáneamente. Aquí, se pasan ambas listas a una función, que realiza lo siguiente:
1. ¿Es el primer elemento de la primera lista idéntico (estructuralmente) al primer elemento de la segunda? Si no, devuelve falso.
2. ¿Son estos primeros elementos listas? Si es así, devolver el resultado de (and (recurrir en el primer elemento de ambas listas) (recurrir en el resto de ambas listas))
3. De no ser así, devolver el resultado de (recurrir en el resto de ambas listas).
El segundo enfoque es más eficiente en la circunstancia simple en la que se desea comparar dos listas. Retorna tan pronto como se encuentra una diferencia, procesando ambas listas en su totalidad solamente donde ambas listas, efectivamente, son estructuralmente idénticas.
