Con la definición de cada estructura se obtiene un constructor, un procedimiento que, dados los argumentos adecuados, genera una instancia o ejemplo de la estructura. Esto es útil para todas las estructuras que definimos; sin embargo, existen otras estructuras que se podrían llamar primitivas y que son la forma estándar de almacenar datos complejos en Scheme. Una lista en Scheme es la implementación de un tipo de dato abstracto; los elementos de la lista, puestos entre paréntesis, constituyen los datos. De esta manera, tanto las listas, que son datos, como los programas lucen igual. Algunos ejemplos de listas son:
(1 2 3 4 5)
(a b c 1 2 3)
("México" "Estados Unidos" "Francia" "España")
¿Qué hará DrScheme si se trata de evaluar una de las expresiones descritas arriba? Marca un error. Algo como "Aplicación de función: se esperaba un procedimiento, pero recibí: 1; los argumentos fueron: 2 3 4 5". DrScheme hizo lo que siempre hace para evaluar expresiones: tomar el primer elemento en la lista, que debe ser un procedimiento; evaluar los argumentos y realizar la aplicación.
Pero en este caso no se pretende que evalúe la expresión, sino que la considere en una lista. Se puede realizar lo anterior con un procedimiento que se llama quote, que emplea como abreviatura un apóstrofo ('). Por ejemplo:
> '(1 2 3 4 5)
(1 2 3 4 5)
Lo que hace (') es indicarle a DrScheme que no evalúe lo que sigue, sino que lo tome literal. Ya se conoce la primera forma de representar listas, pero, ¿cómo crearlas desde un programa? La forma más sencilla es utilizar alguno de los siguientes constructores de listas:
> (list 1 2 3 4 5)
(1 2 3 4 5)
> (cons 1 '(2 3 4 5))
(1 2 3 4 5)
> (append '(1 2) '(3 4 5))
(1 2 3 4 5)
Concepto
Un tipo de dato abstracto o ADT (por sus siglas en inglés) especifica un conjunto de datos y las operaciones para manipularlos. Estos tipos de datos son abstractos por su independencia de una implementación particular: no importa cómo se lleven a cabo las operaciones, sólo qué operaciones pueden hacerse y cuáles son sus efectos..
El constructor más empleado se llama list y reúne en una lista todos los elementos que recibe como argumentos. Por otro lado, uno de los constructores más poderosos que se utilizará con frecuencia es cons (de constructor, en inglés), ya que permite agregar un elemento al inicio de la lista. Recibe dos argumentos: un elemento y una lista. Finalmente,append posibilita unir dos listas en una.
Una lista vacía se representa con '() y DrScheme ofrece un predicado llamado empty? para que regrese #t si el argumento que recibe es la lista vacía. Para "desarmar" u obtener elementos particulares de la lista se tienen varias opciones:
> (define l (list 1 2 3 4 5))
> (first l)
1
> (second l)
2
> (rest l)
(2 3 4 5)
> (third l)
3v
> (nth l 3)
4
Para obtener elementos particulares del primero al octavo, DrScheme ofrece procedimientos particulares: first, second, third, fourth, fifth, sixth, seventh y eighth. En general, el que resulta más útil en los programas es first, junto con rest, que regresa una lista con todos los elementos de la lista original, excepto el primero. Finalmente, nth, devuelve el enésimo elemento en la lista; sin embargo, hay que tomar en cuenta que este procedimiento numera los elementos de la lista desde cero, así (nth lista 0) es igual a (first lista).
Ya se tiene suficiente información sobre el ADT, lista en Scheme, ahora se harán algunos programas para probar todo lo analizado. Aunque existe en Scheme un método primitivo llamado length, ¿cómo obtener la longitud de una lista? Una alternativa es la siguiente receta de diseño:
;; Contrato: longitud lista -> número
;; Propósito: Calcular la longitud (número de elementos)
;; en una lista.
;; Ejemplo: (longitud '(1 2 3 4 5)) debe producir 5
;; Definición:
(define (longitud lista)
(if (empty? lista)
0 ;; longitud lista vacía
+ 1 (longitud (rest lista)))))
;; Pruebas:
(longitud '(1 2 3 4 5))
(longitud '(a b c 1 2 3))
Es importante que primero se pregunte si la lista está vacía para no intentar desarmar con rest una lista vacía, lo que produciría que DrScheme marcara un error.
¿Cómo calcular la suma de todos los números en una lista? Se parece mucho al cálculo anterior, sólo que en lugar de sumar uno por uno, se suman todos los valores de los elementos de la lista. Aquí va con receta:
;; Contrato: suma lista -> número
;; Propósito: calcular la suma de todos los números
;; en una lista.
;; Ejemplo: (suma '(1 2 3 4 5)) debe producir 15
;; Procedimiento:
(define (suma lista)
(if (empty? lista)
0 ;; La suma de cero números
(+ (first lista) (suma (rest lista)))))
