Programación 1 - Práctica 5, Primera Parte

1 Listas

1.1 Introducción

Como #true o 5, '() puede verse como una constate.

Cuando agregamos un elemento a una lista, estamos construyendo otra lista. Para ello, usamos el constructor cons. Por ejemplo,

(cons "Juan" '())

construye una lista de un elemento a partir de la lista vacía '() y la cadena "Juan".

Una vez que contamos con una lista de un elemento, podemos construir listas de dos elementos usando nuevamente el constructor cons. Un ejemplo sería:

(cons "Pedro" (cons "Juan" '()))

Otro ejemplo posible:

(cons "María" (cons "Juan" '()))

A su vez, podemos construir una lista de tres elementos:

(cons "Jorge" (cons "María" (cons "Juan" '())))

También podemos construir listas de números. Un ejemplo de una lista que contiene los 10 dígitos podría ser la siguiente:

(cons 0

(cons 1

(cons 2

(cons 3

(cons 4

(cons 5

(cons 6

(cons 7

(cons 8

(cons 9 '()))))))))))

La construcción de esta lista se obtuvo de aplicar 10 veces el constructor cons y la lista vacía '().

En ciencias de la computación, las definiciones autoreferenciadas juegan un rol fundamental. Veamos, por ejemplo, cómo podemos definir una lista de contactos de una agenda:

; Contactos es:

; - '()

; - (cons String Contactos)

; interpretación: Contactos representa una lista de nombres de

; personas presentes en una agenda.

Ejercicio 1. Cree una lista de Contactos con cinco nombres.

Ejercicio 2. Explique por qué la siguiente lista

(cons "1" (cons "2" '()))

es un ejemplo de lista de Contactos y por qué (cons 2 '()) no lo es.

Miremos nuevamente la definición dada y prestemos atención a los ejemplos dados hasta ahora. Podrá notar que todos caen dentro de dos categorías: o bien son listas vacías '() o bien usan el constructor cons para agregar algo a una lista ya existente. El truco está en decir qué tipo de "listas existentes" queremos permitir. Una de las ventajas de las definiciones de datos autoreferenciadas es que permiten definir datos sin imponer restricciones de tamaño.

Ejercicio 3. Diseñe las listas de valores booleanos. Este tipo de dato debe permitir listas de cualquier longitud.

1.2 Operaciones sobre listas

Una vez que entendimos qué son las listas, debemos poder operar sobre ellas.

DrRacket provee un conjunto de operadores que podemos usar para manipular listas:

Estos operadores son suficientes para definir cualquier función que opere sobre listas. Sin embargo, y para simplificar la escritura de nuestros programas, racket nos provee una forma más sencilla de escribir listas.

Para denotar la lista vacía, escribiremos empty, mientras que para definir una lista con varios elementos, utlizaremos el operador list. Cuando querramos definir la lista

(cons a0 (cons a1 (.... (cons an empty))))

podremos escribir

(list a0 a1 ... an).

Por ejemplo, la lista que contiene los dígitos puede reescribirse como sigue:

(list 0 1 2 3 4 5 6 7 8 9).

Observación 1: Es importante notar que list no es un constructor, sino un operador que nos provee el lenguaje para simplificar la escritura de nuestros programas sobre listas.

Observación 2: Para utlizar estas abreviaturas de listas en DrRacket, es necesario cargar el lenguaje: Estudiante Principiante con Abreviaturas de Listas.

1.3 Programando con listas

Supongamos que por algún motivo Ud. mantiene una lista con los nombres de todos sus amigos. Pensemos que Ud. es alguien muy popular y que esa lista crece tanto que necesita de un programa que le permita buscar un nombre en la misma. Para transformar esta idea en un ejemplo concreto, pensemos en el siguiente problema:

Ud. se encuentra trabajando sobre la lista de contactos de un nuevo teléfono. El dueño del teléfono puede agregar y borrar nombres y consultar esta lista para cualquier nombre. Pensemos que a Ud. se la ha asignado la tarea de diseñar la función que toma la lista de contactos y determina si contiene el nombre "Marcos"

Veremos que siguiendo la receta de diseño vista en la Práctica 2, podemos obtener una solución al problema planteado.

1. Diseño de datos

   El tipo de datos Contactos definido anteriormente es apropiado para representar una lista de nombres que usará la función que queremos definir contiene-Marcos?.

   O sea que con esto completamos el primer paso de la receta.

2. Signatura y declaración de propósito

   Debemos proponer una signatura adecuada para la función contiene-Marcos? y brindar una declaración de propósito.

   Lo hacemos de la siguiente manera:

   ; contiene-Marcos? : Contactos -> Booleano

   ; dada una lista de Contactos, determina si "Marcos" es un elemento de la misma

3. Ejemplos

   Para completar el 3er paso debemos proponer ejemplos ilustrativos que sirvan para validar si la función contiene-Marcos? cumple con su propósito.

   Algunos ejemplos fáciles de calcular son:

   (check-expect (contiene-Marcos? '()) #false)

   (check-expect (contiene-Marcos? (cons "Sara" (cons "Pedro"  (cons "Esteban" '())))) #false)

   (check-expect (contiene-Marcos? (cons "A" (cons "Marcos" (cons "C" '())))) #true)

   (check-expect (contiene-Marcos? (cons "Juan" '())) #false)

   (check-expect (contiene-Marcos? (cons "Marcos" '())) #true)

4. Definición de la función

   En este paso, la idea es diseñar una función que se corresponda con el tipo de datos que va a usar. Dado que la definición de Contactos tiene dos cláusulas, el cuerpo de la función debe contener una expresión cond con dos condiciones.

   Las dos condiciones - (empty? l) y (cons? l) - determinan cuál de los dos tipos posibles de listas recibió la función.

   Un primer esbozo de la función sería el siguiente:

   (define (contiene-Marcos? l) (cond [(empty? l) ...]

   [(cons? l) ...]))

   Observación: Podemos reemplazar (cons? l) con else, pues nuestra función recibe sólo listas como dato de entrada.

   Si la primera condición es verdadera, entonces l es la lista vacía '(). En este caso no quedan dudas que la función contiene-Marcos? deberá devolver #false. Podemos ir completando la definición de la siguiente manera:

   (define (contiene-Marcos? l) (cond [(empty? l) #false]

   [(cons? l) ...]))

   En caso de que la segunda condición sea la verdadera, entonces l es una lista con al menos un elemento. Gracias a los operadores first y rest podemos separar el primer elemento de la lista y el resto de la misma.

   Podemos verificar entonces si el primer elemento de la lista coincide con el nombre "Marcos" usando el siguiente código:

   (string=? (first l) "Marcos")

   Si esta comparación resulta verdadera, entonces sabemos que la función contiene-Marcos? debe devolver #true. Si resulta falsa, será necesario buscar el nombre "Marcos" en el resto de la lista (rest l).

   Pero, cómo hacemos para buscar a "Marcos" en la lista (rest l)? Por suerte tenemos la función contiene-Marcos? que, según su declaración de propósito, determina si una lista contiene o no a "Marcos". Esto nos lleva al siguiente código:

   (contiene-Marcos? (rest l))

   Combinando ambos casos obtenemos el código final de la función contiene-Marcos?:

   (define (contiene-Marcos? l) (cond [(empty? l) #false]

   [(cons? l) (if (string=? (first l) "Marcos")

   #true

   (contiene-Marcos? (rest l)))]))

5. Evaluar el código en los ejemplos

   Podemos correr el código en DrRacket y veremos que los casos de prueba funcionan correctamente. Por esto no es necesario pasar al 6to paso de la receta.

Si juntamos todo, vemos que el diseño final obtenido es el siguiente:

; contiene-Marcos? : Contactos -> Booleano

; dada una lista de Contactos, determina si "Marcos" es un elemento de la misma

(check-expect (contiene-Marcos? '()) #false)

(check-expect (contiene-Marcos? (cons "Sara" (cons "Pedro"  (cons "Esteban" '())))) #false)

(check-expect (contiene-Marcos? (cons "A" (cons "Marcos" (cons "C" '())))) #true)

(check-expect (contiene-Marcos? (cons "Juan" '())) #false)

(check-expect (contiene-Marcos? (cons "Marcos" '())) #true)

(define (contiene-Marcos? l) (cond [(empty? l) #false]

[(cons? l) (if (string=? (first l) "Marcos")

#true

(contiene-Marcos? (rest l)))]))

Ejercicio 4. Use DrRacket para evaluar la función contiene-Marcos? usando la siguiente lista como entrada:

(cons "Eugenia"

(cons "Lucía"

(cons "Dante"

(cons "Federico"

(cons "Marcos"

(cons "Gabina"

(cons "Laura"

(cons "Pamela" '()))))))))

Ejercicio 5. Diseñe la función contiene? que determine si un string aparece en una lista de string.

DrRacket provee una función member? que toma dos valores y chequea que el primero aparezca en el segundo, este último debiendo ser una lista. Por ejemplo:

> (member? "Laura" (cons "a" (cons "b" (cons "Laura" '()))))

#true

No use member? para definir la función contiene?.

Ejercicio 7. Aquí vemos un tipo de dato que nos permite representar listas de montos de dinero:

Diseñe la función pos? que tome una Lista-de-numeros y determine si todos los elementos de la lista son positivos. En otras palabras, si (pos? l) devuelve #true, entonces l es un elemento del tipo de dato Lista-de-montos.

Use el evaluador paso a paso de DrRacket para entender cómo se evalúan las siguientes expresiones: (pos? (cons 5 '())) y (pos? (cons -1 '())).

Por último, diseñe la función checked-suma. Esta función recibe como entrada una Lista-de-numeros y devuelve la suma de sus elementos si la lista pertenece a Lista-de-montos; sino deberá devolver un string indicando un error.

Ejercicio 9. Diseñe:

• todos-verdaderos, una función que recibe como entrada una lista de valores booleanos y devuelve #true si todos los elementos de la lista son #true.

• uno-verdadero, una función que recibe como entrada una lista de valores booleanos y devuelve #true si al menos uno de los elementos de la lista es #true.

Ejercicio 10. Diseñe la función cant-elementos que dada una lista, devuelve la cantidad de elementos que contiene.

Ejercicio 11. Diseñe la función promedio, que devuelve el promedio de una lista de números. Sugerencia: No reinvente la rueda, use los ejercicios anteriores!

2 Clasificando elementos de una lista

Ejercicio 12. Diseñe una función pares que tome una lista de números l y devuelva una lista con los números pares de l.

Ejemplo:

pares (list 4 6 3 7 5 0)

= (list 4 6 0)

Ejercicio 13. Diseñe una función cortas que tome una lista de strings y devuelva una lista con aquellas palabras de longitud menor a 5.

Ejemplo:

cortas (list "Lista" "de" "palabras" "sin" "sentido")

= (list "de" "sin")

Ejercicio 14. Diseñe la función mayores, que dada una lista de números l y un número n, devuelve una lista con aquellos elementos de l que son mayores a n.

Ejercicio 15. Diseñe una función cerca que tome una lista de puntos del plano (representados mediante estructuras posn), y devuelva la lista de aquellos puntos que están a distancia menor a MAX de origen, donde MAX es una constante de su programa.

Ejemplo (considerando 5 para la constante) :

cerca (list (make-posn 3 5) (make-posn 1 2) (make-posn 0 1) (make-posn 5 6))

= (list (make-posn 1 2) (make-posn 0 1))

Ejercicio 17. Diseñe una función eliminar que tome una lista de números y un número y devuelva la lista luego de eliminar el número que indica el 2do argumento

Ejemplo:

(eliminar (list 1 2 3 2 7 6) 2)

= (list 1 3 7 6)

(eliminar (list 1 2 3 2 7 6) 0)

= (list 1 2 3 2 7 6)

3 Aplicando transformaciones a cada elemento de una lista

Ejercicio 19. Diseñe una función distancias que tome una lista de puntos del plano y devuelva una lista con la distancia al origen de cada uno.

Ejemplo:

(distancias (list (make-posn 3 4) (make-posn 0 4) (make-posn 12 5)))

= (list 5 4 13)

Ejercicio 20. Diseñe una función anchos que tome una lista de imágenes y devuelva una lista con el ancho de cada una.

Ejemplo:

(anchos (list (circle 30 "solid" "red") (rectangle 10 30 "outline" "blue")))

= (list 60 10)

Ejercicio 22. Diseñe una función cuadrados que tome una lista de números y devuelva otra lista donde los elementos que aparezcan sean el cuadrado de los elementos de la lista original.

Ejemplo:

(cuadrados (list 1 2 3))  = (list 1 4 9)

Ejercicio 23. Diseñe una función longitudes que tome una lista de cadenas y devuelva una lista de números que corresponda con la longitud de cada cadena de la lista original.

Ejemplo:

(longitudes(list "hola" "cómo" "estás?")) = (list 4 4 6)

Ejercicio 24. Diseñe la función convertirFC, que convierte una lista de temperaturas medidas en Fahrenheit a una lista de temperaturas medidas en Celsius.

4 Operando con los elementos de una lista

Ejercicio 28. Diseñe una función sumdist que tome una lista de puntos del plano y devuelva la suma de sus distancias al origen.

Ejemplo:

(sumdist (list (make-posn 3 4) (make-posn 0 4) (make-posn 12 5)))

= 22