Saltar a contenido

Ejercicios · PFC · Ordenamiento y alto orden

Once ejercicios para recorrer en el navegador, en el orden de la sesión: primero las tuplas, con lo que guardan y con lo que permiten escribir; después el ordenamiento por mezclas, y al final las funciones que ya traen el recorrido hecho. 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.

Lo que cambia frente a los ejercicios de listas es quién escribe el recorrido. Allá lo escribía usted con recursión; aquí lo traen map, filter y fold, y queda por decidir cuál de los tres sirve para cada cosa.

Tuplas

tuplas

Trece preguntas sobre una pareja y un triple: qué devuelve cada expresión, de qué tipo es y cuáles de cuatro declaraciones compilan. Las tres que no compilan traen lo que contesta el compilador, copiado de la corrida. El tamaño forma parte del tipo, y de ahí salen las dos cosas que más sorprenden: que _3 no exista en una pareja y que un patrón de dos nombres no sirva para un triple.

Tuplas en reconocimiento de patrones

sumarVec

La suma de dos vectores se puede escribir sin tuplas, y queda larga. Con (u, v) match los dos recorridos avanzan a la vez y cada caso dice qué hacer con un par: dos listas vacías, dos con cabeza, o una de cada clase, que es el error de tamaños distintos.

Ordenamiento por mezclas

msort

El árbol de llamadas se recorre por niveles: baja partiendo la lista por la mitad y sube mezclando. La frontera entre las tres cosas que hace la función queda marcada en el código, y es la misma frontera del ejercicio de la tarde.

merge

merge aislada, suponiendo que las dos listas llegan ordenadas. En cada paso usted elige qué cabeza sale, y el historial va armando la cadena de :: que devuelve la función. Si se equivoca, el mensaje dice qué comparación mandaba.

polimorfico

Qué hay que cambiar para que msort sirva con cualquier tipo, y qué se rompe si falta la función de comparación o si la llamada recursiva no la vuelve a pasar. Con x > y en lugar de x < y, la misma función ordena al revés.

Map y filter

mapFilter

Con la misma lista de entrada se predice qué devuelve map y qué devuelve filter. La diferencia que queda a la vista es la longitud: map transforma cada elemento y conserva cuántos hay, filter conserva los elementos y cambia cuántos quedan.

variaciones

Las cinco funciones emparentadas con filter, sobre la misma lista y con el mismo predicado. Además del resultado hay que decir a cuántos elementos se les llegó a aplicar el predicado, y ahí se parten en dos familias: las que recorren la lista entera y las que se detienen en el primero que no cumple. dropWhile devuelve cuatro elementos habiendo mirado tres.

empaquetar

empaquetar agrupa los elementos iguales que están seguidos, y para eso parte la lista con span en cada vuelta. La traza muestra el grupo que se está cerrando y lo que queda por recorrer.

codificar

empaquetar, map y una tupla, en ese orden. Primero se predice cuántos pares salen, que es el número de grupos y no el de elementos distintos: en List(1, 1, 2, 1, 1, 1) el 1 abre dos grupos separados por el 2 y deja dos pares. Las tres opciones equivocadas son lo que devuelven tres funciones parecidas.

Reduce y fold

reduceFold

Ocho preguntas sobre lo que más se enreda: con qué asociatividad acumula cada uno. reduceLeft y reduceRight dan resultados distintos con la resta, y reduce sobre la lista vacía falla, que es justo la razón de que fold pida un valor inicial.

reversaFold

La misma inversión del principio, ahora con foldLeft y sin recursión escrita a mano. El acumulador crece por el frente, y esa es toda la diferencia que hace falta para que la lista salga al revés.