I1M2014: Programación dinámica en Haskell

En la segunda parte de la clase de hoy del curso Informática de 1º del Grado en Matemáticas hemos estudiado la técnica de programación dinámica.

En primer lugar, se explicó el patrón de la programación dinámica. A continuacin, se aplicó al problema de la sucesión de Fibonacci y problema del producto de cadenas de matrices.

Las transparencias usadas en la clase son las páginas 1-21 del tema 24:

El código del patrón de programación dinámica es

module Dinamica (module Tabla, dinamica)  where

import Data.Array
import I1M.Tabla as Tabla

dinamica :: Ix i => (Tabla i v -> i -> v) -> (i,i) -> Tabla i v
dinamica calcula cotas = t
    where t = tabla [(i,calcula t i) | i <- range cotas]

module Dinamica (module Tabla, dinamica) where

import Data.Array

import I1M.Tabla as Tabla

dinamica :: Ix i => (Tabla i v -> i -> v) -> (i,i) -> Tabla i v

dinamica calcula cotas = t

where t = tabla [(i,calcula t i) | i <- range cotas]

El código de la sucesión de Fibonacci con programación dinámica es

import I1M.Dinamica

-- ---------------------------------------------------------------------
-- Fibonacci como ejemplo de programación dinámica.                   --
-- ---------------------------------------------------------------------

-- (fib n) es el n-ésimo término de la sucesión de Fibonacci, calculado
-- mediante programación dinámica. Por ejemplo, 
--    fib 8  ==  21
fib :: Int -> Int
fib n = valor t n
    where t = dinamica calculaFib (cotasFib n) 

-- (calculaFib t i) es el valor de i-ésimo término de la sucesión de
-- Fibonacci calculado mediante la tabla t que contiene los
-- anteriores. Por ejemplo,
--    calculaFib (tabla []) 0                                     ==  0
--    calculaFib (tabla [(0,0)]) 1                                ==  1
--    calculaFib (tabla [(0,0),(1,1)]) 2                          ==  1
--    calculaFib (tabla [(0,0),(1,1),(2,1)]) 3                    ==  2
--    calculaFib (tabla [(0,0),(1,1),(2,1),(3,2)]) 4              ==  3
--    calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3)]) 5        ==  5
--    calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5)]) 6  ==  8
-- Además,
--    ghci> dinamica calculaFib (0,8)
--    Tbl [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21)]
calculaFib :: Tabla Int Int -> Int -> Int
calculaFib t i | i <= 1    = i
               | otherwise = valor t (i-1) + valor t (i-2)

-- (cotasFib n) son las cotas del vector que se necesita para calcular
-- el n-ésimo término de la sucesión de Fibonacci mediante programación
-- dinámica. 
cotasFib :: Int -> (Int,Int)
cotasFib n = (0,n)

-- ---------------------------------------------------------------------
-- Fibonacci mediante divide y vencerás                               --
-- ---------------------------------------------------------------------

-- (fibR n) es el n-ésimo término de la sucesión de Fibonacci calculado
-- mediante divide y vencerás. Por ejemplo, 
--    fibR 8  ==  21
fibR :: Int -> Int
fibR 0 = 0
fibR 1 = 1
fibR n = fibR (n-1) + fibR (n-2)

-- Comparación
--    ghci> fib 20
--    6765
--    (0.01 secs, 524824 bytes)
--    ghci> fibR 20
--    6765
--    (0.06 secs, 2165236 bytes)
--    ghci> fib 30
--    832040
--    (0.01 secs, 0 bytes)
--    ghci> fibR 30
--    832040
--    (6.46 secs, 222602404 bytes)

-- ---------------------------------------------------------------------
-- Fibonacci mediante programación dinámica con listas infinitas      --
-- ---------------------------------------------------------------------

-- fibs es la lista de los términos de la sucesión de Fibonacci. Por
-- ejemplo, 
--    take 10 fibs  ==  [0,1,1,2,3,5,8,13,21,34]
fibs :: [Int]
fibs = 0:1:[x+y | (x,y) <- zip fibs (tail fibs)]

