I1M2013: El triángulo de Pascal en Haskell

En la tercera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentando soluciones del ejercicio 3 de la relación 17 sobre el triángulo de Pascal.

-- ---------------------------------------------------------------------
-- Ejercicio 3.1. El triángulo de Pascal es un triángulo de números
--          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. 
-- 
-- 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]]
-- ---------------------------------------------------------------------

-- 1ª definición (con iterate):
pascal :: [[Integer]]
pascal = iterate f [1]
    where f xs = zipWith (+) (0:xs) (xs++[0])

-- 2ª definición (con map):
pascal2 :: [[Integer]]
pascal2 = [1] : map f pascal2
    where f xs = zipWith (+) (0:xs) (xs++[0])


-- ---------------------------------------------------------------------
-- Ejercicio 3.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.

-- ---------------------------------------------------------------------

-- Ejercicio 3.1. El triángulo de Pascal es un triángulo de números

-- 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.

-- 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]]

-- ---------------------------------------------------------------------

-- 1ª definición (con iterate):

pascal :: [[Integer]]

pascal = iterate f [1]

where f xs = zipWith (+) (0:xs) (xs++[0])

-- 2ª definición (con map):

pascal2 :: [[Integer]]

pascal2 = [1] : map f pascal2

where f xs = zipWith (+) (0:xs) (xs++[0])

-- ---------------------------------------------------------------------

-- Ejercicio 3.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.

Se puede imprimir o compartir con