Reloj Cuántico

binarias = iterate (concatMap (\xs -> ['0':xs,'1':xs])) [""]

El n-ésimo término de la lista infinita ‘binarias’ es una lista que contiene las cadenas binarias de longitud n; por ejemplo,

> binarias !! 4
["0000","1000","0100","1100","0010","1010","0110","1110",
 "0001","1001","0101","1101","0011","1011","0111","1111"]

Se construyen con la regla de que cada lista en ‘binarias’ es igual a la anterior después de poner un ’0′ y un ’1′ al principio de cada cadena en la lista, iniciando con la lista que contiene a la cadena vacía.

‘concatMap’ es similar a ‘map’, pero permite agregar varios valores al resultado en lugar de sólo uno:

> map (\ k -> k+10) [1..5]
[11,12,13,14,15]
> concatMap (\ k -> [k, k+10]) [1..5]
[1,11,2,12,3,13,4,14,5,15]

Para cada número en [1..5] ‘map’ solamente extiende la lista resultado en uno; ‘concatMap’ aquí la extiende en dos, porque (\ k -> [k, k+10]) regresa una lista con dos elementos.

Manipular la función de extensión permite generar cadenas binarias con propiedades particulares. Por ejemplo, las cadenas binarias que no tienen dos unos juntos:

sinRachas = [""] :
    iterate (concatMap 
        (\xs -> if head xs == '1' 
                  then ['0':xs] 
                  else ['0':xs,'1':xs])) ["0","1"]

Aunque se ve más complicada, es casi exactamente la misma función. La única diferencia es que, en lugar de simplemente agregar un ’0′ y un ’1′, primero pregunta si la cadena a la que está agregando empieza con ’1′ (head xs == ’1′); si es así, extiende solamente con ’0′.

Como está preguntando por el principio de la cadena binaria, no es posible comenzar a iterar con una cadena vacía. Por eso ‘[""] :’ agrega directamente las cadenas binarias sin dos unos juntos que tienen longitud cero (solamente “”) y comienza a iterar con las de longitud uno, ["0","1"].

Como nota interesante, los números de cadenas binarias sin dos unos juntos corresponden a números de Fibonacci:

> map length sinRachas 
[1,2,3,5,8,13,21,34,55,89,144,233,377...