-- (fib' n) es el n-ésimo término de la sucesión de Fibonacci, calculado
-- a partir de fibs. Por ejemplo, 
--    fib' 8  ==  21
fib' :: Int -> Int
fib' n = fibs!!n

-- Comparaciones:
--    ghci> fib 30
--    832040
--    (0.02 secs, 524808 bytes)
--    ghci> fib' 30
--    832040
--    (0.01 secs, 542384 bytes)

import I1M.Dinamica

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

-- Fibonacci como ejemplo de programación dinámica. --

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

-- (fib n) es el n-ésimo término de la sucesión de Fibonacci, calculado

-- mediante programación dinámica. Por ejemplo,

-- fib 8 == 21

fib :: Int -> Int

fib n = valor t n

where t = dinamica calculaFib (cotasFib n)

-- (calculaFib t i) es el valor de i-ésimo término de la sucesión de

-- Fibonacci calculado mediante la tabla t que contiene los

-- anteriores. Por ejemplo,

-- calculaFib (tabla []) 0 == 0

-- calculaFib (tabla [(0,0)]) 1 == 1

-- calculaFib (tabla [(0,0),(1,1)]) 2 == 1

-- calculaFib (tabla [(0,0),(1,1),(2,1)]) 3 == 2

-- calculaFib (tabla [(0,0),(1,1),(2,1),(3,2)]) 4 == 3

-- calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3)]) 5 == 5

-- calculaFib (tabla [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5)]) 6 == 8

-- Además,

-- ghci> dinamica calculaFib (0,8)

-- Tbl [(0,0),(1,1),(2,1),(3,2),(4,3),(5,5),(6,8),(7,13),(8,21)]

calculaFib :: Tabla Int Int -> Int -> Int

calculaFib t i | i <= 1 = i

| otherwise = valor t (i-1) + valor t (i-2)

-- (cotasFib n) son las cotas del vector que se necesita para calcular

-- el n-ésimo término de la sucesión de Fibonacci mediante programación

-- dinámica.

cotasFib :: Int -> (Int,Int)

cotasFib n = (0,n)

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

-- Fibonacci mediante divide y vencerás --

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

-- (fibR n) es el n-ésimo término de la sucesión de Fibonacci calculado

-- mediante divide y vencerás. Por ejemplo,

-- fibR 8 == 21

fibR :: Int -> Int

fibR 0 = 0

fibR 1 = 1

fibR n = fibR (n-1) + fibR (n-2)

-- Comparación

-- ghci> fib 20

-- 6765

-- (0.01 secs, 524824 bytes)

-- ghci> fibR 20

-- 6765

-- (0.06 secs, 2165236 bytes)

-- ghci> fib 30

-- 832040

-- (0.01 secs, 0 bytes)

-- ghci> fibR 30

-- 832040

-- (6.46 secs, 222602404 bytes)

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

-- Fibonacci mediante programación dinámica con listas infinitas --

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

-- fibs es la lista de los términos de la sucesión de Fibonacci. Por

-- ejemplo,

-- take 10 fibs == [0,1,1,2,3,5,8,13,21,34]

fibs :: [Int]

fibs = 0:1:[x+y | (x,y) <- zip fibs (tail fibs)]

