PeH: El triángulo de Pascal en Haskell
El triángulo de Pascal es un triángulo de números
|
1 2 3 4 5 6 7 |
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ............... |
construido de la siguiente forma
- la primera fila está formada por el número 1;
- las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.
La construcción del triángulo de Pascal sirve para ilustrar cómo se puede trabajar con listas infinitas en Haskell usando la evaluación perezosa como se muestra en los siguientes ejercicios.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
-- --------------------------------------------------------------------- -- Ejercicio 1. Definir la función -- pascal :: [[Integer]] -- tal que pascal es la lista de las líneas del triángulo de Pascal. Por -- ejemplo, -- ghci> take 6 pascal -- [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]] -- --------------------------------------------------------------------- pascal :: [[Integer]] pascal = [1] : map f pascal where f xs = zipWith (+) (0:xs) (xs++[0]) -- --------------------------------------------------------------------- -- Ejercicio 2. Escribir la traza del cálculo de la expresión -- take 4 pascal -- --------------------------------------------------------------------- -- Nota: El cálculo es -- take 4 pascal -- = take 4 ([1] : map f pascal) -- = [1] : (take 3 (map f pascal)) -- = [1] : (take 3 (map f ([1]:R1pascal))) -- = [1] : (take 3 ((f [1]) : map R1pascal))) -- = [1] : (take 3 ((zipWith (+) (0:[1]) ([1]++[0]) : map R1pascal))) -- = [1] : (take 3 ((zipWith (+) [0,1] [1,0]) : map R1pascal))) -- = [1] : (take 3 ([1,1] : map R1pascal))) -- = [1] : [1,1] : (take 2 (map R1pascal))) -- = [1] : [1,1] : (take 2 (map ([1,1]:R2pascal))) -- = [1] : [1,1] : (take 2 ((f [1,1]) : map R2pascal))) -- = [1] : [1,1] : (take 2 ((zipWith (+) (0:[1,1]) ([1,1]++[0]) : map R2pascal))) -- = [1] : [1,1] : (take 2 ((zipWith (+) [0,1,1] [1,1,0]) : map R2pascal))) -- = [1] : [1,1] : (take 2 ([1,2,1] : map R2pascal))) -- = [1] : [1,1] : [1,2,1] : (take 1 (map R2pascal))) -- = [1] : [1,1] : [1,2,1] : (take 1 (map ([1,2,1]:R3pascal))) -- = [1] : [1,1] : [1,2,1] : (take 1 ((f [1,2,1]) : map R3pascal))) -- = [1] : [1,1] : [1,2,1] : (take 1 ((zipWith (+) (0:[1,2,1]) ([1,2,1]++[0]) : map R3pascal))) -- = [1] : [1,1] : [1,2,1] : (take 1 ((zipWith (+) [0,1,2,1] [1,2,1,0]) : map R3pascal))) -- = [1] : [1,1] : [1,2,1] : (take 1 ([1,3,3,1] : map R3pascal))) -- = [1] : [1,1] : [1,2,1] : [1,3,3,1] : (take 0 (map R3pascal))) -- = [1] : [1,1] : [1,2,1] : [1,3,3,1] : [] -- = [[1],[1,1],[1,2,1],[1,3,3,1]] -- en el cálculo con R1pascal, R2pascal y R3pascal es la el triángulo de -- Pascal si el primero, los dos primeros o los tres primeros elementos, -- respectivamente. |
Destino
La anterior relación de ejercicios se ha elaborado para
- la asignatura de Informática de 1º del Grado en Matemáticas y
- la ampliación del libro Piensa en Haskell.
Fuentes
- Wikipedia. Triángulo de Pascal.
- Weisstein. Pascal’s Triangle. En MathWorld.