Hasta ahora se ha hablado de datos simples: números o datos compuestos como las listas de números. Sin embargo, hay muchos ejemplos de programación que se relacionan con datos simbólicos; por ejemplo, editores de texto, software para realizar cálculos algebraicos o incluso interpretar y ejecutar programas, como DrScheme.
De hecho ya se mostró una forma de manejar cualquier tipo de datos, con quote ('); cuando lo utilizas con una lista, DrScheme no interpreta de manera usual la lista, la toma de manera literal. ¿Qué sucedería si se evalúa la siguiente expresión: 'hola? DrScheme, igual que con las listas, tomará literalmente hola y lo presentará en la pantalla; este tipo de elementos se llaman símbolos y Scheme ofrece un predicado para saber si algo es o no un símbolo: symbol?
Con esta información se distingue entre símbolos y valores, por ejemplo: > (define uno 1)
> (define dos 2)
> (list uno dos)
(1 2)
> (list 'uno 'dos)
(uno dos)
> (list 'uno uno)
(uno 1)
Ahora se mostrarán algunas primitivas más para trabajar con símbolos. Por ejemplo, con eq? Se puede saber si dos símbolos son iguales, es como = para números. Para mostrar su uso se hará un pequeño programa para buscar un símbolo en una lista; se procederá directo a la receta, porque es un procedimiento similar a los que ya se han revisado con números:
;; Contrato: símbolo lista -> booleano
;; Propósito: saber si un símbolo se encuentra en la lista
;; Ejemplos: (está? 'luis '(sergio josé ernesto luis jesús paco))
;; debe producir #t
;; Procedimiento:
(define (está? elem lista)
(cond ((empty? lista) #f)
((eq? elem (first lista)))
(else (está? elem (rest lista)))))
;; Pruebas:
(está? 'luis '(sergio josé ernesto luis jesús paco))
Todos los procedimientos que se han realizado hasta el momento son provistos por primitivas de Scheme. Hay un procedimiento llamado memq, parecido a está? que determina si un símbolo aparece en una lista. Observa, sin embargo, que no utiliza un signo de interrogación al final; esto se debe a que regresa la sublista a partir del elemento que se busca, si es que éste aparece, #f en caso contrario. Scheme provee un procedimiento llamado equal?, el cual se parece a eq? o a =, pero funciona con listas y, en general, con todo tipo de elementos del lenguaje.
Ahora regresando al problema de encontrar los puntos más cercanos en un conjunto de puntos. Para seguir el algoritmo definido en el módulo anterior, se intentará resolverlo por partes: primero, se atenderá la tarea de generar todas las parejas de puntos y, segundo, seguir el algoritmo para comparar las distancias, manteniendo siempre la menor (y los puntos con esa distancia). ¿Cómo encontrar todas las parejas de puntos posibles? Si se piensa que el conjunto es una lista, una alternativa es seleccionar el primer punto y armar parejas de éste con todos los siguientes, después tomar el segundo y armar parejas con todos los que le siguen. ¿Por qué ya no es necesario combinar el segundo elemento con el primero? Se explica con la receta:
(define (crea-parejas lista)
'()
(append (parejas (first lista) (rest lista))
(crea-parejas (rest lista)))))
Se puede notar que el procedimiento auxiliar parejas separa el primero de la lista y lo asocia con todos los que le siguen. Como la distancia entre los puntos de una pareja es un dato que se utilizará frecuentemente, es preferible calcularla al momento de crear la pareja y almacenar este valor. Conviene utilizar una nueva estructura:
(define-struct pareja (p1 p2 d))
(define (parejas elem lista)
(if (empty? lista)
'()
cons (make-pareja elem (first lista)
(distancia2 elem (first lista)))
(parejas elem (rest lista)))))
Nótese cómo al crear una pareja con make-pareja, se calcula la distancia entre ambos puntos de la pareja y se almacena. Sólo resta convertir en código el algoritmo que ya se ha explicado en el capítulo anterior:
;; Contrato: lista -> imprime el resultado
;; Propósito: regresar los dos puntos más cercanos entre sí.
;; Ejemplos: (puntos-más-cercanos '(p1 p2 ... pN))
;; donde cada punto es una estructura punto.
;; Procedimiento:
(define (puntos-más-cercanos lista)
(let ((lista-puntos (crea-parejas lista)))
(if (empty? lista)
(display "No hay suficientes puntos en la lista")
(menor-distancia (first lista-puntos) (rest listapuntos)))))
(define (menor-distancia menor lista)
(if (empty? lista)
(imprime menor)
(let ((siguiente (first lista)))
(menor-distancia
(if (< (pareja-d siguiente) (pareja-d menor))
;; Tenemos un nueva pareja más cercana siguiente
;; La pareja "menor" sigue siendo la más pequeña menor)
(rest lista)))))
En este caso, el procedimiento auxiliar, menor-distancia, es el encargado de comparar las distancias ya calculadas, entre todas las parejas de puntos. La idea es muy sencilla: se tienen N parejas en la lista; entonces, se asume que la primera es la de menor distancia y se pasa con el argumento menor de menor-distancia y el resto de las parejas. El procedimiento auxiliar compara la distancia de este supuesto menor con la distancia de la siguiente pareja y, si es menor esta última, se hace la llamada recursiva, pero ahora la segunda pareja es menor, y así sucesivamente. Aquí están unos ejemplos de su ejecución:
> (define p1 (make-punto 1 1))
> (define p2 (make-punto 2 2))
> (define p3 (make-punto 5 5))
> (puntos-más-cercanos (list p1 p2 p3))
Distancia más pequeña: P1(1,1) - P2(2,2) = 1.4142135623730951
> (define p4 (make-punto 5.5 6))
> (puntos-más-cercanos (list p4 p2 p3 p1))
Distancia más pequeña: P1(5.5,6) - P2(5,5) = 1.118033988749895
Este programa es un ejemplo típico de construcción modular de soluciones, similar a la construcción de un edificio, por ejemplo la catedral de la Sagrada Familia, que se ilustra en el inicio de este capítulo. Se trata de un problema complicado, dividido en varios subproblemas más sencillos, cada uno con un procedimiento (como encontrar la menor distancia o crear todas las parejas de puntos) que, al combinarlos, ofrecen la solución final.
