Serie de Thue-Morse

José A. Alonso

25-01-2016

La serie de Thue-Morse comienza con el término [0] y sus siguientes términos se construyen añadiéndole al anterior su complementario. Los primeros términos de la serie son

[0]
[0,1]
[0,1,1,0]
[0,1,1,0,1,0,0,1]
[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]

Definir la lista

serieThueMorse :: [[Integer]]

tal que sus elementos son los términos de la serie de Thue-Morse. Por ejemplo,

λ> take 4 serieThueMorse
[[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]

Comprobar con QuickCheck que cada término de la serie de Thue-Morse se obtiene del anterior sustituyendo los 1 por 1, 0 y los 0 por 0, 1.

Soluciones

import Test.QuickCheck

-- 1ª definición
serieThueMorse1 :: [[Integer]]
serieThueMorse1 = map termSerieThueMorse [0..]

-- (termSerieThueMorse n) es el término n-ésimo de la serie de
-- Thue-Morse. Por ejemplo,
--    termSerieThueMorse 1  ==  [0,1]
--    termSerieThueMorse 2  ==  [0,1,1,0]
--    termSerieThueMorse 3  ==  [0,1,1,0,1,0,0,1]
--    termSerieThueMorse 4  ==  [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0]
-- ---------------------------------------------------------------------

termSerieThueMorse :: Integer -> [Integer]
termSerieThueMorse 0 = [0]
termSerieThueMorse n = xs ++ complementaria xs
    where xs = termSerieThueMorse (n-1)

-- (complementaria xs) es la complementaria de la lista xs (formada por
-- ceros y unos); es decir, la lista obtenida cambiando el 0 por 1 y el
-- 1 por 0. Por ejemplo,
--    complementaria [1,0,0,1,1,0,1]  ==  [0,1,1,0,0,1,0]
complementaria :: [Integer] -> [Integer]
complementaria = map (1-)

-- 2ª definición
-- =============

serieThueMorse2 :: [[Integer]]
serieThueMorse2 = [0] : map paso serieThueMorse2
    where paso xs = xs ++ complementaria xs

-- 3ª definición
-- =============

serieThueMorse3 :: [[Integer]]
serieThueMorse3 = iterate paso [0]
    where paso xs = xs ++ complementaria xs

-- Propiedad
-- =========

-- La propiedad es
prop_sustitucion :: Integer -> Property
prop_sustitucion n =
    n >= 0 ==>
    termSerieThueMorse (n+1) == concatMap paso (termSerieThueMorse n)
    where paso x = [x,1-x]

-- Su comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=7}) prop_sustitucion
--    +++ OK, passed 100 tests.

-- 4ª definición (basada en la propiedad anterior)
-- ===============================================

serieThueMorse4 :: [[Integer]]
serieThueMorse4 = [0] : map (concatMap paso) serieThueMorse4
    where paso x = [x,1-x]