1votos

Contador Binario (Backtracking básico) en Haskell

por josejuan hace 5 años

Exactamente la misma versión anterior pero detalladamente explicada (como no se pueden editar las soluciones ni borrar una vez con comentarios, duplico la solución).

Utilizando backtracking crear un contador binario de n dígitos.

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
-- Dejemos, de momento, fijo el número de bits (ej. 3). 
 
-- Usando la mónada de listas, el backtracking puede establecerse como 
 
    do 
            a <- [0,1] 
            b <- [0,1] 
            c <- [0,1] 
            return [a,b,c] 
 
-- El backtracking puede "verse" eliminando la notación "do", pues quedaría 
 
    [0,1] >>= 
        \a -> [0,1] >>= 
            \b -> [0,1] >>= \c -> 
                return [a,b,c] 
 
-- En que se ve el anidamiento de las tres funciones (*aún* no recursivas pero 
-- sí en backtracking) de los tres niveles de "recursión".  
 
-- Si "depuramos" y seguimos la traza de dicho código, vemos que 
     
    a = 0 
        b = 0 
            c = 0 
            c = 1 
        b = 1 
            c = 0 
            c = 1 
    a = 1 
        b = 0 
            c = 0 
            c = 1 
        b = 1 
            c = 0 
            c = 1 
 
-- Que es precisamente el árbol backtracking solicitado. 
 
-- En donde se ve (creo que cláramente) que la misma función (aunque escrita 
-- a mano 3 veces) es "arrastrar el valor en la recursión" (que son los parámetros 
-- "a", "b" y "c" en el ejemplo). 
 
-- La función en cuestión es 
 
    acumularBit = do 
                        bit <- [0, 1] 
                        return bit 
 
-- Ahora bien, como no sólo lo queremos hacer 3 veces sino "n" veces, debemos 
-- hacer que la función se llame recursivamente "n" veces (y no sólo 3 como antes). 
 
-- Para ello, creamos otra mónada que acumule para cada i=1,2,3..., n los elementos 
-- de la recursión, es decir, para i=1 nos creará la función con parámetro "a", para 
-- i=2 aquella con parámetro "b", para i=3 el parámetro "c" y sucesivos. 
 
-- Es decir, mapeamos a cada bit i-ésimo la función `acumularBit` dentro de otra mónada 
 
    mapM (\_ -> acumularBit) [1..n] 
 
-- Ésto, hace que `acumularBit` se llame recursivamente "n" veces (el resultado de una llamada 
-- superior es pasada a otra inferior por la acción monádica). 
 
-- Lo que obtenemos es 
     
    [0,1] >>= 
        \a -> [0,1] >>= 
            \b -> [0,1] >>= \c -> 
                ... 
                ... 
                ... 
                \r -> [0,1] >>= \s -> 
                    \s -> [0,1] >>= \t -> 
                        return [a,b,c, ..., r, s, t] -- <<< aquí los "n" bits 
 
-- Pero resulta, que el índice "i" del nivel en el que estamos no se usa en la recursión, sólo 
-- los bits "arrastrados", es por eso, que en el mapeo 
 
    mapM (\_ -> acumularBit) [1..n] 
 
-- se ignore el argumento y no se use, que es equivalente a escribir 
 
    mapM (const acumularBit) [1..n] 
 
-- Pero resulta, que si nos fijamos en la función `acumularBit`, ésta es 
 
    do 
        bit <- [0, 1] 
        return bit 
 
-- que sin notación "do" es 
     
    [0, 1] >>= return 
 
-- ¡pero esa es la identidad!, quedando 
     
    [0, 1] 
 
-- con lo cual, nuestra función con "n" niveles de recursión queda finalmente 
     
    mapM (const [0, 1]) [1..n] 
 
-- como habíamos escrito. 
1 comentario
0votos

Escrito por ilopez hace 5 años

Bien explicado ;). Con la traza queda claro que hace backtracking. Con Haskell se simplifica mucho las cosas.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.