Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
A continuación se muestran las soluciones.
1. Mayor producto de las ramas de un árbol
Los árboles se pueden representar mediante el siguiente tipo de datos
data Arbol a = N a [ Arbol a ]
deriving Show
Por ejemplo, los árboles
1 3
/ \ / | \
2 3 / | \
| 5 4 7
4 | / \
6 2 1
se representan por
ej1 , ej2 :: Arbol Int
ej1 = N 1 [ N 2 [ ] , N 3 [ N 4 [ ] ] ]
ej2 = N 3 [ N 5 [ N 6 [ ] ] , N 4 [ ] , N 7 [ N 2 [ ] , N 1 [ ] ] ]
Definir la función
mayorProducto :: ( Ord a , Num a ) = > Arbol a -> a
tal que (mayorProducto a) es el mayor producto de las ramas del árbol a. Por ejemplo,
λ> mayorProducto ( N 1 [ N 2 [ ] , N 3 [ ] ] )
3
λ> mayorProducto ( N 1 [ N 8 [ ] , N 4 [ N 3 [ ] ] ] )
12
λ> mayorProducto ( N 1 [ N 2 [ ] , N 3 [ N 4 [ ] ] ] )
12
λ> mayorProducto ( N 3 [ N 5 [ N 6 [ ] ] , N 4 [ ] , N 7 [ N 2 [ ] , N 1 [ ] ] ] )
90
λ> mayorProducto ( N ( - 8 ) [ N 0 [ N ( - 9 ) [ ] ] , N 6 [ ] ] )
0
λ> a = N ( - 4 ) [ N ( - 7 ) [ ] , N 14 [ N 19 [ ] ] , N ( - 1 ) [ N ( - 6 ) [ ] , N 21 [ ] ] , N ( - 4 ) [ ] ]
λ> mayorProducto a
84
Soluciones
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
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
import Test.QuickCheck
data Arbol a = N a [ Arbol a ]
deriving Show
-- 1ª solución
-- ===========
mayorProducto1 :: ( Ord a , Num a ) = > Arbol a -> a
mayorProducto1 a = maximum [ product xs | xs < - ramas a ]
-- (ramas a) es la lista de las ramas del árbol a. Por ejemplo,
-- λ> ramas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
-- [[3,5,6],[3,4],[3,7,2],[3,7,1]]
ramas :: Arbol b -> [ [ b ] ]
ramas ( N x [ ] ) = [ [ x ] ]
ramas ( N x as ) = [ x : xs | a < - as , xs < - ramas a ]
-- 2ª solución
-- ===========
mayorProducto2 :: ( Ord a , Num a ) = > Arbol a -> a
mayorProducto2 a = maximum ( map product ( ramas a ) )
-- 3ª solución
-- ===========
mayorProducto3 :: ( Ord a , Num a ) = > Arbol a -> a
mayorProducto3 = maximum . map product . ramas
-- 4º solución
-- ===========
mayorProducto4 :: ( Ord a , Num a ) = > Arbol a -> a
mayorProducto4 = maximum . productosRamas
-- (productosRamas a) es la lista de los productos de las ramas
-- del árbol a. Por ejemplo,
-- λ> productosRamas (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
-- [90,12,42,21]
productosRamas :: ( Ord a , Num a ) = > Arbol a -> [ a ]
productosRamas ( N x [ ] ) = [ x ]
productosRamas ( N x xs ) = [ x * y | a < - xs , y < - productosRamas a ]
-- 5ª solución
-- ===========
mayorProducto5 :: ( Ord a , Num a ) = > Arbol a -> a
mayorProducto5 ( N x [ ] ) = x
mayorProducto5 ( N x xs )
| x > 0 = x * maximum ( map mayorProducto5 xs )
| x == 0 = 0
| otherwise = x * minimum ( map menorProducto xs )
-- (menorProducto a) es el menor producto de las ramas del árbol
-- a. Por ejemplo,
-- λ> menorProducto (N 1 [N 2 [], N 3 []])
-- 2
-- λ> menorProducto (N 1 [N 8 [], N 4 [N 3 []]])
-- 8
-- λ> menorProducto (N 1 [N 2 [],N 3 [N 4 []]])
-- 2
-- λ> menorProducto (N 3 [N 5 [N 6 []], N 4 [], N 7 [N 2 [], N 1 []]])
-- 12
menorProducto :: ( Ord a , Num a ) = > Arbol a -> a
menorProducto ( N x [ ] ) = x
menorProducto ( N x xs )
| x > 0 = x * minimum ( map menorProducto xs )
| x == 0 = 0
| otherwise = x * maximum ( map mayorProducto2 xs )
-- 6ª solución
-- ===========
mayorProducto6 :: ( Ord a , Num a ) = > Arbol a -> a
mayorProducto6 = maximum . aux
where aux ( N a [ ] ) = [ a ]
aux ( N a b ) = [ v , u ]
where u = maximum g
v = minimum g
g = map ( * a ) ( concatMap aux b )
-- Comprobación de equivalencia
-- ============================
-- (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo,
-- > sample (arbolArbitrario 5 :: Gen (Arbol Int))
-- N 0 [N 0 []]
-- N (-2) []
-- N 4 []
-- N 2 [N 4 []]
-- N 8 []
-- N (-2) [N (-9) [],N 7 []]
-- N 11 []
-- N (-11) [N 4 [],N 14 []]
-- N 10 [N (-3) [],N 13 []]
-- N 12 [N 11 []]
-- N 20 [N (-18) [],N (-13) []]
arbolArbitrario :: Arbitrary a = > Int -> Gen ( Arbol a )
arbolArbitrario n = do
x < - arbitrary
ms < - sublistOf [ 0 . . n ` div ` 2 ]
as < - mapM arbolArbitrario ms
return ( N x as )
-- Arbol es una subclase de Arbitraria
instance Arbitrary a = > Arbitrary ( Arbol a ) where
arbitrary = sized arbolArbitrario
-- La propiedad es
prop_mayorProducto :: Arbol Integer -> Bool
prop_mayorProducto a =
all ( == mayorProducto1 a )
[ f a | f < - [ mayorProducto2
, mayorProducto3
, mayorProducto4
, mayorProducto5
, mayorProducto6
] ]
-- La comprobación es
-- λ> quickCheck prop_mayorProducto
-- +++ OK, passed 100 tests.
-- Comparación de eficiencia
-- =========================
-- La comparación es
-- λ> ejArbol <- generate (arbolArbitrario 600 :: Gen (Arbol Integer))
-- λ> mayorProducto1 ejArbol
-- 2419727651266241493467136000
-- (1.87 secs, 1,082,764,480 bytes)
-- λ> mayorProducto2 ejArbol
-- 2419727651266241493467136000
-- (1.57 secs, 1,023,144,008 bytes)
-- λ> mayorProducto3 ejArbol
-- 2419727651266241493467136000
-- (1.55 secs, 1,023,144,248 bytes)
-- λ> mayorProducto4 ejArbol
-- 2419727651266241493467136000
-- (1.60 secs, 824,473,800 bytes)
-- λ> mayorProducto5 ejArbol
-- 2419727651266241493467136000
-- (0.83 secs, 732,370,352 bytes)
-- λ> mayorProducto6 ejArbol
-- 2419727651266241493467136000
-- (0.98 secs, 817,473,344 bytes)
--
-- λ> ejArbol2 <- generate (arbolArbitrario 700 :: Gen (Arbol Integer))
-- λ> mayorProducto5 ejArbol2
-- 1044758937398026715504640000000
-- (4.94 secs, 4,170,324,376 bytes)
-- λ> mayorProducto6 ejArbol2
-- 1044758937398026715504640000000
-- (5.88 secs, 4,744,782,024 bytes)
El código se encuentra en GitHub .
La elaboración de las soluciones se describe en el siguiente vídeo
VIDEO
2. Diferencia simétrica
La diferencia simétrica de dos conjuntos es el conjunto cuyos elementos son aquellos que pertenecen a alguno de los conjuntos iniciales, sin pertenecer a ambos a la vez. Por ejemplo, la diferencia simétrica de {2,5,3} y {4,2,3,7} es {5,4,7}.
Definir la función
diferenciaSimetrica :: Ord a = > [ a ] -> [ a ] -> [ a ]
tal que (diferenciaSimetrica xs ys) es la diferencia simétrica de xs e ys. Por ejemplo,
diferenciaSimetrica [ 2 , 5 , 3 ] [ 4 , 2 , 3 , 7 ] == [ 4 , 5 , 7 ]
diferenciaSimetrica [ 2 , 5 , 3 ] [ 5 , 2 , 3 ] == [ ]
diferenciaSimetrica [ 2 , 5 , 2 ] [ 4 , 2 , 3 , 7 ] == [ 3 , 4 , 5 , 7 ]
diferenciaSimetrica [ 2 , 5 , 2 ] [ 4 , 2 , 4 , 7 ] == [ 4 , 5 , 7 ]
diferenciaSimetrica [ 2 , 5 , 2 , 4 ] [ 4 , 2 , 4 , 7 ] == [ 5 , 7 ]
Soluciones
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import Test.QuickCheck
import Data.List ( ( \ \ ) , intersect , nub , sort , union )
import qualified Data . Set as S
-- 1ª solución
-- ===========
diferenciaSimetrica1 :: Ord a = > [ a ] -> [ a ] -> [ a ]
diferenciaSimetrica1 xs ys =
sort ( nub ( [ x | x < - xs , x ` notElem ` ys ] ++ [ y | y < - ys , y ` notElem ` xs ] ) )
-- 2ª solución
-- ===========
diferenciaSimetrica2 :: Ord a = > [ a ] -> [ a ] -> [ a ]
diferenciaSimetrica2 xs ys =
sort ( nub ( filter ( ` notElem ` ys ) xs ++ filter ( ` notElem ` xs ) ys ) )
-- 3ª solución
-- ===========
diferenciaSimetrica3 :: Ord a = > [ a ] -> [ a ] -> [ a ]
diferenciaSimetrica3 xs ys =
sort ( nub ( union xs ys \ \ intersect xs ys ) )
-- 4ª solución
-- ===========
diferenciaSimetrica4 :: Ord a = > [ a ] -> [ a ] -> [ a ]
diferenciaSimetrica4 xs ys =
[ x | x < - sort ( nub ( xs ++ ys ) )
, x ` notElem ` xs || x ` notElem ` ys ]
-- 5ª solución
-- ===========
diferenciaSimetrica5 :: Ord a = > [ a ] -> [ a ] -> [ a ]
diferenciaSimetrica5 xs ys =
S . elems ( ( xs ' `S.union` ys' ) ` S . difference ` ( xs ' `S.intersection` ys' ) )
where xs ' = S.fromList xs
ys' = S . fromList ys
-- Comprobación de equivalencia
-- ============================
-- La propiedad es
prop_diferenciaSimetrica :: [ Int ] -> [ Int ] -> Bool
prop_diferenciaSimetrica xs ys =
all ( == diferenciaSimetrica1 xs ys )
[ diferenciaSimetrica2 xs ys ,
diferenciaSimetrica3 xs ys ,
diferenciaSimetrica4 xs ys ,
diferenciaSimetrica5 xs ys ]
-- La comprobación es
-- λ> quickCheck prop_diferenciaSimetrica
-- +++ OK, passed 100 tests.
-- Comparación de eficiencia
-- =========================
-- La comparación es
-- λ> length (diferenciaSimetrica1 [1..2*10^4] [2,4..2*10^4])
-- 10000
-- (2.34 secs, 10,014,360 bytes)
-- λ> length (diferenciaSimetrica2 [1..2*10^4] [2,4..2*10^4])
-- 10000
-- (2.41 secs, 8,174,264 bytes)
-- λ> length (diferenciaSimetrica3 [1..2*10^4] [2,4..2*10^4])
-- 10000
-- (5.84 secs, 10,232,006,288 bytes)
-- λ> length (diferenciaSimetrica4 [1..2*10^4] [2,4..2*10^4])
-- 10000
-- (5.83 secs, 14,814,184 bytes)
-- λ> length (diferenciaSimetrica5 [1..2*10^4] [2,4..2*10^4])
-- 10000
-- (0.02 secs, 7,253,496 bytes)
El código se encuentra en GitHub .
La elaboración de las soluciones se describe en el siguiente vídeo
VIDEO
3. Conjunto de primos relativos
Dos números enteros positivos son primos relativos si no tienen ningún factor primo en común; es decit, si 1 es su único divisor común. Por ejemplo, 6 y 35 son primos entre sí, pero 6 y 27 no lo son porque ambos son divisibles por 3.
Definir la función
primosRelativos :: [ Int ] -> Bool
tal que (primosRelativos xs) se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,
primosRelativos [ 6 , 35 ] == True
primosRelativos [ 6 , 27 ] == False
primosRelativos [ 2 , 3 , 4 ] == False
primosRelativos [ 6 , 35 , 11 ] == True
primosRelativos [ 6 , 35 , 11 , 221 ] == True
primosRelativos [ 6 , 35 , 11 , 231 ] == False
Soluciones
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
import Test.QuickCheck
import Data.List ( delete , intersect )
import Data.Numbers.Primes ( primeFactors , primes )
import qualified Data . Set as S ( disjoint , fromList )
-- 1ª solución
-- ===========
primosRelativos1 :: [ Int ] -> Bool
primosRelativos1 [ ] = True
primosRelativos1 ( x : xs ) =
and [ sonPrimosRelativos1 x y | y < - xs ] && primosRelativos1 xs
-- (sonPrimosRelativos x y) se verifica si x e y son primos
-- relativos. Por ejemplo,
-- sonPrimosRelativos1 6 35 == True
-- sonPrimosRelativos1 6 27 == False
sonPrimosRelativos1 :: Int -> Int -> Bool
sonPrimosRelativos1 x y =
null ( divisoresPrimos x ` intersect ` divisoresPrimos y )
-- (divisoresPrimos x) es la lista de los divisores primos de x. Por
-- ejemplo,
-- divisoresPrimos 600 == [2,2,2,3,5,5]
divisoresPrimos :: Int -> [ Int ]
divisoresPrimos 1 = [ ]
divisoresPrimos x =
y : divisoresPrimos ( x ` div ` y )
where y = menorDivisorPrimo x
-- (menorDivisorPrimo x) es el menor divisor primo de x. Por ejemplo,
-- menorDivisorPrimo 15 == 3
-- menorDivisorPrimo 11 == 11
menorDivisorPrimo :: Int -> Int
menorDivisorPrimo x =
head [ y | y < - [ 2.. ] , x ` mod ` y == 0 ]
-- 2ª solución
-- ===========
primosRelativos2 :: [ Int ] -> Bool
primosRelativos2 [ ] = True
primosRelativos2 ( x : xs ) =
all ( sonPrimosRelativos1 x ) xs && primosRelativos2 xs
-- 3ª solución
-- ===========
primosRelativos3 :: [ Int ] -> Bool
primosRelativos3 [ ] = True
primosRelativos3 ( x : xs ) =
all ( sonPrimosRelativos2 x ) xs && primosRelativos3 xs
sonPrimosRelativos2 :: Int -> Int -> Bool
sonPrimosRelativos2 x y =
null ( primeFactors x ` intersect ` primeFactors y )
-- 4ª solución
-- ===========
primosRelativos4 :: [ Int ] -> Bool
primosRelativos4 [ ] = True
primosRelativos4 ( x : xs ) =
all ( sonPrimosRelativos3 x ) xs && primosRelativos4 xs
sonPrimosRelativos3 :: Int -> Int -> Bool
sonPrimosRelativos3 x y =
S . fromList ( primeFactors x ) ` S . disjoint ` S . fromList ( primeFactors y )
-- 5ª solución
-- ===========
primosRelativos5 :: [ Int ] -> Bool
primosRelativos5 [ ] = True
primosRelativos5 ( x : xs ) =
all ( sonPrimosRelativos5 x ) xs && primosRelativos5 xs
sonPrimosRelativos5 :: Int -> Int -> Bool
sonPrimosRelativos5 x y =
gcd x y == 1
-- Comprobación de equivalencia
-- ============================
-- La propiedad es
prop_primosRelativos :: [ Positive Int ] -> Bool
prop_primosRelativos xs =
all ( == primosRelativos1 ys )
[ primosRelativos2 ys ,
primosRelativos3 ys ,
primosRelativos4 ys ,
primosRelativos5 ys ]
where ys = getPositive < $ > xs
-- La comprobación es
-- λ> quickCheck prop_primosRelativos
-- +++ OK, passed 100 tests.
-- Comparación de eficiencia
-- =========================
-- La comparación es
-- λ> primosRelativos1 (take 120 primes)
-- True
-- (1.92 secs, 869,909,416 bytes)
-- λ> primosRelativos2 (take 120 primes)
-- True
-- (1.99 secs, 869,045,656 bytes)
-- λ> primosRelativos3 (take 120 primes)
-- True
-- (0.09 secs, 221,183,200 bytes)
--
-- λ> primosRelativos3 (take 600 primes)
-- True
-- (2.62 secs, 11,196,690,856 bytes)
-- λ> primosRelativos4 (take 600 primes)
-- True
-- (2.66 secs, 11,190,940,456 bytes)
-- λ> primosRelativos5 (take 600 primes)
-- True
-- (0.14 secs, 123,673,648 bytes)
El código se encuentra en GitHub .
La elaboración de las soluciones se describe en el siguiente vídeo
VIDEO
4. Familias de números con algún dígito en común
Una familia de números es una lista de números tal que todos tienen la misma cantidad de dígitos y, además, dichos números tienen al menos un dígito común.
Por ejemplo, los números 72, 32, 25 y 22 pertenecen a la misma familia ya que son números de dos dígitos y todos tienen el dígito 2, mientras que los números 123, 245 y 568 no pertenecen a la misma familia, ya que no hay un dígito que aparezca en los tres números.
Definir la función
esFamilia :: [ Integer ] -> Bool
tal que (esFamilia ns) se verifica si ns es una familia de números. Por ejemplo,
esFamilia [ 72 , 32 , 25 , 22 ] == True
esFamilia [ 123 , 245 , 568 ] == False
esFamilia [ 72 , 32 , 25 , 223 ] == False
esFamilia [ 56 ] == True
esFamilia [ ] == True
Soluciones
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
import Data.List ( intersect , nub )
import Test.QuickCheck ( quickCheck )
-- 1ª solución
-- ===========
esFamilia1 :: [ Integer ] -> Bool
esFamilia1 [ ] = True
esFamilia1 ns =
igualNumeroElementos dss && tieneElementoComun dss
where dss = map show ns
-- (igualNumeroElementos xss) se verifica si todas las listas de xss
-- tienen el mismo número de elementos. Por ejemplo,
-- igualNumeroElementos [[1,3],[2,2],[4,9]] == True
-- igualNumeroElementos [[1,3],[2,1,2],[4,9]] == False
igualNumeroElementos :: [ [ a ] ] -> Bool
igualNumeroElementos xss =
iguales ( map length xss )
-- (iguales xs) se verifica si todos los elementos de xs son
-- iguales. Por ejemplo,
-- iguales [3,3,3,3] == True
-- iguales [3,3,7,3] == False
iguales :: Eq a = > [ a ] -> Bool
iguales [ ] = True
iguales ( x : xs ) = all ( == x ) xs
-- (tieneElementoComun xss) se verifican si todas las listas de xss
-- tienen algún elemento común. Por ejemplo,
-- tieneElementoComun [[1,2],[2,3],[4,2,7]] == True
-- tieneElementoComun [[1,2],[2,3],[4,3,7]] == False
tieneElementoComun :: Eq a = > [ [ a ] ] -> Bool
tieneElementoComun [ ] = False
tieneElementoComun ( xs : xss ) = any ( ` esElementoComun ` xss ) xs
-- (esElementoComun x yss) se verifica si x pertenece a todos los
-- elementos de yss. Por ejemplo,
-- esElementoComun 2 [[1,2],[2,3],[4,2,7]] == True
-- esElementoComun 2 [[1,2],[2,3],[4,3,7]] == False
esElementoComun :: Eq a = > a -> [ [ a ] ] -> Bool
esElementoComun x = all ( x ` elem ` )
-- 2ª solución
-- ===========
esFamilia2 :: [ Integer ] -> Bool
esFamilia2 [ ] = True
esFamilia2 ns =
igualNumeroElementos2 dss && tieneElementoComun2 dss
where dss = map show ns
igualNumeroElementos2 :: [ [ a ] ] -> Bool
igualNumeroElementos2 xss =
length ( nub ( map length xss ) ) == 1
tieneElementoComun2 :: Eq a = > [ [ a ] ] -> Bool
tieneElementoComun2 xss =
not ( null ( foldl1 intersect xss ) )
-- 3ª solución
-- ===========
esFamilia3 :: [ Integer ] -> Bool
esFamilia3 [ ] = True
esFamilia3 ns =
igualNumeroElementos3 dss && tieneElementoComun3 dss
where dss = map show ns
igualNumeroElementos3 :: [ [ a ] ] -> Bool
igualNumeroElementos3 = ( ( == 1 ) . length ) . nub . map length
tieneElementoComun3 :: Eq a = > [ [ a ] ] -> Bool
tieneElementoComun3 = ( not . null ) . foldl1 intersect
-- Comprobación de equivalencia
-- ============================
-- La propiedad es
prop_esFamilia :: [ Integer ] -> Bool
prop_esFamilia xss =
all ( == esFamilia1 xss )
[ esFamilia2 xss ,
esFamilia3 xss ]
-- La comprobación es
-- λ> quickCheck prop_esFamilia
-- +++ OK, passed 100 tests.
-- Comparación de eficiencia
-- =========================
-- La comparación es
-- λ> esFamilia1 [10^6..4*10^6]
-- False
-- (1.85 secs, 1,931,162,984 bytes)
-- λ> esFamilia2 [10^6..4*10^6]
-- False
-- (2.31 secs, 2,288,177,752 bytes)
-- λ> esFamilia3 [10^6..4*10^6]
-- False
-- (2.23 secs, 2,288,177,864 bytes)
El código se encuentra en GitHub .
La elaboración de las soluciones se describe en el siguiente vídeo
VIDEO
5. Biparticiones de una lista
Definir la función
biparticiones :: [ a ] -> [ ( [ a ] , [ a ] ) ]
tal que (biparticiones xs) es la lista de pares formados por un prefijo de xs y el resto de xs. Por ejemplo,
λ> biparticiones [ 3 , 2 , 5 ]
[ ( [ ] , [ 3 , 2 , 5 ] ) , ( [ 3 ] , [ 2 , 5 ] ) , ( [ 3 , 2 ] , [ 5 ] ) , ( [ 3 , 2 , 5 ] , [ ] ) ]
λ> biparticiones "Roma"
[ ( "" , "Roma" ) , ( "R" , "oma" ) , ( "Ro" , "ma" ) , ( "Rom" , "a" ) , ( "Roma" , "" ) ]
Soluciones
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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import Data.List ( inits , tails )
import Control.Applicative ( liftA2 )
import Test.QuickCheck ( quickCheck )
-- 1ª solución
-- ===========
biparticiones1 :: [ a ] -> [ ( [ a ] , [ a ] ) ]
biparticiones1 [ ] = [ ( [ ] , [ ] ) ]
biparticiones1 ( x : xs ) =
( [ ] , ( x : xs ) ) : [ ( x : ys , zs ) | ( ys , zs ) < - biparticiones1 xs ]
-- 2ª solución
-- ===========
biparticiones2 :: [ a ] -> [ ( [ a ] , [ a ] ) ]
biparticiones2 xs =
[ ( take i xs , drop i xs ) | i < - [ 0..length xs ] ]
-- 3ª solución
-- ===========
biparticiones3 :: [ a ] -> [ ( [ a ] , [ a ] ) ]
biparticiones3 xs =
[ splitAt i xs | i < - [ 0..length xs ] ]
-- 4ª solución
-- ===========
biparticiones4 :: [ a ] -> [ ( [ a ] , [ a ] ) ]
biparticiones4 xs =
zip ( inits xs ) ( tails xs )
-- 5ª solución
-- ===========
biparticiones5 :: [ a ] -> [ ( [ a ] , [ a ] ) ]
biparticiones5 = liftA2 zip inits tails
-- 6ª solución
-- ===========
biparticiones6 :: [ a ] -> [ ( [ a ] , [ a ] ) ]
biparticiones6 = zip < $ > inits < * > tails
-- Comprobación de equivalencia
-- ============================
-- La propiedad es
prop_biparticiones :: [ Int ] -> Bool
prop_biparticiones xs =
all ( == biparticiones1 xs )
[ biparticiones2 xs ,
biparticiones3 xs ,
biparticiones4 xs ,
biparticiones5 xs ,
biparticiones6 xs ]
-- La comprobación es
-- λ> quickCheck prop_biparticiones
-- +++ OK, passed 100 tests.
-- Comparación de eficiencia
-- =========================
-- La comparación es
-- λ> length (biparticiones1 [1..6*10^3])
-- 6001
-- (2.21 secs, 3,556,073,552 bytes)
-- λ> length (biparticiones2 [1..6*10^3])
-- 6001
-- (0.01 secs, 2,508,448 bytes)
--
-- λ> length (biparticiones2 [1..6*10^6])
-- 6000001
-- (2.26 secs, 2,016,494,864 bytes)
-- λ> length (biparticiones3 [1..6*10^6])
-- 6000001
-- (2.12 secs, 1,584,494,792 bytes)
-- λ> length (biparticiones4 [1..6*10^6])
-- 6000001
-- (0.78 secs, 1,968,494,704 bytes)
-- λ> length (biparticiones5 [1..6*10^6])
-- 6000001
-- (0.79 secs, 1,968,494,688 bytes)
-- λ> length (biparticiones6 [1..6*10^6])
-- 6000001
-- (0.77 secs, 1,968,494,720 bytes)
--
-- λ> length (biparticiones4 [1..10^7])
-- 10000001
-- (1.30 secs, 3,280,495,432 bytes)
-- λ> length (biparticiones5 [1..10^7])
-- 10000001
-- (1.42 secs, 3,280,495,416 bytes)
-- λ> length (biparticiones6 [1..10^7])
-- 10000001
-- (1.30 secs, 3,280,495,448 bytes)
El código se encuentra en GitHub .
La elaboración de las soluciones se describe en el siguiente vídeo
VIDEO
Se puede imprimir o compartir con