Download Cómo diseñar programas

SECCIÓN 11
Números naturales
Hasta ahora las únicas definiciones de datos autoreferenciales consideradas incluían cons y listas
de longitud arbitraria. Se requerían dichas definiciones de datos debido a que las clases de listas
que se necesitaba procesar eran de tamaño arbitrario. Los números naturales son otra clase de
datos cuyos elementos son de tamaño arbitrario; después de todo, no existe límite en cuanto a qué
tan grande puede ser un número natural y, en principio, una función debería ser capaz de
procesarlos todos.
En esta sección, se estudia cómo describir números naturales mediante definiciones de datos
autoreferenciales y cómo desarrollar funciones que procesen números naturales de forma
sistemática. Puesto que tales funciones tienen muchos sabores, se analizan diferentes sabores de
definiciones.
11.1 Definición de números naturales
Normalmente se introducen los números naturales mediante enumeración: 0, 1, 2, etc.34. Esta
abreviación “etc.”, significa que la serie continua de la misma manera. Los matemáticos emplean
puntos para el mismo propósito. Sin embargo, ni los puntos ni el “etc.” son suficientemente
buenos, si se desea diseñar sistemáticamente funciones con base en números naturales. De ahí la
pregunta de saber qué significa escribir “etc.”, o dicho de otra manera qué es una descripción de
números naturales completa y autocontenida:
La única forma de quitar el informal “etc.” de la enumeración es describir la colección de números
mediante una descripción auto-referencial. Un primer intento puede ser:
0 es un número natural.
Si n es un número natural, entonces uno más n lo es también
34
Es importante empezar a contar a partir de 0 de modo de emplear números naturales para contar el número de
ítems en una lista o los miembros en un árbol genealógico familiar.
155
Si bien esta descripción aún no es suficientemente rigurosa35, permite desarrollar una descripción
de datos de las del tipo empleado en Scheme.
Un número-natural es
1. 0
o
2. (add1 n) si n es un número natural.
La operación add1 añade 1 a un número natural. Por supuesto, se podría emplear (+ …. 1), pero
add1 destaca e indica “número natural”, como opuesto a un número arbitrario, al lector de una
definición de datos y de una función.
Aunque son familiares los números naturales, es ilustrativo construir ejemplos a partir de la
definición de datos. Es claro que,
0
es el primer número natural,
(add1 0)
el siguiente, por lo que es fácil comprender el siguiente patrón.
(add1 (add1 0))
(add1 (add1 (add1 0)))
(add1 (add1 (add1 (add1 0))))
Los ejemplos nos hacen presente el proceso de construcción de listas. Se han construido listas que
inician con empty, con base en la cual se construye con más cosas. Ahora se construyen números
naturales iniciando con 0 y a los que se les va agregando 1. Además, los números naturales vienen
con abreviaciones desde hace siglos. Por ejemplo, (add1 0) se abrevia como 1, (add1 (add1 0))
como 2, y así sucesivamente.
Una función en números naturales debe extraer el número que acompañó la construcción de un
número natural positivo, de forma parecida a como una función en listas extrae la lista que forma
parte de una lista construida, la operación que realiza dicha extracción se denomina sub1, y
satisface la regla
(sub1 (add1 n)) = n
35
Habría que diferirlo a un curso de matemáticas de conjuntos.
156
De la misma forma que la operación rest cumple con
(rest (cons un-valor una-lista)) = una-lista
Por supuesto igual operaría (- n 1), sin embargo, sub1 destaca e indica que la función procesa
números naturales.
11.2 Procesamiento de números naturales de tamaño arbitrario
La función holas, consume un número natural n y genera una lista de n copias de >hola. Su
contrato es
;; holas : n -> lista-de-símbolos
;; crear una lista de n copias de >hola
(define (holas n) ... )
Ejemplos:
(holas 0)
;; valor esperado:
empty
(holas 2)
;; valor esperado:
(cons `hola (cons `hola empty))
El diseño del formato para holas sigue la receta de diseño para definiciones de datos autoreferenciales. También, que holas es una función condicional, cuya cond-expresión tiene dos
cláusulas, y que la primera debe distinguir 0 de otras posibles entradas:
(define (holas n)
(cond
[(zero? n) ...]
[else ... ] ))
Además, como la definición de datos afirma que 0 es un valor atómico, cualquier otro número es
un valor compuesto que “contiene” los predecesores a los cuales se les sumó 1, de ahí que si n no
es 0, entonces se reste 1 de n, siendo el resultado un número natural, por lo que conforme a la
receta de diseño correspondiente tal resultado requiera envolverse con (holas ...):
157
(define (holas n)
(cond
[(zero? n) ... ]
[else ... (holas (sub1 n)) ... ] ) )
Ahora que se ha aprovechado cada posibilidad de la definición de datos se puede proceder con la
definición.
Si (zero? n) devuelve true, entonces la respuesta debe ser empty, como se ilustra en el primer
ejemplo. Si se supone que la entrada de la función es mayor que 0, por ejemplo 2, holas empleará
(holas 1) para calcular parte de la respuesta. El propósito de la función especifica que (holas 1)
produce (cons `hola empty), una lista con un `hola. En general, (holas (sub1 n)) produce una lista
que contiene n - 1 ocurrencias de ‘hola. De ahí que para producir una lista con n ocurrencias, se
deba cons otro ‘hola a tal lista:
(define (holas n)
(cond
[ (zero? n) empty]
[else (cons ‘hola (holas (sub1 n) ) ) ] ) )
Como de costumbre, la definición final es el formato con algunos añadidos.
Si se prueba holas con algunas evaluaciones manuales
(holas 0)
= (cond
[(zero? 0) empty]
[else (cons ‘hola (holas (sub1 0)))])
= (cond
[true empty]
[else (cons ´hola (holas (sub1 0)))])
= empty
que confirma que holas opera correctamente para el primer ejemplo.
Otro ejemplo
(holas 1)
= (cond
[(zero? 1) empty]
[else (cons ‘hola (holas (sub1 1)))])
158
= (cond
[false empty]
[else (cons ´hola (holas (sub1 1)))])
= (cons ´hola (holas 0))
= (cons ´hola empty)
Para el último paso de cálculo, se aprovecha que se sabe que (holas 0) se evalúa a empty y
remplaza a la expresión (subrayada) con dicho resultado.
La evaluación manual muestra que la función opera para el segundo ejemplo:
(holas 2)
= (cond
[(zero? 2) empty]
[else (cons ‘hola (holas (sub1 2)))])
= (cond
[false empty]
[else (cons ‘hola (holas (sub1 2)))])
= (cons ´hola (holas (sub1 2)))
= (cons ´hola (holas 1))
= (cons ´hola (cons ´hola empty))
Aprovechando nuevamente lo que se sabe de (holas 1), la cual simplifica significativamente la
evaluación manual.
Ejercicio 11.2.1 Generalizar holas a repetir, la cual consume un número natural n y un símbolo y
produce una lista con n ocurrencias del símbolo.
Ejercicio 11.2.2 Desarrollar la función tabula-f, la cual tabula los valores de
;; f : num -> num
(define (f x)
(+ (* 3 (* x x))
(+ (* -6 x)
-1)))
Para algunos números naturales. En particular, si consume un número natural n produce una lista
de n posns. El primero combina n con (f n), el segundo n – 1 con (f n-1), etc.
Ejercicio 11.2.3 Desarrollar aplica-n. Consume un número natural, n. Aplica la función mover
del ejercicio 10.3.6 n veces a CARA, la lista de formas del ejercicio 10.3.1. Cada aplicación debe
159
trasladar la forma un pixel. El propósito de la función es simular el movimiento continuo de una
forma en un lienzo, la parte que faltó en el ejercicio 10.3.
Ejercicio 11.2.4 Las listas pueden contener listas que contienen listas y así sucesivamente. Una
definición de datos que lleva esta idea a un extremo:
Una lista-profunda es o
1. s, donde s es algún símbolo o
2. (cons lp empty), donde lp es una lista profunda
Desarrollar la función profundidad, la cual consume una lista lp y determina cuántas veces cons
fue empleada para construirla.
Desarrollar la función hacer-profundidad, la cual consume un símbolo s y un número natural y
produce una lista profunda que contiene s y construida con n conses.
11.3 Ejercicio ampliado: Crear listas, probar funciones
Frecuentemente se encuentran situaciones donde se quisiera crear listas de datos que involucren
números; por ejemplo, podría desearse crear grandes listas de números para probar una función,
como extraer1 de la sección 10.2, en lugar de tener que crearlas manualmente. Algunas veces se
desea visualizar datos generados aleatoriamente. Se pueden crear tales funciones empleando
recursión en números naturales y un generador aleatorio de números naturales.
Ejercicio 11.3.1 Scheme proporciona la operación random, la cual consume un número natural n
mayor que 1, y genera un entero aleatorio entre 0 y n-1:
;; random : N -> N
;; calcula un número natural entre 0 y n-1
(define (random n) ...)
Dos empleos sucesivos de (random n) pueden generar distintos resultados. Considérese la
siguiente definición:
;; random-n-m : entero entero -> entero
;; …
;; supóngase: n < m
(define (random-n-m n m)
(+ (random (- m n)) n))
160
Formular una definición precisa y breve para random-n-m. Use una línea de intervalo para
explicar el resultado (random n). Use una evaluación simbólica en apoyo de la explicación.
Ejercicio 11.3.2 Desarrolllar la función tie-dyed. Consume un número natural y produce una lista
por la misma cantidad de números, cada uno seleccionado aleatoriamente entre el rango de 20 y
120. Use tie-dyed para dibujar círculos del ejercicio 9.5.8.
Ejercicio 11.3.3 Desarrollar la función crear-temps. Consume un número natural n y dos enteros,
denominados bajo y alto. Produce una lista de n enteros que están entre bajo y alto.
Emplear crear-temps para probar verifica-rango del ejercicio 9.5.4.
Finalmente, discuta las siguientes preguntas. ¿Se puede suministrar el resultado de crear-temps en
verifica-rango o se requiere saber la lista producida por crear-temps? Existen valores para bajo y
alto tales que no se requiere saber el resultado de crear-temps y aún predecir el resultado de la
prueba? ¿Qué función prueba qué? ¿Qué nos dice acerca de probar automáticamente con datos de
prueba generados?
Ejercicio 11.3.4 Desarrollar la función crear-precios, la cual consume un número natural y
produce una lista con los correspondientes precios entre $.10 y $10.00 en incrementos de diez
centavos. Emplear crear-precios para probar tienda-de-a-peso? del ejercicio 9.5.3.
Sugerencia: ¿Cuántas monedas de diez centavos hay entre $.10 y $10.00
Ejercicio 11.3.5 Desarrollar un programa que visualice una protesta estudiantil. En preparación de
dicha protesta, un pequeño grupo de estudiantes se reúne para llenar globos de pintura. La protesta
típica emplea ‘red únicamente. De ahí que en la tarde de la protesta, los estudiantes entran al teatro
progresista de la universidad con globos que arrojan sobre los asientos.
La única entrada del programa es un número natural, el cual representa el número de globos
arrojados. La visualización debe emplear un lienzo que contenga una trama negra y las posiciones
de los globos:
161
Supóngase una distribución aleatoria de los globos sobre los asientos del teatro. Cada caja en la
trama representa un asiento. Configure el programa de forma que al cambiar sólo una variable
cambie el número de columnas en la trama y un cambio en otra cambie el número de líneas.
Sugerencia: Desarrolle una función auxiliar que dibuje un número dado de líneas en la dirección
vertical y horizontal.
11.4 Definiciones de datos opcionales para números naturales
Al emplear la definición de datos de números naturales estándar previa es fácil desarrollar todo
tipo de funciones en números. Considérese, por ejemplo, una función que multiplique los primeros
n números. O sea, que consume un número natural y multiplica todos los números entre 0
(excluyéndolo) y n (incluyéndolo). La función se denomina factorial y tiene la notación
matemática “!”. Su contrato es fácil de formular:
;; ! : N -> N
;; calcular n · (n - 1) · ... · 2 · 1
(define (! n) ...)
Consume un número natural y produce otro.
Especificar su relación entrada-salida es un poco más laborioso. Se sabe, por supuesto, cuál es el
producto de 1, 2, y 3, teniéndose
(= (! 3)
6)
y, de forma similar,
(= (! 10)
368 800)
La pregunta es qué hacer con la entrada 0. Según la definición informal del problema, ! se supone
producirá el producto de todos los números entre 0 (excluyéndolo) y n (incluyéndolo), el
argumento. Puesto que n es 0, esta petición es algo extraña debido a que no existen números entre
0 (excluyéndolo) y 0 (incluyéndolo). Se resuelve el problema siguiendo la convención matemática
y establecer que (! 0) se evalúa a 1.
De ahí, el resto es fácil. El formato para ! es evidentemente el de una función que procesa un
número:
162
(define (! n)
(cond
[(zero? n) ...]
[else ... (! (sub1 n)) ...]))
La respuesta en la primera cond-cláusula está dada: 1. En la segunda cláusula, la recursión
produce el producto de los primeros n – 1 números. Para obtener el producto de los primeros n
números, se requiere multiplicar el (valor de) la recursión por n. La figura 31 contiene la
definición completa de !.
Ejercicio 11.4.1 Determinar manualmente el valor de (! 2) y mediante DrScheme. También
probar con 10, 100 y 1000.
Nota: Los resultados de dichas expresiones son números grandes, más allá de las capacidades
nativas de otros lenguajes de programación.
Ahora supóngase que se desea diseñar la función producto-de-20, la cual calcula el producto de 20
(excluyéndolo) a un número n (incluyéndolo) que sea mayor o igual a 20. Se tienen varias
opciones. Primero, se puede definir una función que calcule (! n) y (! 20) y divida el primero
entre el último. Una argumentación matemática simple muestra que este enfoque de hecho genera
el producto de todos los números entre 20 (excluyéndolo) y n (incluyéndolo).
n  (n  1)  ...21  20  ...1
20  ...1
 = n  (n -1)  ...  21 
 n  ( n  1)  ...  21
20  ...1
20  ...1
Ejercicio 11.4.2 Emplear esa idea para definir producto, una función que consume dos números
naturales, n y m, donde m > n, y que produce el producto de los números entre n (excluyéndolo) y
m (incluyéndolo).
Luego, se puede aplicar la receta de diseño, comenzando con una caracterización precisa de la
entrada de la función. Evidentemente, las entradas pertenecen a los números naturales, pero se
sabe más que eso. Pertenece a la siguiente colección de números: 20, 21, 22, … Por ahora se sabe
cómo describir con precisión mediante una definición de datos:
Un número-natural [>= 20] es cualquiera de
1. 20
o
2. (add1 n) si n es un número natural [>= 20].
Notación: en contratos, se emplea N [>= 20] en lugar de “números naturales [>= 20].”
163
Empleando la nueva definición de datos, se puede formular el contrato para producto-de-20:
;; producto-de-20 : N [>= 20] -> N
;; calcular n · (n – 1) · … · 21 · 1
(define (producto-de-20 n-superior-20) …)
El primer ejemplo para la especificación entrada-salida de producto-de-20:
(= (producto-de-20 21)
21)
Puesto que la función multiplica todos los números entre 20 (excluyéndolo) y su entrada,
(producto-de-20 21) debe generar 21, el cual es el único número en el intervalo.
De forma parecida,
(= (producto-de-20 22)
462)
por la misma razón. Finalmente, se sigue la convención matemática y se conviene que
(= (producto-de-20 20)
1)
El formato para producto-de-20 es una adaptación directa del formato para !, o de cualquier
función que procesa números naturales:
(define (producto-de-20 n-superior-20)
(cond
[(= n-superior-20 20) …]
[else … (producto-de-20 (sub1 n-superior-20)) …]))
La entrada n-superior-20 es 20 o mayor. Si es 20, no tiene ningún componente según la definición
de datos. De otra forma, es el resultado de añadir 1 a un número natural [>= 20], se puede
recuperar este “componente” al restar 1. El valor de esta expresión selector pertenece a la misma
clase de datos que la entrada y es así un candidato para la recursión natural.
Completar el formato es igualmente directo. Como se ha especificado, el resultado de (productode-20 20) es 1, el cual determina la respuesta para la primera cond-cláusula. De otra forma,
(producto-de-20 (sub1 n-superior-20)) produce ya el producto de todos los números entre 20
(excluyéndolo) y n-superior-20 - 1. El único número no incluido en este rango es n-superior-20.
164
Por lo que (* n-superior-20 (producto-de-20 (sub1 n-superior-20))) es la respuesta correcta en la
segunda cláusula. La figura 31 contiene la definición completa de producto-de-20.
;;
!
: N -> N
;; calcular n * (n - 1) * ... * 2 * 1
(define (! n)
(cond
[(zero? n) 1]
[else (* n (! (sub1 n)))]))
;; producto-de-20 : N [>= 20] -> N
;; calcular n * (n – 1) * … * 21 * 1
(define (producto-de-20 n-superior-20)
(cond
[(= n-superior-20 20) 1]
[else (* n-superior-20 (producto-de-20 (sub1 n-superior-20)))]))
;; producto : N[límite] N[>= límite] -> N
;; calcular n * (n – 1) * … * (límite + 1) * 1
(define (producto límite n)
(cond
[(= n límite) 1]
[else (* n (producto límite (sub1 n))]))
Figura 31. Cálculo de factorial, producto-de-20, y producto
Ejercicio 11.4.3 Desarrollar producto-de-menos-11. La función consume un entero n mayor o
igual que -11 y produce el producto de todos los enteros entre -11 (excluyéndolo) y n
(incluyéndolo).
Ejercicio 11.4.4 En el ejercicio 11.2.2, se desarrolló una función que tabula una función
matemática f para un intervalo de forma (0, n].
Desarrollar la función tabular-f20, la cual tabula los valores de f para números naturales mayores
que 20. En particular, la función consume un número natural n mayor o igual que 20 y produce
una lista de posns, cada uno de los cuales tiene la forma (make-posn n (f n)) para alguna n entre
20 (excluyéndolo) y n (incluyéndolo).
Una comparación de ! y producto-de-20 sugiere que la pregunta natural de cómo diseñar una
función que multiplica todos los números naturales en un cierto rango. O sea, producto es como
producto-de-20 excepto que el límite no es parte de la definición de la función. En su lugar, es otra
entrada, lo cual sugiere el siguiente contrato:
165
;; producto : N N -> N
;; calcular n · (n – 1) · … · (límite + 1) · 1
(define (producto límite n) …)
La intención es que producto, igual que producto-de-20, calcula el producto de límite
(excluyéndolo) a algún número n (incluyéndolo) que es mayor o igual a límite.
Desafortunadamente, el contrato de producto, en contraste con producto-de-20, es más impreciso.
En particular, no describe la colección de números que producto consume como segunda entrada.
Dada su primera entrada, límite, se sabe que la segunda entrada pertenece a límite, (add1 límite),
(add1 (add1 límite)), etc. Si bien es fácil enumerar las posibles segundas entradas, también
muestra que la descripción de la colección depende de la primera entrada –una situación rara que
no habíamos encontrado antes–.
Aun si se asume límite como algún número, la descripción de datos para la segunda entrada es casi
obvia.
Sea límite un número natural. Un número natural [>= límite] (N[>= límite) es cualquiera de
1. límite o
2. (add1 n) si n es un número natural [>= límite].
En otras palabras, la definición de datos es como la de números naturales [>= límite] con 20,
remplazada por la variable límite. Por supuesto, en educación media, se refiere a N[>= 0] como
los números naturales, y N[>= 1] como los enteros positivos.
Con esta nueva definición de datos, se especifica el contrato para producto como sigue:
;; producto : N[límite] N[>= límite] -> N
;; calcular n · ( n – 1) · … · (límite + 1) · 1
(define (producto límite n) …)
O sea, se nombra la primera entrada, un número natural, con la notación [límite] y se especifica la
segunda entrada empleando el nombre para la primera.
El resto del desarrollo del programa es directo. Es básicamente el mismo que para producto-de-20
con 20, remplazado por límite completamente. La única modificación tiene que ver con la
recursión natural en el formato de la función. Puesto que la función consume un límite y un N[>=
límite], el formato debe contener una aplicación de producto a límite y (sub1 n):
(define (producto límite n)
166
(cond
[(= n límite) …]
[else … (producto límite (sub1 n)) …]))
Las demás cosas siguen igual. La definición completa está en la figura 31.
Ejercicio 11.4.5 En los ejercicios 11.2.2 y 11.4.4, se desarrollaron funciones que tabulan f desde
algún número natural o número natural [>= 20] hasta algún 0 o 20 (excluyéndolo),
respectivamente.
Desarrollar la función tabular-f-lim, la cual tabula los valores de f de forma análoga desde algún
número natural n hasta alguno otro límite.
Ejercicio 11.4.6 En los ejercicios 11.2.2, 11.4.4, y 11.4.5, se desarrollaron funciones que tabulan
la función matemática f en varios rangos. En ambos casos, la función final generó una lista de
posns ordenados descendentemente. O sea, una expresión como (tabula-f 3) devuelve la lista
(cons (make-posn 3 2.4)
(cons (make-posn 2 3.4)
(cons (make-posn 1 3.6)
(cons (make-posn 0 3.0)
empty))))
Si se prefiere una lista de posns en orden ascendente, se debe hacer una colección de datos
diferente, números naturales hasta cierto punto superior en la cadena:
Un número natural [<= 20] (N[<=20] ) es cualquiera de
1. 20 o
2. (sub1 n) si n es un número natural [<= 20].
Por supuesto, en educación media, se denomina a N[<= -1] como los enteros negativos.
Desarrollar la función
;; tabular-f-hasta-20 : N[<= 20] -> N
(define (tabular-f-up-to-20 n-inferior-20) …)
la cual tabula los valores de f para números naturales menores a 20. En particular, consume un
número natural n menor o igual a 20 y produce una lista de posns, cada uno de los cuales tiene la
forma (make-posn n (f n)) para algún n entre 0 y n (incluyéndolo).
167
Ejercicio 11.4.7 Desarrollar la función no-es-divisible-por<= i. la cual consume un número natural
[>= 1], i, y un número natural m, con i < m. Si m no es divisible entre cualquier número entre 1
(excluyéndolo) e i (incluyéndolo), la función produce true; de otra forma, la salida es false.
Emplear no-es-divisible-por<=i para definir primo?, el cual consume un número natural y
determina si es o no primo.
11.5 Más en la naturaleza de los números naturales
Los números naturales son un pequeño conjunto de los números Scheme, no de todos. De ahí que
el formato de la función previo no puede emplearse para procesar números arbitrarios, en
particular, los inexactos. A pesar de lo cual, el formato es un buen comienzo para funciones cuyas
definiciones involucran tanto números naturales como otros números Scheme. Para ilustrar lo
anterior, se diseña la función suma-a-pi, la cual consume un número natural n y produce n + 3.14
sin emplear +.
Siguiendo la receta de diseño, se inicia con
;; suma-a-pi : N -> número
;; calcular n + 3.14 sin emplear +
(define (suma-a-pi n) …)
Otro paso fácil es determinar la salida para unas cuantas entradas:
(= (suma-a-pi 0) 3.14)
(= (suma-a-pi 2) 5.14)
(= (suma-a-pi 6) 9.14)
La diferencia entre el contrato de holas (véase ejercicio 11.2.1) y el de suma-a-pi es la salida, pero
como se ha visto esto no afecta el diseño del formato. Se obtiene el formato para suma-a-pi
renombrando de forma apropiada el de holas:
(define (suma-a-pi n)
(cond
[(zero? n) …]
[else … (suma-a-pi (sub1 n)) …])))
En combinación con los ejemplos, el formato sugiere de forma inmediata cómo completar la
función. Si la entrada es 0, la respuesta de suma-a-pi es 3.14. De otra forma, (suma-a-pi (sub1
n)) produce (- n 1) + 3.14; puesto que la respuesta correcta es (suma-a-pi (sub1 n))). La figura 32
contiene la definición completa de la función.
168
;; suma-a-pi : N -> número
;; calcular n + 3.14 sin emplear +
(define (suma-a-pi n)
(cond
[(zero? n) 3.14]
[else (add1 (suma-a-pi (sub1 n))]))
Figura 32. Sumar un número natural a pi
Ejercicio 11.5.1 Definir suma, la cual consume dos números naturales, n y x, y produce n + x
sin emplear +, definida por Scheme.
Ejercicio 11.5.2 Desarrollar la función multiplicar-por-pi, la cual consume un número natural y
lo multiplica por 3.14 sin emplear *. Por ejemplo,
(= (multiplicar-por-pi 0) 0)
(= (multiplicar-por-pi 2) 6.28)
(= (multiplicar-por-pi 3) 9.42)
Definir multiplicar, la cual consume dos números naturales, n y x, y produce n * x sin emplear *
de Scheme. También, eliminar + de dichas definiciones.
Sugerencia: Recordar que multiplicar x por n significa sumar x a sí mismo n veces.
Ejercicio 11.5.3 Desarrollar la función exponente, la cual consume un número natural n y un
número x y calcula
xn
Eliminar * de la definición, también.
Sugerencia: Recordar que elevar n a la x significa multiplicar x por sí mismo n veces.
Ejercicio 11.5.4 Una lista profunda (véase ejercicio 11.2.4) es otra representación para los
números naturales. Muéstrese cómo representar 0, 3, y 8.
Desarrollar la función sumaLP, la cual consume dos listas profundas, siendo números naturales n
y m, y produce una lista profunda representando n + m.
169
SECCIÓN 12
Componer funciones, nueva revisión
En la sección 3 se dijo que los programas son colecciones de definiciones de funciones y, también,
de algunas definiciones de variables; para orientar la división del trabajo entre funciones,
conviene:
Formular definiciones de funciones auxiliares para cada dependencia entre cantidades en
el enunciado del problema.
Dicho lineamiento ha sido razonablemente efectivo, pero ahora es tiempo de revisarlo y
acompañarlo de orientaciones adicionales relacionadas con funciones auxiliares.
En la primera subsección, se depura la primera orientación relacionada con programas auxiliares.
Las sugerencias formulan en palabras la experiencia adquirida con los ejercicios. La segunda y la
tercera ilustran dos de las ideas a mayor profundidad; la última es un ejercicio ampliado.
12.1 Diseño de programas complejos
Al desarrollar un programa, se busca instrumentarlo con una sola definición de función, sin
embargo, es necesario estar preparado para escribir funciones auxiliares; en particular, si la
declaración del problema menciona varias dependencias, es natural expresar cada una como una
función. Otros que lean la declaración del problema y el programa pueden seguir nuestro
razonamiento con más facilidad de este modo. El ejemplo del cine en la sección 3.1 es un buen
ejemplo para este estilo de desarrollo.
De otra forma, se debe seguir la receta de diseño e iniciar un análiss completo de los datos de
entrada y salida. Empleando el análisis de datos, se diseña un formato y se busca convertirlo en
una definición de función completa, lo cual requiere combinar los valores de las subexpresiones
del formato en una respuesta final, pudiéndose presentar las siguientes situaciones:
1. Si la formulación de una respuesta requiere analizar los casos de los valores de las
variables disponibles, emplear una cond-expresión.
170
2. Si el cálculo requiere conocimiento de un dominio de aplicación particular, como
dibujar en un lienzo (computacional), contabilidad, música o ciencia, entre otros,
emplear funciones auxiliares.
3. Si el cálculo requiere procesar una lista, un número natural, o cualquier otra pieza de
dato de tamaño arbitrario, emplear una función auxiliar.
4. Si la formulación natural de la función no es exactamente lo que se desea,
probablemente es una generalización del propósito que se persigue, por lo que en dicho
caso la función principal es una definición recortada que difiere el cálculo a un
programa generalizado auxiliar.
Los dos últimos criterios son situaciones que no se han discutido aún. Las siguientes dos
subsecciones los ilustran con ejemplos.
Después de determinar la necesidad de una función auxiliar, se añade el contrato, un
encabezamiento y una declaración de propósito, a las funciones de la LISTA DE DESEOS36.
Guía para la lista de deseos
Mantener una lista de funciones que se deben desarrollar
para completar un programa. Desarrollar cada función
según la receta de diseño correspondiente.
Antes de colocar una función en la lista de deseos, se debe verificar si una función parecida existe
o si no está ya en la lista de deseos. Scheme proporciona muchas operaciones y funciones
primitivas, igual que otros lenguajes. Se debe explorar tanto como sea posible nuestro lenguaje de
trabajo, pero solamente cuando nos hemos establecido en uno; para principiantes un conocimiento
superficial de un lenguaje es suficiente.
Seguir dichas orientaciones conduce a intercalar el desarrollo de una función con la de otras,
cuando se concluya una función que no depende de ninguna otra de la lista de deseos, se prueba.
Una vez que se han probado las funciones básicas, se pueden probar otras funciones hasta concluir
las de la lista de deseos; al probar cada función rigurosamente antes de probar las que dependen de
ella, se reduce el esfuerzo de búsqueda de errores lógicos.
36
El término “lista de deseos” en este contexto se debe al Dr. John Stone.
171
12.2 Funciones recursivas auxiliares
A menudo las personas requieren ordenar cosas, inversionistas ordenan sus portafolios según la
ganancia que cada inversión genera; doctores ordenan listas de pacientes que requieren
transplantes, programas de correo ordenan mensajes, en general, ordenar listas de valores de
acuerdo algun criterio es algo que muchos programas requieren realizar.
Aquí se analiza cómo ordenar una lista de números, no debido a su importancia en muchas tareas
de programación, sino porque proporciona un un buen caso de estudio del diseño de programas
auxiliares. Una función de ordenamiento consume una lista y genera otra, si bien ambas contienen
los mismos números, la lista generada los contiene en orden diferente. Lo cual es la esencia del
contratro y de la declaración de propósito:
;; ordena : lista-de-números -> lista-de-números
;; crear una lista ordenada de números a partir de los contenidos en una-lista-de-números,
uldn
(define (ordena uldn) ...)
un ejemplo por cláusula en la definición de datos es
(ordena empty)
;; valor esperado:
empty
(ordena (cons 1297.04 (cons 20000.00 (cons -505.25 empty))))
;; valor esperado:
(cons 20000.00 (cons 1297.04 (cons -505.25 empty)))
La respuesta para la entrada empty es empty, debido a que empty contiene los mismos ítems
(ninguno) y ordenados.
A continuación se debe traducir la definición de datos en un formato de función. Otra vez, se
opera con listas de números como antes, lo cual es fácil.
(define (ordena uldn)
(cond
[(empty? uldn) ...]
[else ... (first uldn) ... (ordena (rest uldn)) ...]))
172
Con base en dicho formato, se pasa a la parte interesante del desarrollo de programas. Se
considera cada cond-expresión por separado, iniciando con el caso más simple. Si la entrada de
ordena es empty, entonces, la lista ordenada es empty, como especifica el ejemplo. Suponiéndose
que no es empty la entrada, o sea operando con la segunda cond-cláusula. Contiene dos expresiones y, de acuerdo con la receta de diseño, se debe entender qué calculan:
1. (first uldn) obtiene el primer número,
2. (ordena (rest uldn)) genera una versión ordenada de (rest uldn), conforme el propósito
de la función.
Conjuntando esos resultados si se inserta el primero en su lugar adecuado en el resto de la lista
ordenada.
Para el caso del segundo ejemplo en dicho contexto. Cuando ordena consume (cons 1297.04
(cons 20000.00 (cons -505.25 empty))), entonces
1. (first uldn) obtiene1297.04,
2. (rest uldn) es (cons 20000.00 (cons -505.25 empty)), y
3. (ordena (rest uldn)) genera (cons 20000.00 (cons -505.25 empty)).
La respuesta buscada requiere insertar 1297.04 entre los dos números de esta última lista. La
respuesta en la segunda cond-línea debe ser una expresión que inserta (first uldn) en lugar
apropiado de una lista ordenada (ordena (rest uldn)).
Insertar un número en una lista ordenada no es una tarea simple. Se requiere buscar a través de la
lista entera antes de conocer su lugar adecuado. Buscar a través de una lista, sin embargo, puede
realizarse con una función, debido a que las listas son de tamaño arbitrario procesarlas requiere
funciones recursivas. Se necesita desarrollar una función auxiliar que inserte un número en una
lista ordenada, buscando en la lista para encontrar el lugar apropiado, denominemos a dicha
función inserta y formulemos una entrada en la lista de deseos:
;; inserta : número uldn -> uldn
;; crear una lista de números con n y uldn ordenada de mayor a menor,
;; requiriéndose que uldn esté previamente ordenada
(define (inserta n uldn) ...)
con inserta, se completa la definición ordena:
(define (ordena uldn)
(cond
[(empty? uldn) empty]
[else (inserta (first uldn) (ordena (rest uldn)))]))
173
La respuesta en la segunda línea afirma que para producir el resultado final, ordena extrae el
primer ítem de la lista no vacía, calcula la versión ordenada del resto de la lista, e inserta el
primero en el último en el lugar apropiado.
Por supuesto, no se ha concluido hasta que se ha desarrollado inserta. Se tiene un contrato, un
encabezamiento, y la declaración de propósito. A continuación se requiere construir ejemplos para
la función. Puesto que la primera entrada de inserta es atómica, se elaboran ejemplos con base en
la definición de datos de listas. O sea, se considera primero qué debe producir inserta para un
número y empty. De acuerdo con la declaración de propósito de inserta, la salida debe ser una
lista, debe contener todos los números de la segunda entrada, y debe contener el primer
argumento. Lo que sugiere lo siguiente:
(inserta 5 empty)
;; valor esperado:
(cons 5 empty)
En lugar de 5, pudo haberse empleado cualquier otro número.
El segundo ejemplo debe emplear una lista no vacía, entonces, la idea de inserta fue sugerida por
dicho ejemplo cuando se analizó cómo ordena debe operar con listas no vacías. En particular, se
dijo que ordena tenía que insertar 1297.04 en (cons 2000.00 (cons -505.25 empty)) en el lugar
apropiado:
(inserta 1297.04 (cons 20000.00 (cons -505.25 empty)))
;; valor esperado:
(cons 20000.00 (cons 1297.04 (cons -505.25 empty)))
En contraste a ordena, la función inserta consume dos entradas. Pero sabemos que el primero es
un número y atómico. Por lo que al centrarse en el segundo argumento, el cual es una lista de
números y sugiere emplear el formato de procesamiento de listas una vez más.
(define (inserta n uldn)
(cond
[(empty? uldn) ...]
[else ... (first uldn) ... (inserta n (rest uldn)) ...]))
La única diferencia entre este formato y el de ordena es que éste requiere tomar en cuenta el
argumento adicional n.
Para cubrir lo indefinido en el formato de inserta, otra vez se procede con base en un análisis caso
por caso. El primero relacionado con la lista vacía. Conforme la declaración de propósito, inserta
ahora debe construir una lista empleando un número: n. De ahí que la respuesta en el primer caso es
(cons n empty).
174
El segundo caso es más complicado que eso. Cuando uldn no es empty,
1. (first uldn) es el primer número en uldn, y
2. (inserta n (rest uldn)) produce una lista ordenada que contiene n y todos los números
en (rest uldn).
El problema es cómo combinar dichas piezas de datos para obtener una respuesta. Considérese un
ejemplo:
(inserta 7 (cons 6 (cons 5 (cons 4 empty))))
Donde n es 7 y mayor que cualquier número de la segunda entrada. Por lo que es suficiente cons 7
en (cons 6 (cons 5 (cons 4 empty))). En cambio, cuando la aplicación es algo como
(inserta 3 (cons 6 (cons 2 (cons 1 (cons -1 empty)))))
n de hecho debe ser insertado en el resto de la lista. Más en concreto,
1. (first uldn) es 6
2. (inserta n (rest uldn) es (cons 3 (cons 2 (cons 1 (cons -1 empty))))
en este caso al colocar 6 al frente de la última lista se obtiene lo que se busca. Ahora se generaliza
a partir de los ejemplos. El problema requiere distinguir un caso adicional. Si n es mayor que (o
igual que) (first uldn), todos los ítems en uldn son menores que n; depués de todo, uldn está
ordenada. El resultado es (cons n uldn) para este caso. Sin embargo, si n es menor que (first uldn),
entonces aún no se encuentra el lugar apropiado para insertar n en uldn. Se sabe que el primer ítem
de el resultado debe ser (first uldn) y que n debe ser insertado en (rest uldn). El resultado final en
este caso es
(cons (first uldn) (inserta n (rest uldn)))
Debido a que esta lista contiene n y todos los ítems de uldn ordenados –que es lo que se requiere–.
La traducción de dicho análisis en Scheme requiere la formulación de una expresión condicional
que distinga entre dos casos posibles:
(cond
[(>= n (first uldn)) ...]
[(< n (first uldn)) ...])
A partir de aquí, sólo se requiere colocar expresiones de respuesta apropiadas en los dos condcláusulas. La figura 33 contiene las definiciones completas de inserta y ordena.
175
Terminología: Este programa de ordenamiento en particular se conoce como Ordena-Inserta en la
literatura de la programación.
;; ordena : uldn -> uldn (ordenada)
;; crear una lista de números con los mismos que uldn pero ordenados descendentemente
(define (ordena uldn)
(cond
[(empty? uldn) empty]
[(cons? uldn) (inserta (first uldn) (ordena (rest uldn)))]))
;; inserta : número uldn (ordenada) -> uldn
;; crear una lista de números de n y los números en uldn ordenada descendentemente
;; uldn está ordenada
(define (inserta n uldn)
(cond
[(empty? uldn) (cons n empty)]
[else (cond
[(>= n (first uldn)) (cons n uldn)]
[else (cons (first uldn) (inserta n (rest uldn)))] )]))
Figura 33. Ordenación de listas de números
Ejercicio 12.2.1 Desarrollar un programa que ordene listas de mensajes de correo por fecha.
Estructuras de correo se definen:
(define-struct correo (de fecha mensaje))
Un mensaje de correo es una estructura:
(make-correo nombre n s)
donde nombre es cadena, n es número y s es cadena.
También desarrollar un programa que ordene listas de mensajes de correo por nombre. Para
comparar dos cadenas alfabéticamente, emplear la primitiva string<?.
Ejercicio 12.2.2 La función busca:
;; busca : num lista-de-num -> boolean
(define (busca n uldn)
(cond
[(empty? uldn) false]
[else (or (= (first uldn) n) (busca n (rest uldn)))]))
176
Determinar si algún número ocurre en una lista de números. La función puede recorrer la lista
entera para encontrar que el número que nos interesa no está contenido en la lista.
Desarrollar la función busca-ordenada, que determina si un número ocurre en una lista ordenada
de números. La función debe aprovechar el hecho de que la lista esté ordenada.
Terminología: La función busca-ordenada lleva a una BÚSQUEDA LINEAL.
12.3 Generalización de problemas, generalización de funciones
Al considerar el problema de dibujar un polígono, o sea, una figura geométrica con un número
arbitrario de esquinas37. Una representación natural de un polígono es una lista de estructuras
posn.
Una lista-de-posns es
1. la lista vacía, empty, o
2. (cons p ldp) donde p es un posn y ldp es una lista de posns.
Si cada posn representa una esquina del polígono:
(cons (make-posn 10 10)
(cons (make-posn 60 60)
(cons (make-posn 10 60)
empty)))
entonces, lo anterior representa un triángulo. La pregunta es qué significa empty como polígono.
La respuesta es que empty no representa un polígono y por lo tanto no debe ser incluido en las
representaciones de la clase de polígonos. Un polígono debe tener cuando menos una esquina, y
las listas que representan polígonos deben contener cuando menos un posn. Lo que sugiere la
siguiente definición de datos:
Un polígono es
1. (cons p empty) donde p es un posn, o
2. (cons p ldp) donde p es una estructura posn y ldp es un polígono
37
Paul C. Fisher inspiró esta sección.
177
Brevemente, una discusión de cómo seleccionar un conjunto de datos (listas de posns) representa
la información deseada (polígonos geométricos) revela que nuestra selección fue inadecuada.
Revisando la definición de datos nos acerca a nuestras intenciones y facilita diseñar el programa.
Debido a que las primitivas de dibujo siempre que producen algo producen true, es natural sugerir
el siguiente contrato y declaración de propósito:
;; dibuja-polígono : polígono -> true
;; dibujar el polígono especificado por un-polígono
(define (dibuja-polígono un-polígono)
En otras palabras, la función dibuja líneas entre las esquinas y, si todas las primitivas de dibujo
operan correctamente, produce true. Por ejemplo, la lista previa de posns debe producir un
triángulo.
Aunque la definición de datos no es una variante del tema de listas que se ha usado bastante, el
formato es cercano al de una función de procesamiento de listas:
;; dibuja-polígono : polígono -> true
;; dibujar el polígono especificado por un-polígono
(define (dibuja-polígono un-polígono)
(cond
[(empty? (rest un-polígono)) ... (first un-polígono) ...]
[else ... (first un-polígono) ...
... (second un-polígono) ...
... (dibuja-polígono (rest un-polígono)) ...]))
Dado que ambas cláusulas en la definición de datos emplean cons, la primera condición debe
inspeccionar el resto de la lista, la cual es empty para el primer caso y no empty para el segundo.
Es más, en la primera cláusula, se puede añadir (first un-polígono); y en el segundo, no sólo se
tiene el primer ítem de la lista sino el segundo también. Después de todo, los polígonos generados
según la segunda cláusula consisten de cuando menos dos posns.
Ahora se puede remplazar los “…” en el formato para obtener una definición de función completa.
Para la primera cláusula, la respuesta debe ser true, debido a que no se tienen dos posns que
pudieran conectarse para formar una línea. Para la segunda cláusula, se tienen dos posns, se puede
dibujar una línea entre ellos, y se sabe que (dibuja-polígono (rest un-polígono)) dibuja todas las
líneas restantes. Puesto de otra forma, se puede escribir
(draw-solid-line (first un-polígono) (second un-polígono))
178
en la segunda cláusula debido a que se sabe que un-polígono tiene un segundo ítem. Ambos
(draw-solid-line …) y (dibuja-polígono …) producen true si todo resulta bien. Al combinar las
dos expresiones con and, dibuja-polígono dibuja todas las líneas.
A continuación está la definición de la función completa:
(define (dibuja-polígono un-polígono)
(cond
[(empty? (rest un-polígono)) true]
[else (and (draw-solid-line (first un-polígono) (second un-polígono) ‘red))
(dibuja-polígono (rest un-polígono)) )]))
Desafortunadamente, al probarse con el ejemplo del triángulo inmediatamente revela una falla. En
lugar de dibujar un polígono con tres lados, la función dibuja únicamente una curva abierta, que
conecta las esquinas pero no cierra la curva:
(10, 10)
(60, 60)
(10, 60)
En términos matemáticos, se ha definido una función más general que la que se desea. La función
que se ha definido debería denominarse “conecta-los-puntos” y no dibuja-polígono.
Pasar de esa función más general a la que queremos, se requiere imaginar alguna manera de
conectar el último punto al primero. Existen varias formas de lograrlo, pero todas requieren definir
una función principal en términos de la que se ha definido, o algo parecido. En otras palabras, se
define una función auxiliar en términos de una más general.
Una forma de definir la nueva función es añadir la primera posición de un polígono al final y
dibujar la nueva lista obtenida. Un método simétrico es seleccionar el último y añadirlo al frente
del polígono. Una tercera opción es modificar la versión previa de dibuja-polígono de modo de
que conecte el último posn con el primero. Aquí se instrumenta la segunda opción; los ejercicios
cubren las otras dos.
Para añadir el último punto de un polígono al frente de éste, se requiere algo como
(cons (último un-polígono) un-polígono)
179
donde último es alguna función auxiliar que extrae el último ítem de una lista no vacía. De hecho,
esta expresión es la definición de dibuja-polígono suponiendo que se defina último: véase la
figura 34.
Formular la entrada en la lista de deseos para último es inmediato:
;; último : polígono -> posn
;; extraer el último posn de un polígono
(define (último un-polígono) ... )
Y, debido a que último consume un polígono, se puede reusar el formato anterior
(define (último un-polígono)
(cond
[(empty? (rest un-polígono)) …(first un-polígono)…]
[else … (first un-polígono)…
… (second un-polígono)…
… (último (rest un-polígono))…]))
Sólo hay un paso pequeño para transformar el formato en una función completa. Si la lista es
empty con excepción de un ítem, éste es el resultado deseado. Si (rest un-polígono) es no empty,
(último (rest un-polígono)) determina el último ítem de un-polígono. La definición completa de
último se presenta al final de la figura 34.
;; dibuja-polígono : polígono -> true
;; dibujar el polígono especificado por un-polígono
(define (dibuja-polígono un-polígono)
(conecta-puntos (cons (último un-polígono) un-polígono)))
;; conecta-puntos : polígono -> true
;; dibuja conexiones entre los puntos de un-polígono
(define (conecta-puntos un-polígono)
(cond
[(empty? (rest un-polígono)) true]
[else (and (draw-solid-line (first un-polígono) (second un-polígono) ‘red)
(conecta-puntos (rest un-polígono)))]))
;; último : polígono -> posn
;; extraer el último posn en un-polígono
(define (último un-polígono)
(cond
[(empty? (rest un-polígono)) (first un-polígono)]
[else (último (rest un-polígono))]))
Figura 34. Dibujar un polígono
180
El desarrollo de dibuja-polígono condujo naturalmente a considerar un problema más general:
conectar puntos, por lo que resolver el problema original requirió definir una función que emplea
(una variante de) la función más general. Este método de generalizar el propósito de una función
es muchas veces el mejor para simplificar un problema.
Ejercicio 12.3.1 Modificar dibuja-polígono de modo que añada el primer ítem de un-polígono a
su final. Esto requiere una función auxiliar diferente: sumar-al-final.
Ejercicio 12.3.2 Modificar conecta-puntos de forma que consuma un posn adicional al cual se
conecta el último posn conectado.
Entonces modificar dibuja-polígono para emplear esta nueva versión de conecta-puntos.
Acumulador: La nueva versión de conecta-puntos es una instancia simple de un estilo de función
denominado acumulador, cuya clase completa se considera en la parte VI.
12.4 Ejercicio ampliado: Arreglar palabras
Los periódicos ofrecen ejercicios que piden a los lectores encontrar todas las posibles palabras que
se pueden obtener de algunas letras. Una forma de jugar este juego es formar todos los posible
arreglos de las letras de forma sistemática y analizar cuáles arreglos son palabras de diccionario.
Supóngase que se tienen las letras “a”, “d”, “e”, y “r”. Existen veinticuatro posibles arreglos de
dichas letras:
ader
daer
dear
dera
aedr
eadr
edar
edra
aerd
eard
erad
erda
adre
dare
drae
drea
arde
rade
rdae
rdea
ared
raed
read
reda
la palabra legítima en la lista está “arde”.
La enumeración sistemática de todos los posibles arreglos es claramente una tarea para un
programa de computadora. Consume una palabra y produce una lista de palabras de los arreglos
palabra-por-palabra.
Una representación de una palabra es una lista de símbolos. Cada ítem en la entrada representa una
letra: ‘a, ‘b, …, ‘z. A continuación se presenta la definición de datos para palabras.
Una palabra es
1. empty, o
2. (cons a p) donde a es un símbolo (‘a, ‘b, …’z) y p es una palabra.
181
Ejercicio 12.4.1 Formular la definición de datos para listas de palabras. De forma sistemática
elaborar ejemplos de palabras y listas de palabras.
Denominemos a la función arreglos38. Su formato es el de una función que procesa una lista:
;; arreglos : palabra -> lista-de-palabras
;; crear una lista de todos los arreglos de las letras en una-palabra
(define (arreglos una-palabra)
(cond
[(empty? una-palabra) …]
[else … (first una-palabra) … (arreglos (rest una-palabra)) …] ) )
Dado el contrato, las definiciones de datos de apoyo, y los ejemplos, se puede analizar cada condlínea en el formato:
1. Si la entrada es empty, existe sólo un posible arreglo de la entrada: la palabra empty.
De ahí el resultado (cons empty empty), la lista que contiene la lista vacía es el único
ítem.
2. De otra forma existe una primera letra en la palabra, y (first una-palabra) es esa letra
y la recursión produce la lista de todos los posibles arreglos para el resto de la palabra.
Por ejemplo, si la lista es
(cons ‘d (cons ‘e (cons ‘r empty)))
Entonces la recursión es (arreglos (cons ‘e (cons ‘r empty))). Producirá el resultado
(cons (cons 'e (cons 'r empty))
(cons (cons 'r (cons 'e empty))
empty))
Para obtener todos los posible arreglos para la lista entera, ahora se debe insertar el
primer ítem, ‘d en nuestro caso, en todas estas palabras entre todas las posibles letras
y al inicio y al final.
La tarea de insertar una letra en muchas palabras diferentes requiere procesar una lista
arbitrariamente grande. De ahí que se requiera otra función, denominada insertar-entodo/en-laspalabras, para completar la definición de arreglos:
38
El término matemático es permutación.
182
(define (arreglos una-palabra)
(cond
[(empty? una-palabra) (cons empty empty)]
[else insertar-entodo/en-las-palabras (first una-palabra)
(arreglos (rest una-palabra)))]))
Ejercicio 12.4.2 Desarrollar la función insertar-entodo/en-las-palabras. Consume un símbolo y
una lista de palabras. El resultado es una lista de palabras como su segundo argumento, pero con
el primer argumento insertado entre todas las letras al inicio y al final de todas las palabras del
segundo argumento.
Sugerencia: Reconsiderar el ejemplo anterior. Nos detuvimos y decidimos que se requiere insertar
‘d en las palabras (cons ‘e (cons ‘r empty)) y (cons ‘r (cons ‘e empty)). De ahí que la
siguiente sea un candidato natural:
(insertar-entodo/en-las-palabras 'd
(cons (cons 'e (cons 'r empty))
(cons (cons 'r (cons 'e empty))
empty)))
para el paso “ejemplos de la función”. Tener presente que la segunda entrada corresponde a la
secuencia de palabras (parciales) “er” y “re”.
También, emplear la operación append de Scheme, la cual consume dos listas y produce su
concatenación. Por ejemplo:
(append (list 'a 'b 'c) (list 'd 'e))
= (list 'a 'b 'c 'd 'e)
Se discutirá el desarrollo de funciones como append en la sección 17.
183
SECCIÓN 13
Intermezzo 2: Abreviaciones de listas
Estudiante
intermedio
Emplear cons para crear listas puede ser engorroso si la lista contiene muchos ítems. Afortunadamente, Scheme proporciona la operación list, la cual consume un número arbitrario de
valores y crea una lista. La sintáxis ampliada de Scheme es
<prm> = list
La colección ampliada de valores es
<val> = (list <val> ... <val> )
Una forma más simple de comprender expresiones list es pensarlas como abreviaciones. En
particular, cada expresión de la forma
(list exp-1 … exp-n)
Representa una serie de n expresiones cons:
(cons exp-1 (cons … (cons exp-n empty)))
Recuérdese que empty no es un ítem de estas listas, sino del resto de la lista. Como muestran los
ejemplos:
(list 1 2)
= (cons 1 (cons 2 empty))
(list ‘Houston ‘Dallas ‘SanAntonio)
= (cons ‘Houston (cons ‘Dallas (cons ‘SanAntonio empty)))
(list false true false false)
= (cons false (cons true (cons false (cons false empty))))
184
Que introducen listas con dos, tres y cuatro ítems, respectivamente.
Por supuesto que se puede aplicar list no sólo a valores sino a expresiones:
(list (+ 0 1) (+ 1 1))
= (list 1 2)
Antes que la lista sea construida, las expresiones deben evaluarse. Si durante la evaluación de una
expresión ocurre un error, la lista nunca se forma:
(list (/ 1 0) (+ 1 1))
= /: divide by zero
O sea, list se comporta exactamente igual que cualquier otra operación primitiva.
El empleo de list simplifica mucho la notación para listas con muchos ítems y listas que contienen
listas o estructuras. Por ejemplo:
(list 0 1 2 3 4 5 6 7 8 9)
Esta lista contiene 10 ítems y su formación con cons y empty requeriría 10 empleos de cons y una
instancia de empty. De forma similar, la lista
(list (list 'bob 0 'a)
(list 'carl 1 'a)
(list 'dana 2 'b)
(list 'erik 3 'c)
(list 'frank 4 'a)
(list 'grant 5 'b)
(list 'hank 6 'c)
(list 'ian 8 'a)
(list 'john 7 'd)
(list 'karel 9 'e))
Requiere emplear 11 veces list en contraste con 40 cons y 11 de empty.
Ejercicio 13.1.1 Use cons y empty para construir el equivalente de las siguientes listas:
1. (list 0 1 2 3 4 5)
2. (list (list 'adam 0) (list 'eve 1) (list 'louisXIV 2))
3. (list 1 (list 1 2) (list 1 2 3)).
185
Ejercicio 13.1.2 Use list para construir el equivalente de las siguientes listas:
1. (cons 'a (cons 'b (cons 'c (cons 'd (cons 'e empty)))))
2. (cons (cons 1 (cons 2 empty)) empty)
3. (cons 'a (cons (cons 1 empty) (cons false empty)))
4. (cons (cons 1 (cons 2 empty)) (cons (cons 2 (cons 3 empty)) empty))
Inicie determinando cuántos ítems contiene cada lista y cada lista anidada.
Ejercicio 13.1.3 Es raro encontrar listas formadas con cons y list. Reformular las siguientes listas
mediante cons y empty de forma exclusiva:
1. (cons 'a (list 0 false))
2. (list (cons 1 (cons 13 empty)))
3. (list empty empty (cons 1 empty))
4. (cons 'a (cons (list 1) (list false empty))).
Luego formule las listas empleando list.
Ejercicio 13.1.4 Determine los valores de las expresiones siguientes:
1. (list (symbol=? 'a 'b) (symbol=? 'c 'c) false)
2. (list (+ 10 20) (* 10 20) (/ 10 20))
3. (list 'dana 'jane 'mary 'laura)
Ejercicio 13.1.5 Determine los valores de
(first (list 1 2 3))
(rest (list 1 2 3))
Emplear list facilita significativamente evaluar expresiones con listas. Por ejemplo, los pasos
recursivos de un ejemplo de la sección 9.5:
186
(suma (list (make-ri 'robot 22.05) (make-ri 'muñeca 17.95)))
= (+ (ir-price (first (list (make-ri 'robot 22.05) (make-ri 'muñeca 17.95))))
(suma (rest (list (make-ri 'robot 22.05) (make-ri 'muñeca 17.95)))))
= (+ (ir-price (make-ri 'robot 22.05))
(suma (list (make-ri 'muñeca 17.95))))
donde, se emplea una de las ecuaciones que gobiernan
las nuevas operaciones primitivas por primera vez:
= (+ 22.05
(suma (list (make-ri 'muñeca 17.95))))
= (+ 22.05
(+ (ir-price (first (list (make-ri 'muñeca 17.95))))
(suma (rest (list (make-ri 'muñeca 17.95))))))
= (+ 22.05
(+ (ir-price (make-ri 'muñeca 17.95))
(suma empty)))
= (+ 22.05 (+ 17.95 (suma empty)))
= (+ 22.05 (+ 17.95 0))
Puesto que las leyes de first y de rest resultan de valores de listas de forma natural, una evaluación empleando list no requiere expandir empleos de cons y empty.
Siguiendo una antigua convención de lenguajes de programación39, se pueden abreviar listas y
símbolos aún más. Si la lista es formulada con list, se puede simplemente convenir en eliminar list
y que cada paréntesis de apertura signifique por sí mismo y la palabra list. Por ejemplo,
'(1 2 3)
simplifica
(list 1 2 3)
o
(cons 1 (cons 2 (cons 3 empty))) .
De forma parecida,
'((1 2) (3 4) (5 6))
significa
(list (list 1 2) (list 3 4) (list 5 6)),
la cual puede ser expandida en expresiones cons y empty.
39
La convención se debe a LISP, un temprano y altamente avanzado lenguaje de programación diseñado en 1958.
Scheme hereda muchas ideas de LISP, pero es un lenguaje diferente.
187
Si se elimina la comilla en frente de símbolos, escribir listas de símbolos es rápido:
'(a b c)
Es una simplificación de
(list 'a 'b 'c)
Y, aún más,
'(<html>
(<title> My First Web Page)
(<body> Oh!))
representa
(list '<html>
(list '<title> 'My 'First 'Web 'Page)
(list '<body> 'Oh!))
Ejercicio 13.1.6 Reestablezca list y comilla donde sea necesario.
1.
'(1 a 2 b 3 c)
2.
'((alan 1000)
(barb 2000)
(carl 1500)
(dawn 2300))
3.
'((My First Paper)
(Sean Fisler)
(Section 1
(Subsection 1 Life is difficult)
(Subsection 2 But learning things makes it interesting))
(Section 2
Conclusion? What conclusion?))
188