Introducción a la Programación
Clases teóricas
por Pablo E. “Fidel” Martínez López
9. Listas
Repaso
Repaso
Repaso
● Programar es comunicar (con máquinas y personas)
○ Estrategia de solución (división en subtareas)
○ Legibilidad (elección de nombres, indentación)
■ CONTRATOS: Propósito, parámetros y precondiciones
● Programas (texto con diversos elementos)
○ Comandos: describen acciones
○ Expresiones: describen información
■ Tipos: clasifican expresiones
Repaso
● Comandos
○ Primitivos y secuencia
○ PROCEDIMIENTOS (con y sin parámetros)
○ Repetición simple (repeat)
○ Alternativa condicional (if-then-else)
○ Repetición condicional (while)
○ Asignación de variables (:=)
Repaso
● Expresiones
○ Valores literales y expresiones primitivas
○ Operadores
numéricos, de enumeración, de comparación, lógicos
○ Alternativa condicional en expresiones (choose)
○ FUNCIONES (con y sin parámetros, con y sin procesamiento)
○ Parámetros y variables (como datos)
○ Constructores (de registros y variantes)
○ Funciones observadoras de campo
Repaso
● Tipos de datos
○ Básicos
Colores, Direcciones, Números, Booleanos
○ Registros (muchas partes de diferentes tipos)
○ Variantes (una parte, muchas posibilidades)
Listas
Listas
Listas
● Si queremos programar un juego de cartas, ¿cómo
representar un mazo de cartas?
○ No es un color, ni un número, ni otro tipo básico
○ No es un variante, porque tiene varios elementos (las cartas)
○ No es un registro, porque sus elementos son del mismo tipo
○ Necesitamos un nuevo tipo de datos
¡No siempre hay la
misma cantidad de
elementos!
Listas
● Las listas son datos con estructura
○ Tienen muchos elementos, todos del mismo tipo
○ Son datos, por lo que se pueden pasar como argumentos,
guardar en variables, retornar como resultados, etc.
○ Hay funciones para manipular listas
○ ¿Qué necesitamos para escribir listas?
Estas son funciones primitivas…
No podemos hacerlas nosotros
con las herramientas actuales
Listas
● Precisamos sintaxis para listas
○ ¿Cómo decimos cuál es la lista?
■ Constructores de listas
○ ¿Cómo obtenemos información de ella?
■ Funciones de acceso (primitivas)
Es mejor trabajar en texto
Listas
● Para construir listas de forma literal enumeramos sus
elementos entre corchetes
○ [ <exp1>, <exp2>, … , <expN> ]
○ Las expresiones deben ser todas del mismo tipo
○ ¡Puede haber listas con un elemento e incluso con cero!
Esta es una lista
SIN ELEMENTOS,
la lista vacía
Listas
● El tipo de una lista es “Lista de” el tipo de sus elementos
○ [42,99] es de tipo Lista de Números o [ Número ]
○ [ Norte ] es de tipo Lista de Direcciones o [Dirección]
○ [ Carta(palo<-Espadas, número<-1) ] es de tipo
Lista de Cartas o [ Carta ]
es una Lista de Números
(con un solo número)
¡No es lo mismo un
es un Número elemento que una
lista con un solo
elemento!
Listas
● Otra forma de construir listas es juntando dos existentes
● Para eso se usa el operador para agregar (append)
○ <expLista1> ++ <expLista2>
○ El resultado es una lista que tiene los elementos de
ambas, en el mismo orden
○ Es una operación asociativa
Tiene más sentido
cuando una de las listas
no es literal
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ con_agregadoAdelanteDeLaLista_
que dados un elemento y una lista, lo agrega adelante
■ Lo abreviamos cons(elemento, lista)
es equivalente a
es equivalente a
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ con_agregadoAdelanteDeLaLista_
que dados un elemento y una lista, lo agrega adelante
■ Lo abreviamos cons(elemento, lista)
Observar que ++ recibe
dos listas, la primera con
un solo elemento
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ laLista_con_AgregadoAtrás
que dados una lista y un elemento, lo agrega al final
■ Lo abreviamos snoc(lista, elemento)
es equivalente a
es equivalente a
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ laLista_con_AgregadoAtrás
que dados una lista y un elemento, lo agrega al final
■ Lo abreviamos snoc(lista, elemento)
Aquí, en cambio, la lista de
un solo elemento es la 2da
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ secuenciaAritméticaDeNúmerosDe_A_
que dados dos valores, devuelva la secuencia entre ellos
■ Precisamos una repetición simple y un acumulador de listas
es equivalente a
es equivalente a
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ secuenciaAritméticaDeNúmeros
que dados dos valores, devuelva la secuencia entre ellos
■ Precisamos una repetición simple y un acumulador de listas
La cantidad
de veces es
uno más que
la diferencia
entre los
extremos
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ secuenciaAritméticaDeNúmeros
que dados dos valores, devuelva la secuencia entre ellos
■ Precisamos una repetición simple y un acumulador de listas
es equivalente a
La expresividad de
la programación
en acción
Listas
● Las secuencias aritméticas pueden ser de otros tipos
○ ¿Cómo la definiríamos?
■ Con repetición condicional y siguiente (ejercicio…)
○ Para tipos básicos, Gobstones provee notación especial
■ [ <expValorInicial> .. <expValorFinal> ]
es equivalente a es equivalente a
es equivalente a es equivalente a
Listas
● Las secuencias aritméticas pueden tener elementos a
distancia mayor que uno
○ ¿Cómo la definiríamos? (Ejercicio…)
○ La sintaxis para secuencias no consecutivas es
■ [ <expInicial>, <expSegundo> .. <expFinal> ]
es equivalente a
es equivalente a
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ enTotal_IgualesA_, que dadas una cantidad y un
elemento, describe una lista con esa cantidad del elemento
■ Precisamos una repetición simple y un acumulador de listas
debe ser equivalente a
debe ser equivalente a
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ enTotal_IgualesA_, que dadas una cantidad y un
elemento, describe una lista con esa cantidad del elemento
■ Precisamos una repetición simple y un acumulador de listas
Inicializar un
acumulador
SOLAMENTE
tiene sentido en
una acumulación
Listas
● Combinando las operaciones definidas se pueden
expresar listas de maneras más poderosas…
es equivalente a
¿Y si fuesen muchos más?
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ filaActual
■ Precisamos la función celdaActual definida antes
¿Cómo sería?
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ filaActual
■ Precisamos la función celdaActual definida antes
Se agrega al
final para que el
orden sea el
mismo que en el
que fueron
recorridas
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ tableroActual
■ ¡Precisamos la función filaActual recién definida!
¿Cómo sería?
Listas
● Combinando listas literales y append se pueden
construir otras operaciones interesantes, por ejemplo
○ tableroActual
■ ¡Precisamos la función filaActual recién definida!
Se recorren las
filas y se agregan a
la lista
Listas
● ¿Cómo obtenemos información de una lista?
● Precisamos acceder a sus elementos…
○ ¡Funciones primitivas sobre listas!
○ ¿Cuál es el conjunto mínimo de primitivas que resulta
más conveniente tener?
¿ ¿Cómo estar
seguros que
lo elegido va
? a permitir
hacer otras
que no están
acá?
Listas
● ¿Cómo obtenemos información de una lista?
● Precisamos acceder a sus elementos…
○ ¡Funciones primitivas sobre listas!
○ ¿Cuál es el conjunto mínimo de primitivas que resulta
más conveniente tener?
Estas son las
elegidas.
Veremos
cómo hacer
los demás
Listas
● Un conjunto adecuado de primitivas debe permitir crear
todas las demás operaciones que se deseen
● El siguiente conjunto cumple esa condición
○ primero(<expLista>)
○ resto(<expLista>) (en bloques: “sinElPrimero_”)
○ esVacía(<expLista>) (en bloques: “¿estáVacía_?”)
¿Cuál es el contrato
de cada una?
Listas
● primero(<expLista>)
○ PROPÓSITO: describe el primer elemento de la lista dada
○ PRECONDICIÓN: la lista dada no es vacía
○ PARÁMETRO: la lista es de tipo Lista de “Elementos”
○ RESULTADO: un valor de tipo “Elemento”
es equivalente a es equivalente a
Se aplica a cualquier
lista, y funciona si no es equivalente a
está vacía
Listas
● resto(<expLista>)
○ PROPÓSITO: describe una lista con los elementos de la
lista dada, excepto que sin el primero de ellos
○ PRECONDICIÓN: la lista dada no es vacía
○ PARÁMETRO: la lista es de tipo Lista de “Elementos”
○ RESULTADO: un valor de tipo Lista de “Elementos”
es equivalente a es equivalente a
Se aplica a cualquier
es equivalente a lista, y funciona si no
está vacía
Listas
● esVacía(<expLista>)
○ PROPÓSITO: indica si la lista es vacía
○ PRECONDICIÓN: ninguna
○ PARÁMETRO: la lista es de tipo Lista de “Elementos”
○ RESULTADO: un valor de tipo Booleano
Se aplica a cualquier lista
es Falso
es Falso es Verdadero
Listas
● Con combinaciones de primero y resto podemos obtener
cualquier elemento
○ ¡Recordar respetar los tipos!
■ O sea, es un ERROR escribir (resto(primero([10,20])),
porque el argumento de resto debe ser una lista
El segundo queda primero
luego de sacar el primero
Listas
● Con combinaciones de primero y resto podemos obtener
cualquier elemento
○ ¡Recordar respetar los tipos!
Al sacar el primero 2 veces
seguidas, hay 2 elementos
menos
Listas
● Con combinaciones de primero y resto, podemos hacer
muchas otras operaciones
○ Contar, sumar o modificar elementos
○ Buscar, elegir, eliminar o agregar elementos
○ Todos implican recorrer la lista de a un elemento por vez
Éstas son solo algunas de
las que podemos hacer
Listas
● Con combinaciones de primero y resto podemos obtener
cualquier elemento
○ ¡Recordar respetar los tipos!
Y al sacar 2, el que queda
primero es el tercero
Listas
● Ejercicio:
○ construir una función que describa un mazo
mazoDeCartasEspañolas
○ Precisamos la función paloSiguiente_ definida antes
Cierre
Cierre
Cierre
● Listas
○ Son datos con estructura
○ Tienen muchas partes, pero no siempre la misma
cantidad
○ Se pueden crear a través de funciones constructoras
○ Se puede obtener información de ellas a través de
funciones de acceso
○ Se pueden hacer recorridos sobre los elementos de
una lista
○ Son un tipo de datos muy poderoso y útil
