Download Cómo diseñar programas

PARTE III
Más en procesamiento de datos
arbitrariamente grandes
SECCIÓN 14
Más definiciones auto-referenciales de datos
Muchas clases de datos pueden requerir definiciones más complejas que las definiciones autoreferenciales de listas y números. La definiciones de datos de ambos consisten en dos cláusulas;
ambos tienen una sola auto-referencia. Sin embargo, muchas clases de datos interesantes requieren
definiciones más complejas. De hecho, al respecto no hay límte a las variaciones. Es necesario
aprender a formular definiciones de datos a voluntad, el punto de partida de éstas son las
descripciones informales de la información. Una vez que se tienen, se puede seguir una receta de
diseño ligeramente modificada para definiciones de datos auto-referenciales.
14.1 Estructuras en estructuras
Los investigadores médicos se apoyan en árboles familiares (genealógicos) para investigar males
hereditarios. Por ejemplo, buscar en un árbol genealógico un cierto color de ojos. Dicha tarea
puede auxiliarse del cómputo, de ahí que sea natural representar árboles familiares y funciones
para realizar dicho procesamiento.
Una forma de mantener un árbol familiar es añadir un nodo al árbol cada vez que nace un niño.
Desde este nodo se pueden dibujar conexiones a los nodos del padre y de la madre, lo cual muestra
cómo se relaciona la gente en el árbol. Para los individuos cuyos padres se desconocen, no se
dibuja ninguna conexión, resultando lo que se denomina un árbol familiar de ancestros, pues para
cualquier nodo en el árbol, se puede encontrar los ancestros de la persona si seguimos las flechas,
pero no los descendientes.
Al mismo tiempo que se registra el árbol familiar, se pueden registrar ciertas piezas de
información: la fecha de nacimiento, el peso al nacer, el color de los ojos, o el color del pelo, entre
otros.
En cuanto a dibujar un árbol de ancestros familiares véase la figura 35. Adam es el hijo de Bettina
y Carl, tiene ojos amarillos, y nació en 1950. De forma similar Gustav es el hijo de Eva y Fred,
tiene ojos cafés, y nació en 1988. Para representar un niño en el árbol familiar se necesita
191
combinar diversas piezas de información: el padre, la madre, el nombre, la fecha de nacimiento, y
el color de los ojos. Lo que sugiere definir una nueva estructura:
(define-struct hijo (padre madre nombre fecha ojos))
Carl (1926)
Eyes: green
Bettina (1926)
Eyes: green
Adam (1950)
Eyes: yellow
Dave (1955)
Eyes: black
Eva (1965)
Eyes: blue
Fred (1966)
Eyes: pink
Gustav (1988)
Eyes: brown
Figura 35. Un ejemplo de árbol familiar de ancestros
Los cinco campos de estructuras hijo registan la información necesaria, la cual sugiere la siguiente
definición de datos:
Una estructura hijo:
(make-hijo p m n f o)
Donde p y m son estructuras hijo; n y o son símbolos, y f es número
Si bien esta definición de datos es simple, no sirve. La definición se refiere a sí misma, pero
debido a que no tiene alguna cláusula, no existe forma de crear una estructura hijo. Si trataramos
de crear una estructura hijo, tendríamos que escribir
(make-hijo
(make-hijo
(make-hijo
(make-hijo
...
)))
... ... ... ...)
192
sin parar. Por esa razón se requiere que toda definición de datos auto-referencial consista en varias
cláusulas (por ahora) y que cuando menos una de ellas no se refiera a la definición de datos.
Si se pospone la definición de datos por un momento y se estudia en su lugar cómo emplear
estructuras hijo para representar árboles familiares. Supóngase que se requiere añadir un hijo a un
árbol familiar existente, que además se tienen ya representaciones de los padres. Por ejemplo, para
Adam se podría crear la siguiente estructura:
(make-hijo Carl Bettina 'Adam 1950 'yellow)
Suponiendo que Carl y Bettina representan a los padres de Adam.
El problema es que no siempre se conocen los padres de una persona. En la familia representada
de la figura 35, no se conocen los padres de Bettina. Por lo que a pesar de que no se conozcan el
padre o la madre de una persona, se debe emplear algún valor Scheme para los dos campos
correspondientes de la estructura hijo. Se podrían emplear todo tipo de valores para indicar la
carencia de información (5, false, o ‘ninguno); aquí se emplea empty. Por ejemplo, para construir
una estructura hijo para Bettina, se hace lo siguiente:
(make-hijo empty empty 'Bettina 1926 'green)
Por supuesto, si sólo uno de los padres falta, se llena el campo correspondiente con empty.
El análisis sugiere que un nodo hijo tiene la siguiente definición de datos:
Un nodo hijo es (make-hijo p m n f o) donde
1. p y m son cualquiera de
a. empty o
b. nodos hijo;
2. n y o son símbolos;
3. f es un número.
Esta definición es especial en dos aspectos. Primero, es una definición de datos auto-referencial
que involucra estructuras. Segundo, la definición de datos menciona dos opciones para el primer
y el segundo componente. Lo que viola las convenciones relacionadas con la forma de las
definiciones de datos.
Se puede evitar ese problema al optar por definir la colección de nodos en un árbol familiar.
Un nodo-árbol-familiar, naf, es cualquiera de
1. empty, o
193
2. (make-hijo padre madre nombre fecha ojos)
donde p y m son nafs, n y o son símbolos, y f es un número.
Esta nueva definición satisface las convenciones. Consiste de dos cláusulas. Una de las cláusulas
es auto-referencial, la otra no.
En contraste con las definiciones de datos previas relacionadas con estructuras, la definición de
naf no es una explicación directa de qué clase de datos se muestran en cada campo. En su lugar, se
tiene una multicláusulas y auto-referencial. Considerándose que está es la primera de tales
definiciones, al traducir cuidadosamente el ejemplo de la figura 35, se garantiza que la nueva clase
de datos puede representar la información de interés.
La información para Carl es fácil de traducir a un naf:
(make-hijo empty empty 'Carl 1926 'green)
Bettina y Fred se representan con nodos similares. A su vez, el nodo para Adam se crea con
(make-hijo (make-hijo empty empty 'Carl 1926 'green)
(make-hijo empty empty 'Bettina 1926 'green)
'Adam
1950
'yellow)
Como muestran los ejemplos, una transliteración simple nodo-por-nodo de la figura 35 requiere
numerosas repeticiones de datos. Por ejemplo, si se construye la estructura hijo para Dave como la
de Adam, se obtiene
(make-hijo (make-hijo empty empty 'Carl 1926 'green)
(make-hijo empty empty 'Bettina 1926 'green)
'Dave
1955
'black)
De ahí que sea una buena idea introducir una definición de variable por nodo y emplearla después.
Para facilitar las cosas, se emplea Carl para representar la estructura hijo que describe Carl, etc. La
transliteración completa del árbol familiar en Scheme se encuentra en la figura 36.
Las definiciones de estructura en la figura 36 corresponden naturalemente a una imagen de cajas
anidadas profundamente. Cada caja contiene cinco compartimentos. Las primeras dos contienen a
su vez cajas, las cuales contienen cajas en sus dos primeros compartimentos, etc. De ahí que si se
dibujaran las definiciones de estructura para el árbol familiar empleando cajas anidadas,
194
rápidamente quedaríamos abrumados por los detalles del dibujo. Es más, el dibujo copiaría ciertas
porciones del árbol de la misma forma que nuestro intento de emplear make-hijo sin definiciones
de variable. Por dichas razones, es mejor imaginar las estructuras como cajas y flechas, como
originalmente se dibujaron en la figura 35. En general, un programador debe ir y venir
flexiblemente entre dichas ilustraciones gráficas. Para extraer valores de estructuras, la imagen de
cajas-en-cajas opera mejor; para descubrir cómo operar grandes colecciones de estructuras
interconectadas, la imagen cajas-y-flechas opera mejor.
;; Generación mayor:
(define Carl (make-hijo empty empty 'Carl 1926 'green))
(define Bettina (make-hijo empty empty 'Bettina 1926 'green))
;; Generación intermedia:
(define Adam (make-hijo Carl Bettina 'Adam 1950 'yellow))
(define Dave (make-hijo Carl Bettina 'Dave 1955 'black))
(define Eva (make-hijo Carl Bettina 'Eva 1965 'blue))
(define Fred (make-hijo empty empty 'Fred 1966 'pink))
;; Generación más joven:
(define Gustav (make-hijo Fred Eva 'Gustav 1988 'brown))
Figura 36. Una representación Scheme del árbol familiar de muestra
Una vez que se dispone de una comprensión clara de la representación de árboles familiares, se
puede iniciar el diseño de funciones que consumen nafs. Considérese inicialmente una función
genérica de este tipo:
;; fun-para-naf : naf -> ???
(define (fun-para-naf un-árbol) ...)
Después de todo, se debe poder construir el formato sin tener que considerar el propósito de la
función.
Puesto que la definición de datos de nafs contiene dos cláusulas, el formato debe consistir de una
cond-expresión con dos cláusulas. La primera opera con empty , la segunda con estructuras hijo:
; fun-para-naf : naf -> ???
(define (fun-para-naf un-árbol)
(cond
[(empty? un-árbol) ...]
[else ; (hijo? naf)
...]))
195
Es más, para la primera cláusula, la entrada es atómica de ahí que no se requiera nada adicional.
Para la segunda cláusula, sin embargo, la entrada contiene cinco piezas de información: dos nodos
de árbol familiar adicionales, el nombre de la persona, la fecha de nacimiento, y el color de ojos:
; fun-para-naf : naf -> ???
(define (fun-para-naf un-árbol)
(cond
[(empty? un-árbol) ...]
[else
... (fun-para-naf (hijo-padre un-árbol)) ...
... (fun-para-naf (hijo-madre un-árbol)) ...
... (hijo-nombre un-árbol) ...
... (hijo-fecha un-árbol) ...
... (hijo-ojos un-árbol) ...]))
Aplicándose fun-para-naf a los campos del padre y la madre debido a auto-referencias en la
segunda cláusula de la definición de datos.
Si volvemos a un ejemplo concreto de función ancestro-ojo-azul?, la función que determina si
alguien en un árbol familiar tiene ojos azules:
;; ancestro-ojo-azul? : naf -> booleano
;; determinar si un-árbol contiene una estructura hijo con ´azul en el campo ojos
(define (ancestro-ojo-azul? un-árbol) ...)
Siguiendo la receta, se desarrollan algunos ejemplos. Considérese el nodo de árbol familiar para
Carl. No tiene ojos azules, y debido a que no tiene ningún ancestro conocido en el árbol familiar,
el árbol familiar representado por dicho nodo no contiene una persona con ojos azules. De ahí que
(ancestro-ojo-azul? Carl)
devuelve false. En cambio, el árbol familiar representado por Gustav contiene un nodo para Eva
quien tiene ojos azules. Por lo que
(ancestro-ojo-azul? Gustav)
devuelve true.
196
El formato de la función es como el de fun-para-naf, excepto que emplea el nombre ancestro-ojoazul? Como siempre, se emplea el formato para orientar el diseño de la función. Primero se
supone que se presenta (empty? un-árbol), en cuyo caso, el árbol familiar es empty, y nadie tiene
ojos azules. De ahí que la respuesta deba ser false.
La segunda cláusula del formato contiene varias expresiones que requieren interpretación:
1. (ancestro-ojo-azul? (hijo-padre un-árbol)), la cual determina si alguien en el naf del
padre tiene ojos azules.
2. (ancestro-ojo-azul? (hijo-madre un-árbol)), la cual determina si alguien en el naf de
la madre tiene ojos azules.
3. (hijo-nombre un-árbol), extrae el nombre del hijo.
4. (hijo-fecha un-árbol), extrae la fecha de nacimiento del hijo.
5. (hijo-ojos un-árbol), obtiene el color de los ojos del hijo.
Depende ahora de nosotros emplear dichos valores apropiadamente. Es evidente que si la
estructura hijo contiene ‘blue en el campo ojos, la función responde true. De otra forma, la
función produce true si hay alguna persona en el árbol del padre o de la madre. El resto son datos
que no nos sirven.
Ese análisis sugiere formular una expresión condicional y que su primera condición es
(symbol=? (hijo-ojos un-árbol) 'azul)
Las dos recursiones son dos condiciones adicionales. Si alguna produce true, la función produce
true. La else-cláusula genera false.
En resumen, la respuesta en la segunda cláusula es la expresión:
(cond
[(symbol=? (hijo-ojos un-árbol) 'azul) true]
[(ancestro-ojo-azul? (hijo-padre un-árbol)) true]
[(ancestro-ojo-azul? (hijo-madre un-árbol)) true]
[else false])
La primera definición en la figura 37 reúne todo. La segunda definición muestra como formular
dicha cond-expresión como una equivalente or-expresión, probando cada condición una después
de la otra, hasta que una de ellas sea true o que todas se hayan evaluado a false.
La función ancestro-ojo-azul? es raro que emplee la recursión como condiciones en condexpresiones. Para comprender cómo opera esto, evaluemos una aplicación manual de ancestroojo-azul? a Carl:
197
(ancestro-ojo-azul? Carl)
= (ancestro-ojo-azul? (make-hijo empty empty ‘Carl 1926 ‘green))
= (cond
[(empty (make-hijo empty empty ‘Carl 1926 ‘green)) false]
[else
(cond
[(symbol=?
(hijo-ojos (make-hijo empty empty ‘Carl 1926 ‘green))
‘blue)
true]
[(ancestro-ojo-azul?
(hijo-padre (make-hijo empty empty ‘Carl 1926 ‘green)))
true]
[(ancestro-ojo-azul?
(hijo-madre (make-hijo empty empty ‘Carl 1926 ‘green)))
true]
[else false])])
= (cond
[(symbol=? ‘green ‘blue) true]
[(ancestro-ojo-azul? empty) true]
[(ancestro-ojo-azul? empty) true]
[else false])
= (cond
[false true]
[false true]
[false true]
[else false])
= false
La evaluación confirma que ancestro-ojo-azul? opera adecuadamente para Carl, y también
muestra cómo opera la función.
Ejercicio 14.1.1 La segunda definición de ancestro-ojo-azul? emplea una or-expresión en lugar
de un condicional anidado, como puede verse en la figura 37. Emplear una evaluación manual que
muestre que dicha definición produce la misma salida para las entradas empty y Carl.
198
;; ancestro-ojo-azul? : naf -> booleano
;; determinar si un-árbol contiene una estructura hijo con >azul en el campo ojos
;; versión 1: empleando una cond-expresión anidada
(define (ancestro-ojo-azul? un-árbol)
(cond
[(empty? un-árbol) false]
[else (cond
[(symbol=? (hijo-ojos un-árbol) 'blue) true]
[(ancestro-ojo-azul? (hijo-padre un-árbol)) true]
[(ancestro-ojo-azul? (hijo-madre un-árbol)) true]
[else false])]))
;; ancestro-ojo-azul? : naf -> booleano
;; determinar si un-árbol contiene una estructura hijo con >azul en el campo ojos
;; versión 2: empleando una or-expresión
(define (ancestro-ojo-azul? un-árbol)
(cond
[(empty? un-árbol) false]
[else (or (symbol=? (hijo-ojos un-árbol) ‘blue)
(or (ancestro-ojo-azul? (hijo-padre un-árbol))
(ancestro-ojo-azul? (hijo-madre un-árbol))))]))
Figura 37. Dos funciones para encontrar un ancesto ojo-azul
Ejercicio 14.1.2 Confirmar manualmente que genera false:
(ancestro-ojo-azul? empty)
Con base en lo anterior evaluar (ancestro-ojo-azul? Gustav) a mano, y con DrScheme. Para la
evaluación manual, saltarse aquellos pasos de la evaluación que tienen que ver con extraer,
comparar y condiciones relacionadas con empty?. También reusar ecuaciones establecidas donde
sea posible, especialmente la anterior.
Ejercicio 14.1.3 Desarrollar contar-personas, consume un naf y genera el número de personas en
el correspondiente árbol familiar.
Ejercicio 14.1.4 Desarrollar edad-promedio, consume un naf y el año actual, y genera la edad
promedio de todos los individuos en un árbol familiar.
Ejercicio 14.1.5 Desarrollar la función color-ojos, consume un naf y genera una lista de todos los
colores de ojos en el árbol familiar. Un color de ojos puede ocurrir más de una vez en la lista.
Sugerencia: Emplear la operación Scheme append, la cual consume dos listas y produce la
concatenación de ambas.
199
Por ejemplo:
(append (list ´a ´b ´c) (list ´d ´e))
= (list ´a ´b ´c ´d ´e)
Se discute el desarrollo de funciones como append en la sección 17.
Ejercicio 14.1.6 Supóngase que se requiere ancestro-propio-ojo-azul?, parecido a ancestro-ojoazul?, pero únicamente responde true cuando propiamente un ancestro tiene ojos azules.
El contrato para esta nueva función es el mismo que para la anterior:
;; ancestro-propio-ojo-azul? : naf -> booleano
;; determinar si un-árbol tiene un ancestro ojo-azul
(define (ancestro-propio-ojo-azul? un-árbol) …)
Los resultados difieren ligeramente.
Para apreciar la diferencia, se necesita analizar Eva, quien tiene ojo-azul, pero no tiene un ancestro
ojo-azul. De ahí que
(ancestro-propio-ojo-azul? Eva)
es false. Después de todo Eva no es un ancestro propio de ella misma.
Supóngase alguien considera la declaración de propósito y genera esta solución:
(define (ancestro-propio-ojo-azul? naf)
(cond
[(empty? naf) false]
[else (or (ancestro-propio-ojo-azul? (hijo-padre naf))
(ancestro-propio-ojo-azul? (hijo-madre naf)))]))
¿Cuál sería el resultado de (ancestro-propio-ojo-azul? A) para cualquier naf A?
Corrija la expresión propuesta.
14.2 Ejercicio ampliado: Árboles de búsqueda binaria
Se trabaja más con árboles que con árboles familiares. En particular con los bien conocidos
denominados árboles de búsqueda binaria, que se emplean en muchas aplicaciones orientadas a
almacenar y recuperar información.
200
En particular, árboles binarios que manejan información acerca de personas. En este contexto, un
árbol de búsqueda binaria es parecido a un árbol familiar que en lugar de estructuras hijo contiene
nodos:
(define-struct nodo (nss nombre izquierdo derecho))
De ahí que si decide registrar el número del seguro social, el nombre y otros dos árboles; éstos
como si fueran campos parentales de árboles familiares, aunque la relación entre un nodo y su
campo izquierdo y derecho no se base en relaciones familiares. Si nss, número del seguro social,
nombre es un símbolo e izquierdo y derecho son como los campos de los árboles familiares en un
af, que en lugar de estructuras hijo contiene nodos.
La correspondiente definición de datos es parecida a la de los árboles familiares:
Un árbol binario, AB, es cualquiera de
1. false, o
2. (make-nodo ns pn izq der)
donde ns es un número, pn un símbolo, e izq y der son ABs.
La opción de false para indicar carencia de información es arbitraria. Se pudo haber empleado
empty nuevamente, pero false es igualmente bueno y es más frecuente;
Ejemplos de árboles binarios:
(make-nodo
15
'd
false
(make-nodo 24 'i false false))
(make-nodo
15
'd
(make-nodo 87 'h false false)
false)
La figura 38 muestra cómo se debe pensar acerca de tales árboles. Los que se construyen hacia
abajo, o sea, con la raíz arriba y las ramas abajo. Cada círculo corresponde a un nodo, etiquetados
con su campo ns de una estructura nodo correspondiente. Los árboles omiten false.
201
Ejercicio 14.2.1 Dibuje los dos primeros árboles mencionados, desarrolle contiene-ab?, una
función que consume un número y un AB y determina si el número ocurre en el árbol.
Ejercicio 14.2.2 Desarrolle busca-ab, consume un número n y un AB, si el árbol contiene una
estructura de nodo cuyo campo ns es n, la función genera el valor de pn en ese nodo, en cualquier
otro caso genera false.
Sugerencia: Emplear contiene-ab. O emplear boolean? para encontrar si busca-ab fue empleada
exitosamente en un subárbol. Se discutirá esta segunda técnica, denominada backtracking, en el
intermezzo al final de esta parte.
Árbol A
Árbol B
Figura 38. Un árbol de búsqueda binario y un árbol binario
Ambos árboles en la figura 38 son árboles binarios pero difieren de forma significativa. Si se leen
los números en los dos árboles de izquierda a derecha se obtienen las secuencias:
Árbol A
Árbol B
10
87
15
15
24
24
29
29
63
63
77
33
89
89
95
95
99
99
La secuencia del árbol A está ordenada de forma ascendente, la de B no.
Un árbol binario que tiene una secuencia ordenada de información es un ÁRBOL DE BÚSQUEDA
BINARIA. Todo árbol de búsqueda binaria es un árbol binario, pero no todo árbol binario es uno de
búsqueda binaria. Se dice que la clase de árboles de búsqueda binaria es una SUBCLASE
PROPIA de la de árboles binarios. En concreto, se formula una condición –o invariante de datos–
que distingue a los árboles de búsqueda binaria de los árboles binarios:
El invariante ABB
Un árbol de búsqueda binaria, ABB, es un AB
1. false es siempre un ABB, y
202
2. (make-nodo ns pn izq der) es un ABB si
1. izq y der son ABBs,
2. los nss en izq son menores que ns, y
3. los nss en der son mayores que ns.
Las condiciones segunda y tercera son diferentes de cualquier definición de datos vista hasta
ahora. Ubican un obstáculo adicional y desacostumbrado en la construcción de ABBs. Ahora se
requiere inspeccionar todos los números en dichos árboles y garantizar que son menores (o
mayores) que ns.
Ejercicio 14.2.3 Desarrolle la función enorden, consume un AB y genera una lista de los nss en el
árbol, la lista contiene los números de izquierda a derecha.
Sugerencia: Emplear la operación Scheme append, la cual concatena listas:
(append (list 1 2 3) (list 4) (list 5 6 7))
;; se evalúa a
(list 1 2 3 4 5 6 7)
¿enorden qué genera en un ABB?
Buscar en nodo específico en un ABB es más fácil que en un AB. Para descubrir si un AB contiene
un nodo con un campo nss específico, una función puede haber buscado en cada nodo del árbol.
En contraste, inspeccionar un árbol de búsqueda binaria requiere menores inspecciones.
Supóngase que el ABB dado es
(make-nodo 66 'a I D)
Si se busca 66, se ha encontrado. Si 63, dado el nodo anterior, únicamente se centraría la búsqueda
en I debido a que todos los nodos con nnss menores que 66 están en I. De forma parecida, si se
busca 99, se ignora I y hay que centrarse en D debido a que todos los nodos con nnss mayores que
66 están en D.
Ejercicio 14.2.4 Desarrolle busca-ABB, consume un número n y un ABB. Si el árbol contiene una
estructura de nodo cuyo campo ns es n, la función genera el valor del campo pn en dicho nodo, en
caso contrario false. La organización de la función aprovecha el Invariante ABB de modo que la
función realiza el menor número de comparaciones posible. Compare buscar en árboles de
búsqueda binaria con buscar en listas ordenadas.
Construir un árbol binario es fácil; construir un árbol de búsqueda binaria es complicado, además
de generador de errores. Para crear un AB se combinan dos ABs, un número nss y un nombre con
203
make-nodo. El resultado es, por definición, un AB. Para crear un ABB, este procedimiento falla
debido a que el resultado típicamente no es un ABB. Por ejemplo, si un árbol contiene 3 y 5, y el
otro contiene 2 y 6, no hay forma de reunirlos en un solo árbol de búsqueda binaria.
Se puede superar este problema (cuando menos) de dos formas. Primero, dada una lista de
números y símbolos, se puede determinar manualmente cómo serían los de los correspondientes
ABB y emplear make-nodo para construirlo. Segundo, se puede escribir una función que construya
un ABB de la lista, un nodo después de otro.
Ejercicio 14.2.5 Desarrollar la función crear-abb. Consume un ABB B, un número N, y un
símbolo S. Produce un ABB que es como B y que en lugar de un subárbol false contiene la
estructura nodo
(make-nodo N S false false)
Probar la función con (crear-abb false 66 ‘a); lo que debe crear un solo nodo. Luego demuestre
que lo siguiente se cumple:
(crear-abb (crear-abb false 66 'a) 53 'b)
= (make-nodo 66
'a
(make-nodo 53 'b false false)
false)
Finalmente, crear el árbol A de la figura 38 empleando crear-abb.
Ejercicio 14.2.6 Desarrollar la función crear-abb-de-lista. Consume una lista de números y
nombres; produce un ABB al aplicar de forma repetida crear-abb.
La definición de datos para una lista de números y nombres es como sigue.
Una lista-de-número/nombre es cualquiera de
1. empty o
2. (cons (list nns nom) ldnn)
donde nns es un número, nom un símbolo,
y ldnn es una lista-de-número/nombre.
Considérense los siguientes ejemplos:
204
(define muestra
‘(99 o)
‘(77 l)
‘(24 i)
‘(10 h)
‘(95 g)
‘(15 d)
‘(89 c)
‘(29 b)
‘ 63
a)))
(define muestra
(list (list 99 'o)
(list 77 'l)
(list 24 'i)
(list 10 'h)
(list 95 'g)
(list 15 'd)
(list 89 'c)
(list 29 'b)
(list 63 'a)))
Son equivalentes, sin embargo, el de la izquierda es definido con la abreviación quote, el de la
derecha empleando list. El árbol de la izquierda en la figura 38 es el resultado de emplear crearabb-de-lista en dicha lista.
14.3 Listas en listas
La World Wide Web, o simplemente “la Web”, se ha convertido en la parte más interesante de
Internet, una red global de computadoras. De forma burda, se puede afirmar que la web es una
colección de páginas web. Cada una de éstas es una secuencia de palabras, gráficas, películas y
mensajes de audio, entre otras cosas; lo más importante es que, las páginas web contienen ligas a
otras páginas web.
Un navegador web permite a la gente ver páginas web, presenta una página web como una
secuencia de palabras, imágenes, etc. Algunas palabras en una página pueden ir subrayadas.
Dando click a palabras subrayadas conduce a una nueva página web. Los más modernos
navegadores también proporcionan un generador de páginas web. Estas herramientas ayudan a la
gente a crear colecciones de páginas web. Un generador, entre otras cosas, puede buscar palabras o
reemplazar una palabra por otra. O sea, páginas web son cosas que se debe poder representar en
una computadora, y existen muchas funciones que procesan páginas web.
205
Una simplificación es considerar a una página web compuesta por palabras y otras páginas web
anidadas. Una forma de comprender una página es como una secuencia de palabras y páginas web.
Esta descripción informal sugiere una representación natural de páginas web como una lista de
símbolos, la cual representa palabras, y páginas web, las cuales representan páginas web anidadas.
Después de todo, se ha enfatizado previamente que una lista puede contener diferentes clases de
cosas. Sin embargo, cuando se detalla esta idea como una definición de datos, se obtiene algo raro.
Una página-web, PW, es o
1. empty,
2. (cons s pw)
donde s es un símbolo y pw es una página web; o
3. (cons pwe pw)
donde ambas pwe y pw son páginas web.
Esta definición de datos difiere de otras de listas de símbolos en que tienen tres cláusulas en lugar
de dos y que tiene tres auto-referencias en lugar de una. De todas estas auto-referencias, la primera
al inicio de una lista construida es la más rara. Se denominan dichas páginas web como
inmediatamente empotradas.
Debido a lo raro de la definición de datos, se construyen algunos ejemplos de páginas web antes
de continuar. Una página web sencilla es:
'(The TeachScheme! Project aims to improve the
problem-solving and organization skills of high
school students. It provides software and lecture
notes as well as exercises and solutions for teachers.)
contiene sólo palabras, una página compleja es:
'(The TeachScheme Web Page
Here you can find:
(LectureNotes for Teachers)
(Guidance for (DrScheme: a Scheme programming environment))
(Exercise Sets)
(Solutions for Exercises)
For further information: write to scheme@cs)
Las páginas inmediatamente empotradas inician con paréntesis y los símbolos 'LectureNotes,
'Guidance, 'Exercises, y 'Solutions. La segunda página web empotrada contiene otra página
empotrada, la cual inicia con ´DrScheme. Se dice que esta página está completamente empotrada
con respecto a la página entera.
206
Si se desarrolla la función tamaño, que consume una página web y genera el número de palabras
que contiene, así como el de las páginas incrustadas.
tamaño : pw -> número
contar el número de símbolos que ocurre en una-pw
(define (tamaño una-pw) ... )
Las dos páginas web de arriba sugieren dos buenos ejemplos, pero son demasiado complejas. A
continuación se mencionan tres ejemplos, uno por subclase de datos:
(= (tamaño empty)
0)
(= (tamaño (cons ´Uno empty))}
1)
(= (tamaño (cons (cons ´Uno empty) empty))
1)
Los primeros dos son obvios. El último requiere una pequeña explicación. Es una página web que
contiene una página incrustada inmediatamente, y nada más. La página web incrustada es una del
segundo ejemplo, y contiene uno y solo un símbolo del tercer ejemplo.
Para desarrollar el formato para tamaño, avancemos cuidadosamente a través de la receta de
diseño. La forma de la definición de datos sugiere que se requieren tres cond-cláusulas: una para
la página empty, otra para la que inicie con un símbolo, y otra para una página que inicia con una
página incrustada. Mientras la primera condición es la prueba familiar para empty, la segunda y la
tercera requieren una inspección más minuciosa debido a que ambas cláusulas en la definición de
datos emplean cons, y un simple cons? no distinguirá las dos formas de datos.
Si la página no es empty, es construida, y la característica distintiva es el primer ítem en la lista.
En otras palabras, la segunda condición debe emplear un predicado que pruebe el primer ítem en
una-pw:
;; tamaño : PW -> número
;; contar el número de símbolos que ocurren en una-pw
(define (tamaño una-pw) ... )
(cond
[(empty? una-pw) ...]
[(symbol? (first una-pw)) ... (first una-pw) ... (tamaño (rest una-pw)) ...]
[else ... (tamaño (first una-pw)) ... (tamaño (rest una-pw)) ...]))
207
El resto del formato es como siempre. La segunda y tercera cláusula cond contienen expresiones
selector para el primer ítem y el resto de la lista. Debido a que (rest una-pw) es siempre una
página web y debido a que (first un-pw) es uno en el tercer caso, se agrega una llamada recursiva
a tamaño para dichas expresiones selector.
Empleando los ejemplos y el formato, estamos listos para diseñar tamaño: véase figura 39. Las
diferencias entre la definición y el formato son mínimas, lo cual muestra nuevamente cómo mucho
de una función puede diseñarse pensando sistemáticamente acerca de las definiciones de datos de
sus entradas.
;; tamaño : PW -> número
;; contar el número de símbolos que ocurren en una-pw
(define (tamaño una-pw) ... )
(cond
[(empty? una-pw) 0]
[(symbol? (first una-pw)) (+ 1 (tamaño (rest una-pw)))]
[else (+ tamaño (first una-pw)) (tamaño (rest una-pw)))]))
Figura 39. Definición de tamaño para páginas web
Ejercicio 14.3.1 Explicar brevemente cómo definir tamaño al emplear su formato y los ejemplos.
Probarla empleando los ejemplos previos.
Ejercicio 14.3.2 Desarrolle la función ocurre1, que consume una pw y un símbolo, generando el
número de veces que el símbolo ocurre en la pw, ignorando las pw anidadas. Desarrolle ocurre2,
donde no ignora la ocurrencia del símbolo en las páginas anidadas.
Desarrolle la función ocurre2. Es como ocurre1, pero cuenta todas las ocurrencias de un símbolo,
incluyendo las páginas incrustadas.
Ejercicio 14.3.3 Desarrolle la función reemplaza, consume dos símbolos, nuevo y viejo, así como
una-pw, generando una página idéntica a una-pw con todas las ocurrencias de viejo reemplazadas
por nuevo.
Ejercicio 14.3.4 No son agradables árboles web profundos, pues requieren muchos cambios de
página para llegar a la información útil, de ahí la necesidad de medir la profundidad de una página.
Una profundidad 0 de una página implica que ésta maneja únicamente símbolos; una página con
otra página web inmediatamente incorporada, tiene la profundidad de ésta más 1; si una página
tiene varias páginas inmediatamente incorporadas, su profundidad es la profundidad máxima de
208
las páginas incrustadas más uno. Desarrolle profundidad, la cual consume una pw y calcula su
profundidad.
14.4 Ejercicio ampliado: Evaluar Scheme
DrScheme es un programa que consiste en varias partes. Una función verifica si las definiciones y
expresiones escritas son expresiones gramaticales Scheme, otra evalúa dichas expresiones. Es
factible desarrollar versiones simples de tales funciones.
Lo primero que se requiere desarrollar es una representación para los programas Scheme. En otras
palabras, se debe representar una expresión Scheme como una pieza de datos Scheme. Supóngase
que para empezar se desea representar números, variables, sumas y multiplicaciones; los números
pueden representar números y los símbolos, variables; sumas y multiplicaciones, sin embargo,
requieren una clase de datos compuestos, ya que constan de un operador y dos subexpresiones.
Una forma directa de representar sumas y multiplicaciones es emplear dos estructuras: una para
sumas y otra para multiplicaciones. Dichas definiciones de estructuras son:
(define-struct sum (izquierda derecha)
(define-struct mul (izquierda derecha)
Analizar algunos ejemplos:
Dichos ejemplos cubren todos los casos: números, variables, expresiones simples, y expresiones
anidadas.
Expresión Scheme
3
X
(* 3 10)
representación de una expresión Scheme
3
'x
(make-mul 3 10)
(+ (* 3 3) (* 4 4)) (make-sum (make-mul 3 3) (make-mul 4 4))
(+ (* x x) (* y y)) (make-sum (make-mul 'x 'x) (make-mul 'y 'y))
(* 1/2 (* 3 3))
(make-mul 1/2 (make-mul 3 3))
Ejercicio 14.4.1 Desarrollar definiciones de datos para la representación de expresiones Scheme.
Luego traducir las siguientes expresiones en representaciones:
209
1. (+ 10 -10)
2. (+ (* 20 3) 33)
3. (* 3.14 (* r r))
4. (+ (* 9/5 c) 32)
5. (+ (* 3.14 (* o o)) (* 3.14 (* i i)))
Un evaluador Scheme es una función que consume una representación de una expresión Scheme y
produce su valor. Por ejemplo, la expresión 3 tiene el valor 3, (+ 3 5) tiene el valor 8, (+ (* 3 3) (*
4 4)) tiene el valor 25, etc. Puesto que por ahora se ignoran las definiciones, una expresión que
contiene una variable, por ejemplo, (+ 3 x), no tiene un valor; después de todo, no se sabe qué
representa la variable. O sea, nuestro evaluador Scheme debe ser aplicado únicamente a
expresiones que no contienen variables. Se dice que son expresiones numéricas.
Ejercicio 14.4.2 Desarrollar numérica?, que consume la representación de una expresión Scheme
y determina si es numérica.
Ejercicio 14.4.3 Proporcionar una definición de datos para expresiones numéricas. Desarrollar la
función evaluar-expresión. La función consume (la representación de) una expresión Scheme
numérica y calcula su valor. Cuando se haya probado la función, modificarla para que consuma
todo tipos de expresiones Scheme; la versión revisada marca un error cuando encuentra una
variable.
Ejercicio 14.4.4 Cuando alguien evalúa una aplicación (f a) sustituye a por los parámetros de f
en el cuerpo de f. De forma más general, cuando se evalúan expresiones con variables, se
sustituyen variables con valores.
Desarrollar la función subst. Consume (la representación de) una variable (V), un número (N), y
(la representación de ) una expresión Scheme. Produce una expresión estructuralmente equivalente
en la cual todas las ocurrencias de V son sustituidas por N.
210
SECCIÓN 15
Definiciones de datos mutuamente referidas
En la sección precedente, se desarrollaron representaciones de árboles familiares, páginas web, y
expresiones Scheme. Desarrollar funciones para dichas definiciones de datos se apoyó en una y la
misma receta de diseño. Si se desea desarrollar representaciones más realistas de páginas web o
expresiones Scheme, o se desea estudiar árboles familiares de descendientes en lugar de ancestros,
se debe aprender a describir clases de datos que estén interrelacionados. O sea, se deben formular
varias definiciones de datos a la vez, donde las definiciones de datos no sólo se refieren a sí
mismas, sino a otras definiciones de datos.
15.1 Listas de estructuras, listas en estructuras
Cuando se construye un árbol familiar de forma retroactiva, a menudo se inicia desde la
perspectiva de un hijo procediéndose a partir del mismo, con los padres, abuelos, etc. En la
medida en que se construye el árbol, se escribe quién es hijo de quién, más que quiénes son sus
padres. Se escribe un árbol familiar de descendientes.
Dibujar un árbol de descendientes es parecido a dibujar uno de ancestros, excepto en que las
flechas apuntan en dirección contraria. La figura 40 representa la misma familia de la figura 35,
pero dibujado desde la perspectiva de los descendientes.
Representar estos nuevos tipos de árboles familiares y sus nodos en computadora requiere una
clase diferente de datos que las de árboles familiares de ancestros. Esta vez un nodo debe incluir
información acerca de los hijos en lugar de los dos padres. La definición de estructura es:
(define-struct padre (hijos nombre fecha ojos))
Los tres últimos campos en una estructura padre contienen la misma información básica que la
correspondiente estructura hijo, pero los contenidos del primero plantean un aspecto interesante.
Puesto que un padre puede tener un número arbitrario de hijos, el campo hijos debe contener un
número indeterminado de nodos, cada uno representando un hijo.
211
Carl (1926)
Eyes: green
Bettina (1926)
Eyes: green
Adam (1950)
Eyes: yellow
Dave (1955)
Eyes: black
Eva (1965)
Eyes: blue
Fred (1966)
Eyes: pink
Gustav (1988)
Eyes: brown
Figura 40. Un árbol familiar de descendientes
La opción natural es insistir en que el campo hijos siempre representa una lista de estructuras
padre. La lista representa los hijos; si una persona no tiene hijos, la lista es empty. Lo que sugiere
la siguiente definición de datos:
Un padre es una estructura:
(make-padre ldh n f o)
donde ldh, lista de hijos; n y o son símbolos, y f es un número.
Sin embargo, esta definición de datos viola el criterio referente a definiciones. En particular,
menciona el nombre de una colección no definida aún: lista de hijos.
Puesto que es imposible definir la clase de padres sin conocer qué es una lista de hijos, habría que
empeza por ésta.
Una lista de hijos es cualquiera de:
1. empty o
2. (cons p ldh) donde p es un padre y ldh es una lista de hijos.
Esta segunda definición parece estándar, sin embargo, es afectada con el mismo problema que la
de padres. La clase desconocida a la que se refiere es la de padres, la cual no se puede definir sin
la definición de la lista de hijos, etc.
212
La conclusión es que las definiciones de datos se refieran una a otra y únicamente son
significativas si se introducen juntas.
Un padre es una estructura
(make-padre ldh n f o)
donde ldh, lista de hijos; n y o es símbolo, y f es un número.
Una lista-de-hijos es cualquiera de
1. empty o
2. (cons p ldh) donde p es un padre y ldh es una lista de hijos.
Cuando dos, o más, definiciones de datos se refieren cada una a la otra, se dice que son
MUTUAMENTE RECURSIVAS o MUTUAMENTE REFERENCIALES.
Ahora se puede traducir el árbol familiar de la figura 40 al lenguaje de datos de Scheme. Por
supuesto, antes de crear una estructura padre se deben primero definir todos los nodos que
representan hijos. Y, como en la sección 14.1, la mejor manera de hacerlo es nombrar la estructura
padre antes de reusarla en la lista de hijos. Por ejemplo:
(define Gustav (make-padre empty 'Gustav 1988 'brown))
(make-padre (list Gustav) 'Fred 1966 'pink)
Para crear una estructura padre para Fred, se requiere primero definir una para Gustav de modo de
formar (list Gustav), la lista de hijos de Fred.
La figura 41 contiene la representación Scheme completa del árbol de descendientes. Para evitar
repeticiones, se incluyen definiciones para listas de hijos. Compare las definiciones con la figura
36, la cual representa la misma familia como árbol de ancestros.
Analizando el desarrollo de descendiente-ojo-azul?, la compañera natural de ancestro-ojo-azul?
Consume una estructura padre y determina si ésta o cualquiera de sus descendientes tiene ojos
azules.
;; descendiente-ojo-azul? : padre -> booleano
;; determinar si un-padre o cualquiera de sus descendientes (hijos, nietos, etc) tiene ‘blue
;; en el campo ojos
(define (descendiente-ojo-azul? un-padre) …)
213
A continuación tres ejemplos simples, formulados como pruebas:
(boolean=? (descendiente-ojo-azul? Gustav) false)
(boolean=? (descendiente-ojo-azul? Eva) true)
(boolean=? (descendiente-ojo-azul? Bettina) true)
;; Generación más joven
(define Gustav (make-padre empty 'Gustav 1988 'brown))
(define Fred&Eva (list Gustav))
;; Generación intermedia:
(define Adam (make-padre empty 'Adam 1950 'yellow))
(define Dave (make-padre empty 'Dave 1955 'black))
(define Eva (make-padre Fred&Eva 'Eva 1965 'blue))
(define Fred (make-padre Fred&Eva 'Fred 1966 'pink))
(define Carl&Bettina (list Adam Dave Eva))
;; Generación mayor
(define Carl (make-padre Carl&Bettina 'Carl 1926 'green))
(define Bettina (make-padre Carl&Bettina 'Bettina 1926 'green))
Figura 41. Representación Scheme de un árbol familiar de descendientes
Un examen de la figura 40 explica las respuestas en cada caso.
Conforme a nuestras reglas, el formato para descendiente-ojo-azul? es simple. Puesto que su
entrada es una clase sencilla de estructuras, el formato contiene únicamente expresiones selector
para los campos en la estructura:
(define (descendiente-ojo-azul? un-padre)
…(padre-hijos un-padre) …
… (padre-nombre un-padre) …
… (padre-fecha un-padre) …
… (padre-ojos un-padre) … )
La definición de estructura para padre especifica cuatro campos, de ahí las cuatro expresiones.
214
Las expresiones en el formato nos recuerdan que el color de ojos del padre está disponible y puede
ser verificado. De ahí que se añada una cond-expresión que compare (padre-ojos un-padre) a
‘azul:
(define (descendiente-ojo-azul? un-padre)
(cond
[(symbol=? (padre-ojos un-padre) ‘blue) true]
[else
…(padre-hijos un-padre) …
… (padre-nombre un-padre) …
… (padre-fecha un-padre) … ] ) )
La respuesta es true si el condicional se cumple. La cláusula else contiene las expresiones
remanentes. Los campos nombre y fecha no tienen nada que ver con el color de ojos de una
persona, por lo que se ignoran. Lo que nos deja con
(padre-hijos un-padre)
una expresión que extrae la lista de hijos de la estructura padre.
Si el color de ojos de alguna estructura padre no es ‘blue, es evidente que se debe buscar en la
lista de hijos un descendiente ojo-azul. Siguiendo nuestra guía para funciones complejas, se agrega
la función a nuestra lista de deseos y se continúa. La función que se quiere en la lista de deseos
consume una lista de hijos y verifica si cualquiera de ellos o sus nietos tienen ojos azules. A
continuación el contrato, encabezado y declaración de propósito:
;; hijos-ojo-azul? : lista-de-hijos -> booleano
;; determinar si cualquiera de las estructuras en uldh tiene ojo-azul
;; o tiene algún descendiente ojo-azul
(define (hijos-ojo-azul? uldh) …)
Empleando hijos-ojo-azul? se puede completar la definición de descendiente-ojo-azul?
(define (descendiente-ojo-azul? un-padre)
(cond
[(symbol=? (padre-ojos un-padre) ‘blue) true]
[else (hijos-ojo-azul? (padre-hijo un-padre))]))
O sea, si un-padre no tiene ojos azules, se busca en la lista de sus hijos.
Antes de poder probar descendiente-ojo-azul?, se debe definir la función de la lista de deseos.
Para elaborar ejemplos y pruebas para hijos-ojo-azul?, se emplean las definiciones de la lista-dehijos de la figura 41.
215
(not (hijos-ojo-azul? (list Gustav)))
(hijos-ojo-azul? (list Adam Dave Eva))
Gustav no tiene ojos azules y no tiene registrados descendientes. Por lo que, hijos-ojo-azul?
produce false para (list Gustav). En cambio, Eva tiene ojos azules, por lo que hijos-ojo-azul?
produce true para la segunda lista de hijos.
Puesto que la entrada para hijos-ojo-azul? es una lista, el formato es el patrón estándar:
(define (hijos-ojo-azul? uldh)
(cond
[(empty? uldh) …]
[else
… (first uldh) …
… (hijos-ojo-azul? (rest uldh)) …]))
Ahora se consideran los dos casos. Si la entrada de hijos-ojo-azul? es empty, la respuesta es false.
De otra forma se tienen dos expresiones:
1. (first uldh), la cual extrae el primer ítem, una estructura padre, de la lista; y
2. (hijos-ojo-azul? (rest uldh)), la cual determina si cualquiera de las estructuras en uldh es ojoazul o tiene algún descendiente ojo-azul.
Afortunadamente se cuenta con una función que determina si una estructura padre o cualquiera de
sus descendientes tiene ojos azules: descendiente-ojo-azul?. Esto sugiere que se verifique si
(descendiente-ojo-azul? (first uldh))
se cumple y, en caso afirmativo, puede producir true. Si no, la segunda expresión determina si se
tiene más suerte con el resto de la lista.
La figura 42 contiene las definiciones completas para ambas funciones: descendiente-ojo-azul? e
hijos-ojo-azul? A diferencia de otros grupos de funciones, estas funciones se refieren una a la otra.
Son Mutuamente Recursivas. No sorprende que las referencias mutuas en las definiciones se
correspondan con las referencias mutuas en las definiciones de datos. La figura contiene también
un par de definiciones opcionales que emplean or en lugar de cond-expresiones anidadas.
Ejercicio 15.1.1 Evaluar manualmente (descendiente-ojo-azul? Eva). Luego evaluar (descendiente-ojo-azul? Bettina)
216
Ejercicio 15.1.2 Desarrollar qué-tan-lejos. Determina qué tan lejos está un descendiente con ojos
azules, si existe, de un determinado padre. Si el padre tiene ojos azules, la distancia es 0; si no
tiene ojos azules, pero alguno de los hijos sí, la distancia es 1, etc. Si ningún descendiente de un
padre determinado tiene ojos azules, la función devuelve false cuando se aplica al correspondiente
árbol familiar.
; descendiente-ojo-azul? : padre -> boolean
;; determinar si un-padre o cualquiera de sus descendientes (hijos, nietos,
;; etc) tiene ‘blue en el campo ojos
(define (descendiente-ojo-azul? un-padre)
(cond
[(symbol=? (padre-ojos un-padre) ‘blue) true]
[else (hijos-ojo-azul? (padre-hijos un-padre))]))
;; hijos-ojo-azul? : lista-de-hijos -> boolean
;; determinar si cualquiera de las estructuras en uldh tiene ojo-azul
;; o tiene algún descendiente ojo-azul
(define (hijos-ojo-azul? uldh)
(cond
[(empty? uldh) false]
[else
(cond
[(descendiente-ojo-azul? (first uldh) true]
[else (hijos-ojo-azul? (rest uldh))])]))
; descendiente-ojo-azul? : padre -> boolean
;; determinar si un-padre o cualquiere de sus descendientes (hijos, nietos,
;; etc) tiene ‘blue en el campo ojos
(define (descendiente-ojo-azul? un-padre)
(or (symbol=? (padre-ojos un-padre) ‘blue)
(hijos-ojo-azul? (padre-hijo un-padre))))
;; hijos-ojo-azul? : lista-de-hijos -> boolean
;; determinar si cualquiera de las estructuras en uldh tiene ojo-azul
;; o tiene algún descendiente ojo-azul
(define (hijos-ojo-azul? uldh)
(cond
[(empty? uldh) false]
[else
(or (descendiente-ojo-azul? (first uldh))
(hijos-ojo-azul? (rest uldh)))]))
Figura 42. Dos programas para encontrar un descendiente ojo-azul
217
Ejercicio 15.1.3 Desarrollar la función cuenta-descendientes, la cual consume un padre y produce
el número de descendientes, incluyendo al padre.
Desarrollar la función cuenta-descendientes-propios, la cual consume un padre y produce el
número de los que son propiamente descendientes, o sea, los nodos en el árbol familiar
excluyendo al padre (o madre).
Ejercicio 15.1.4 Desarrollar la función color-ojos, la cual consume un padre y produce una lista
de todos los colores de ojos en el árbol. Un color de ojo puede ocurrir más de una vez en la lista.
Sugerencia: Emplear la operación Scheme append, la cual consume dos listas y produce su
concatenación.
15.2 Diseño de funciones para definiciones mutuamente referidas
La receta para el diseño de funciones con base en definiciones de datos mutuamente referidas
generaliza la de datos auto-referenciales. De hecho, ofrece únicamente dos recomendaciones
adicionales. Primero, se deben crear simultáneamente varios formatos, uno para cada definición.
Segundo, se deben anotar los formatos con auto-referencias y REFERENCIAS CRUZADAS, o sea,
referencias entre diferentes formatos. A continuación una explicación más detallada de las
diferencias.
El análisis y diseño de datos
Si el problema menciona un número de diferentes clases de información (de tamaño
arbitrario), se requiere un grupo de definiciones de datos que sean auto-referenciales y que
se refieran cada una a la otra. En dichos grupos, se identifican las auto-referencias y las
referencias cruzadas entre dos definiciones de datos.
En el ejemplo previo, se requieren dos definiciones interrelacionadas:
Una estructura padre
(make-padre ldh n f o)
donde ldh es una lista de hijos, n y o son símbolos, y f es un número,
Una lista de hijos es cualquiera de
1. empty o
2. (cons p ldh) donde p es un padre y ldh es una lista de hijos
218
La primera tiene que ver con padres y el otro con listas de hijos. La primera
(incondicionalmente) define un padre en términos de símbolos, números y una lista de
hijos, o sea, contiene una referencia cruzada a la segunda condición. Ésta es una definición
condicional; su primera cláusula es simple, su segunda cláusula referencia tanto la
definición para padres como para lista-de-hijos.
Contrato, propósito, encabezado
Para procesar clases de datos interrelacionadas, se requieren tantas funciones como clases
de definiciones. De ahí que, se deban formular tantos contratos, declaraciones de
propósito, y encabezados en paralelo como definiciones de datos.
Formatos
Los formatos se crean en paralelo, siguiendo las recomendaciones relacionadas con datos
compuestos, datos mezclados, y datos auto-referenciales. Finalmente, se deben determinar
para cada expresión selector en cada formato si corresponde con una referencia cruzada de
alguna definición. Si es el caso, anotarse en la misma forma que se anotan referencias
cruzadas.
A continuación los formatos para el ejemplo
(define (fun-padre un-padre)
…(padre-nombre un-padre)
…(padre-fecha un-padre)
…(padre-ojos un-padre)
…(fun-hijos (padre-hijos un-padre)
(define (fun-hijos uldh)
(cond
[(empty? uldh) …]
[else …(fun-padre (first uldh)…(fun-hijos (rest uldh)) …]))
El formato fun-padre no tiene condiciones debido a que la definición de datos para padre
no contiene ninguna cláusula. Contiene una referencia cruzada al segundo formato; para
procesar el campo children de la estructura padre. Conforme las mismas reglas, funchildren es condicional. La segunda cond-cláusula contiene una auto-referencia, para el
rest de la lista, y una referencia cruzada para el first ítem de la lista, la cual es una
estructura padre.
219
Una comparación de las definiciones de datos y los formatos muestra qué tan parecidas
son. Para enfatizar la similaridad entre auto-referencias y referencias cruzadas, las
definiciones de datos y formatos han sido marcados con flechas. Es fácil ver cómo las
flechas correspondientes tienen el mismo origen y destino en los dos dibujos.
El cuerpo
Conforme se procede para crear las definiciones finales, se inicia con un formato o una
cond-cláusula que no contiene auto-referencias al formato ni referencias cruzadas a otros
formatos. Los resultados son típicamente fáciles de formular para dichos formatos o condcláusulas.
En el resto de este paso se procede como antes. Cuando se tiene que operar con otras
cláusulas o funciones, se recuerda qué calcula cada expresión en el formato, suponiendo
que todas las funciones operan según se ha especificado en los contratos. Entonces se
decide cómo combinar dichas piezas de datos en una respuesta final. Conforme se realiza
esto, hay que tener presentes las orientaciones relacionadas con la composición de
funciones complejas (secciones 7.3 y 12).
La figura 43 sintetiza la receta de diseño ampliada.
FASE
Análisis
y diseño
de datos
Formato
Cuerpo
META
ACTIVIDAD
Formular un Desarrollar un grupo de definiciones de datos mutuamente recursivas
grupo de
•cuando menos una definición o una opción en una definición debe
definiciones referirse a datos básicos •identificar explícitamente todas las referencias
de datos
entre definiciones de datos
relacionadas
Formular un Desarrollar simultáneamente tantos formatos como definiciones de datos
grupo de
existen •desarrollar cada formato según corresponda con las reglas para
esquemas de definiciones de datos compuestos y/o mezclados •marcar formatos con
función
recursiones y aplicaciones cruzadas de modo que coincidan con las
referencias cruzadas en las definiciones de datos
Definir un Formular una expresión Scheme para cada formato, y para cada condgrupo de
cláusula en un formato •explicar qué calcula cada expresión en cada
funciones formato •usar funciones auxiliares donde sea necesario
Figura 43. Pasos esenciales en el diseño de grupos de funciones para grupos
de definiciones de datos; para otros casos véase figuras 4, 12 y 18
15.3 Ejercicio ampliado: Más en páginas Web
Con definiciones de datos mutuamente referenciales se pueden representar páginas web en forma
más precisa que en la sección 14.3. A continuación la definición de estructura básica:
220
(define-struct pw (encabezado cuerpo))
Los dos campos contienen dos piezas esenciales de datos en una página web: un encabezado y un
cuerpo. La definición de datos especifíca que un cuerpo es una lista de palabras y páginas web.
Una Página Web, PW, es una estructura
(make-pw e p)
donde e es un símbolo y p es un documento (web).
Un documento (Web) es cualquiera de
1. empty,
2. (cons s p)
donde s es un símbolo y p es un documento, o
3. (cons w p)
donde w es una página Web y p es un documento.
Ejercicio 15.3.1 Desarrollar la función tamaño, que consume una página web y produce el
número de símbolos (palabras) que contiene.
Ejercicio 15.3.2 Desarrollar la función pw-a-archivo. La función consume una página web y
produce una lista de símbolos. La lista contiene todas las palabras en un cuerpo y todos los
encabezados de páginas web empotradas. Los cuerpos de las páginas web inmediatamente
empotradas se ignoran.
Ejercicio 15.3.3 Desarrollar la función ocurre. Consume un símbolo y una página web y
determina si el primero ocurre en cualquier lugar de la segunda, incluyendo las páginas web
empotradas.
Ejercicio 15.3.4 Desarrollar el programa encuentra. Consume una página web y un símbolo.
Produce false, si el símbolo no ocurre en el cuerpo de la página o de sus páginas empotradas. Si el
símbolo ocurre cuando menos una vez, produce una lista de los encabezados encontrados en el
camino al símbolo.
Sugerencia: Defina una auxiliar como encuentra que produzca únicamente true cuando una
página web contenga la palabra encontrada. Emplearla para definir encuentra. Otra opción,
emplear boolean? para determinar si una recursión natural de encuentra produce una lista o un
booleano. Calcule entonces el resultado otra vez. Se discutirá esta segunda técnica, denominada
backtracking, en el intermezzo al final de esta parte.
221
222