-- (fib' n) es el n-ésimo término de la sucesión de Fibonacci, calculado

-- a partir de fibs. Por ejemplo,

-- fib' 8 == 21

fib' :: Int -> Int

fib' n = fibs!!n

-- Comparaciones:

-- ghci> fib 30

-- 832040

-- (0.02 secs, 524808 bytes)

-- ghci> fib' 30

-- 832040

-- (0.01 secs, 542384 bytes)

El código del problema del producto de cadenas de matrices es

-- ---------------------------------------------------------------------
-- Descripción del problema                                           --
-- ---------------------------------------------------------------------

-- Para multiplicar una matriz de orden m*p y otra de orden p*n se
-- necesitan mnp multiplicaciones de elementos.

-- El problema del producto de una cadena de matrices (en inglés,
-- "matrix chain multiplication") consiste en dada una sucesión de
-- matrices encontrar la manera de multiplicarlas usando el menor número
-- de productos de elementos.   

-- Ejemplo: Dada la sucesión de matrices
--    A (30 x 1), B (1 x 40), C (40 x 10), D (10 x 25)
-- las productos necesarios en las posibles asociaciones son
--    ((AB)C)D  30 x  1 x 40 + 30 x 40 x 10 + 30 x 10 x 25 = 20700
--    A{B{CD))  40 x 10 x 25 +  1 x 40 x 25 + 30 x  1 x 25 = 11750
--    (AB)(CD)  30 x  1 x 40 + 40 x 10 x 25 + 30 x 40 x 25 = 41200
--    A((BC)D)   1 x 40 x 10 +  1 x 10 x 25 + 30 x  1 x 25 =  1400 
--    (A(BC))D  1  x 40 x 10 + 30 x  1 x 10 + 30 x 10 x 25 =  8200 

-- ---------------------------------------------------------------------
-- El algoritmo                                                       --
-- ---------------------------------------------------------------------

-- Sea ds=[d_0,...,d_n)] una sucesión de números naturales.

-- A_1,...,A_n es una cadena de matrices de tipo ds si para cada i, A_i es
-- una matriz de orden d_(i-1)xd_i.

-- c(i,j) es el mínimo número de multiplicaciones para multiplicar la
-- cadena Ai,...,Aj (1<=i<=j<=n).

-- Relación de recurrencia de c(i,j):
-- * c(i,i) = 0
-- * c(i,j) = min { c(i,k)+c(k+1,j)+d_(i-1)*d_k*d_j | i<=k<=j}

-- La solución del problema es c(1,n).

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import I1M.Dinamica

-- ---------------------------------------------------------------------
-- Solución mediante programación dinámica                            --
-- ---------------------------------------------------------------------

-- Cadena representa el producto de una cadena de matrices. Por ejemplo,
--    ghci> P (A 1) (P (A 2) (A 3))
--    (A1*(A2*A3))
--    ghci> P (P (A 1) (A 2)) (A 3)
--    ((A1*A2)*A3)
data Cadena = A Int 
            | P Cadena Cadena

instance Show Cadena where
    show (A x)     = "A" ++ show x
    show (P p1 p2) = concat ["(", show p1, "*", show p2, ")"]

-- Los índices de la matriz de cálculo son de la forma (i,j) y sus
-- valores (v,k) donde v es el mínimo número de multiplicaciones
-- necesarias para multiplicar la cadena Ai,...,Aj y k es la posición
-- donde dividir la cadena de forma óptima.
type IndicePCM = (Int,Int)
type ValorPCM  = (Int,Int)

-- (pcm ds) es la el par formado por el número de multiplicaciones
-- elementales de la cadena óptima para multiplicar las matrices A1, A2, ...
-- tales que sus dimensiones son (d1*d2), (d2*d3), ... donde [d1,d2,...]
-- es ds y la cadena. Por ejemplo,  
--    ghci> pcm [30,1,40,10,25]
--    (1400,(A1*((A2*A3)*A4)))
pcm :: [Int] -> (Int, Cadena)
pcm ds = (v, cadena t 1 n)
    where n     = length ds - 1
          t     = dinamica (calculaPCM ds) (cotasPCM n)
          (v,_) = valor t (1,n)

-- (calculaPCM ds t (i,j)) es el valor del índice (i,j) calculado a
-- partir de la lista ds de dimensiones de las matrices y la tabla t de
-- valores previamente calculados.
calculaPCM :: [Int] -> Tabla IndicePCM ValorPCM -> IndicePCM -> ValorPCM
calculaPCM ds t (i,j) 
    | i == j    = (0,i)
    | otherwise = minimum [(fst(valor t (i,k)) 
                            + fst(valor t (k+1,j)) 
                            + ds!!(i-1) * ds!!k * ds!!j, k) 
                           | k <- [i..j-1]]

-- (cotasPCM n) son las cotas de los índices para el producto de una
-- cadena de n matrices.
cotasPCM :: Int -> (IndicePCM,IndicePCM)
cotasPCM n = ((1,1),(n,n)) 

