Ejercicios · PFC · Listas¶
Cuatro ejercicios para recorrer en el navegador, en el orden de la sesión: cómo se arma y cómo se descompone una lista, qué patrón captura cuál, y qué queda pendiente en cada marco cuando una función la recorre entera. Ninguno muestra nada antes de que usted produzca algo: hay trazas que se llenan paso a paso, valores que hay que predecir antes de verlos y patrones entre los que hay que escoger. Lo que se compara en cada caso salió de correr el código de la sesión.
La idea que los atraviesa es que una lista se define por sus dos
constructores, Nil y ::, y que toda función que la recorra tiene un caso
por cada uno. Escribir ese recorrido a mano es el trabajo de aquí.
Construir y descomponer listas¶
construir¶
1 :: 2 :: 3 :: Nil se arma de derecha a izquierda, porque :: asocia por la
derecha. El paso a paso lo muestra naciendo desde Nil y después descompone
una lista de frutas con head, tail e isEmpty. El contador de la última
línea deja ver cuántas veces se llega a isEmpty sobre la lista vacía.
Reconocimiento de patrones con listas¶
patrones¶
Los cuatro patrones del match están en el orden en que los escribe la
sesión, y el ejercicio da una lista concreta y pregunta cuál la captura. El
punto está en que x :: Nil y x :: y :: Nil son casos de uno y de dos
elementos, mientras x :: xs toma cualquier lista no vacía: por eso el orden
en que se escriben decide cuál gana.
Funciones recursivas sobre listas¶
reversa¶
reversa es recursión lineal: en cada marco queda pendiente un ++ List(x)
que solo se resuelve al desarmar la pila. La traza cuenta las celdas que
recorre la concatenación, y ahí se ve de dónde sale el costo cuadrático con
una lista de cuatro elementos.
Ordenamiento por inserción¶
insercion¶
Antes de cada paso usted dice en qué posición va a quedar el elemento que se
inserta, y después lo comprueba. insertar recorre la parte ya ordenada hasta
hallar su sitio, y iSort la llama una vez por elemento.