-- (cadena t i j) es la cadena que resultar de agrupar las matrices
-- Ai,...,Aj según los valores de la tabla t.
cadena :: Tabla IndicePCM ValorPCM -> Int -> Int -> Cadena
cadena t i j 
    | i == j-1  = P (A i) (A j)
    | k == i    = P (A i) (cadena t (i+1) j)
    | k == j-1  = P (cadena t i (j-1)) (A j)
    | otherwise = P (cadena t i (k-1)) (cadena t k j)
    where (_,k) = valor t (i,j)

-- (pcm' ds) es la lista de los índices y valores usados en el cálculo
-- de la cadena óptima para multiplicar las matrices A1, A2, ... tales
-- que sus dimensiones son (d1*d2), (d2*d3), ... donde [d1,d2,...] es
-- ds. Por ejemplo,   
--    ghci> pcm' [30,1,40,10,25]
--    [((1,1),(0,1)),((1,2),(1200,1)),((1,3),(700,1)),((1,4),(1400,1)),
--     ((2,2),(0,2)),((2,3),(400,2)),((2,4),(650,3)),
--     ((3,3),(0,3)),((3,4),(10000,3)),
--     ((4,4),(0,4))]
pcm' :: [Int] -> [((Int, Int), ValorPCM)]
pcm' ds = [((i,j),valor t (i,j)) | i <- [1..n], j <- [i..n]] 
    where n = length ds - 1
          t = dinamica (calculaPCM ds) (cotasPCM n)

-- ---------------------------------------------------------------------
-- Solución mediante divide y vencerás                                --
-- ---------------------------------------------------------------------

-- (pcmDyV ds) es la el par formado por el número de multiplicaciones
-- elementales de la cadena óptima para multiplicar las matrices 
-- A1, A2, ...tales que sus dimensiones son (d1*d2), (d2*d3), ... donde
-- [d1,d2,...] es ds y la cadena, calculada mediante divide y
-- vencerás. Por ejemplo,   
--    ghci> pcmDyV [30,1,40,10,25]
--    (1040,(A1*((A2*A3)*A4)))
pcmDyV :: [Int] -> (Int, Cadena)
pcmDyV ds = cadenaDyV ds 1 n
    where n = length ds - 1
         
-- (cadenaDyV ds i j) es el par formado por el número de
-- multiplicaciones elementales de la cadena óptima para multiplicar las
-- matrices  Ai, ..., Aj tales que sus dimensiones son 
-- (di*d_(i+1)), ... (d_(j-1)*dj), donde [d1,d2,...] es ds y la cadena,
-- calculada mediante divide y vencerás. Por ejemplo,   
--    cadenaDyV [30,1,40,10,25] 1 4  ==  (1040,(A1*((A2*A3)*A4)))
--    cadenaDyV [30,1,40,10,25] 2 4  ==  (290,((A2*A3)*A4))
-- cadenaDyV :: [Int] -> Int -> Int -> (Int, Cadena)
-- cadenaDyV ds i j 
cadenaDyV :: [Int] -> Int -> Int -> (Int, Cadena)
cadenaDyV ds i j 
    | i == j    = (0, A i)
    | i == j-1  = (ds!!(i-1)*ds!!i*ds!!j, P (A i) (A j))
    | k == i    = (v, P (A i) (subcadena (i+1) j))
    | k == j-1  = (v, P (subcadena i (j-1)) (A j))
    | otherwise = (v, P (subcadena i (k-1)) (subcadena k j))
    where (v,k) = minimum [((valor i k) 
                            + (valor (k+1) j) 
                            + ds!!(i-1) * ds!!k * ds!!j, k) 
                           | k <- [i..j-1]]
          valor p q     = fst (cadenaDyV ds p q)
          subcadena p q = snd (cadenaDyV ds p q)

-- ---------------------------------------------------------------------
-- Comparación de las soluciones                                      --
-- ---------------------------------------------------------------------

--    ghci> :set +s
--    ghci> fst (pcm [1..20])
--    2658
--    (0.04 secs, 4144552 bytes)
--    ghci> fst (pcmDyV [1..20])
--    2658
--    (1582.60 secs, 340414297896 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

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

-- Descripción del problema --

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

-- Para multiplicar una matriz de orden m*p y otra de orden p*n se

-- necesitan mnp multiplicaciones de elementos.

-- El problema del producto de una cadena de matrices (en inglés,

-- "matrix chain multiplication") consiste en dada una sucesión de

-- matrices encontrar la manera de multiplicarlas usando el menor número

-- de productos de elementos.

-- Ejemplo: Dada la sucesión de matrices

-- A (30 x 1), B (1 x 40), C (40 x 10), D (10 x 25)

-- las productos necesarios en las posibles asociaciones son

-- ((AB)C)D 30 x 1 x 40 + 30 x 40 x 10 + 30 x 10 x 25 = 20700

-- A{B{CD)) 40 x 10 x 25 + 1 x 40 x 25 + 30 x 1 x 25 = 11750

-- (AB)(CD) 30 x 1 x 40 + 40 x 10 x 25 + 30 x 40 x 25 = 41200

-- A((BC)D) 1 x 40 x 10 + 1 x 10 x 25 + 30 x 1 x 25 = 1400

-- (A(BC))D 1 x 40 x 10 + 30 x 1 x 10 + 30 x 10 x 25 = 8200

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

-- El algoritmo --

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

-- Sea ds=[d_0,...,d_n)] una sucesión de números naturales.

-- A_1,...,A_n es una cadena de matrices de tipo ds si para cada i, A_i es

-- una matriz de orden d_(i-1)xd_i.

-- c(i,j) es el mínimo número de multiplicaciones para multiplicar la

-- cadena Ai,...,Aj (1<=i<=j<=n).

-- Relación de recurrencia de c(i,j):

-- * c(i,i) = 0

-- * c(i,j) = min { c(i,k)+c(k+1,j)+d_(i-1)*d_k*d_j | i<=k<=j}

-- La solución del problema es c(1,n).

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

-- Importación de librerías auxiliares --

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

import I1M.Dinamica

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

-- Solución mediante programación dinámica --

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

-- Cadena representa el producto de una cadena de matrices. Por ejemplo,

-- ghci> P (A 1) (P (A 2) (A 3))

-- (A1*(A2*A3))

-- ghci> P (P (A 1) (A 2)) (A 3)

-- ((A1*A2)*A3)

data Cadena = A Int

| P Cadena Cadena

instance Show Cadena where

show (A x) = "A" ++ show x

show (P p1 p2) = concat ["(", show p1, "*", show p2, ")"]

-- Los índices de la matriz de cálculo son de la forma (i,j) y sus

-- valores (v,k) donde v es el mínimo número de multiplicaciones

-- necesarias para multiplicar la cadena Ai,...,Aj y k es la posición

-- donde dividir la cadena de forma óptima.

type IndicePCM = (Int,Int)

type ValorPCM = (Int,Int)

-- (pcm ds) es la el par formado por el número de multiplicaciones

-- elementales de la cadena óptima para multiplicar las matrices A1, A2, ...

-- tales que sus dimensiones son (d1*d2), (d2*d3), ... donde [d1,d2,...]

-- es ds y la cadena. Por ejemplo,

-- ghci> pcm [30,1,40,10,25]

-- (1400,(A1*((A2*A3)*A4)))

pcm :: [Int] -> (Int, Cadena)

pcm ds = (v, cadena t 1 n)

where n = length ds - 1

t = dinamica (calculaPCM ds) (cotasPCM n)

(v,_) = valor t (1,n)

-- (calculaPCM ds t (i,j)) es el valor del índice (i,j) calculado a

-- partir de la lista ds de dimensiones de las matrices y la tabla t de

-- valores previamente calculados.

calculaPCM :: [Int] -> Tabla IndicePCM ValorPCM -> IndicePCM -> ValorPCM

calculaPCM ds t (i,j)

| i == j = (0,i)

| otherwise = minimum [(fst(valor t (i,k))

+ fst(valor t (k+1,j))

+ ds!!(i-1) * ds!!k * ds!!j, k)

| k <- [i..j-1]]

-- (cotasPCM n) son las cotas de los índices para el producto de una

-- cadena de n matrices.

cotasPCM :: Int -> (IndicePCM,IndicePCM)

cotasPCM n = ((1,1),(n,n))

-- (cadena t i j) es la cadena que resultar de agrupar las matrices

-- Ai,...,Aj según los valores de la tabla t.

cadena :: Tabla IndicePCM ValorPCM -> Int -> Int -> Cadena

cadena t i j

| i == j-1 = P (A i) (A j)

| k == i = P (A i) (cadena t (i+1) j)

| k == j-1 = P (cadena t i (j-1)) (A j)

| otherwise = P (cadena t i (k-1)) (cadena t k j)

where (_,k) = valor t (i,j)

-- (pcm' ds) es la lista de los índices y valores usados en el cálculo

-- de la cadena óptima para multiplicar las matrices A1, A2, ... tales

-- que sus dimensiones son (d1*d2), (d2*d3), ... donde [d1,d2,...] es

-- ds. Por ejemplo,

-- ghci> pcm' [30,1,40,10,25]

-- [((1,1),(0,1)),((1,2),(1200,1)),((1,3),(700,1)),((1,4),(1400,1)),

-- ((2,2),(0,2)),((2,3),(400,2)),((2,4),(650,3)),

-- ((3,3),(0,3)),((3,4),(10000,3)),

-- ((4,4),(0,4))]

pcm' :: [Int] -> [((Int, Int), ValorPCM)]

pcm' ds = [((i,j),valor t (i,j)) | i <- [1..n], j <- [i..n]]

where n = length ds - 1

t = dinamica (calculaPCM ds) (cotasPCM n)

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

-- Solución mediante divide y vencerás --

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

-- (pcmDyV ds) es la el par formado por el número de multiplicaciones

-- elementales de la cadena óptima para multiplicar las matrices

-- A1, A2, ...tales que sus dimensiones son (d1*d2), (d2*d3), ... donde

-- [d1,d2,...] es ds y la cadena, calculada mediante divide y

-- vencerás. Por ejemplo,

-- ghci> pcmDyV [30,1,40,10,25]

-- (1040,(A1*((A2*A3)*A4)))

pcmDyV :: [Int] -> (Int, Cadena)

pcmDyV ds = cadenaDyV ds 1 n

where n = length ds - 1

-- (cadenaDyV ds i j) es el par formado por el número de

-- multiplicaciones elementales de la cadena óptima para multiplicar las

-- matrices Ai, ..., Aj tales que sus dimensiones son

-- (di*d_(i+1)), ... (d_(j-1)*dj), donde [d1,d2,...] es ds y la cadena,

-- calculada mediante divide y vencerás. Por ejemplo,

-- cadenaDyV [30,1,40,10,25] 1 4 == (1040,(A1*((A2*A3)*A4)))

-- cadenaDyV [30,1,40,10,25] 2 4 == (290,((A2*A3)*A4))

-- cadenaDyV :: [Int] -> Int -> Int -> (Int, Cadena)

-- cadenaDyV ds i j

cadenaDyV :: [Int] -> Int -> Int -> (Int, Cadena)

cadenaDyV ds i j

| i == j = (0, A i)

| i == j-1 = (ds!!(i-1)*ds!!i*ds!!j, P (A i) (A j))

| k == i = (v, P (A i) (subcadena (i+1) j))

| k == j-1 = (v, P (subcadena i (j-1)) (A j))

| otherwise = (v, P (subcadena i (k-1)) (subcadena k j))

where (v,k) = minimum [((valor i k)

+ (valor (k+1) j)

+ ds!!(i-1) * ds!!k * ds!!j, k)

| k <- [i..j-1]]

valor p q = fst (cadenaDyV ds p q)

subcadena p q = snd (cadenaDyV ds p q)

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

-- Comparación de las soluciones --

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

-- ghci> :set +s

-- ghci> fst (pcm [1..20])

-- 2658

-- (0.04 secs, 4144552 bytes)

-- ghci> fst (pcmDyV [1..20])

-- 2658

-- (1582.60 secs, 340414297896 bytes)

Se puede imprimir o compartir con