La serie de Thue-Morse
Publicado el 9 de enero de 2024 por José A. Alonso

serieThueMorse :: [[Int]]

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

module La_serie_de_Thue_Morse where

import Test.QuickCheck (NonNegative (NonNegative), quickCheckWith, maxSize, stdArgs)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)

-- 1ª solución
-- ===========

serieThueMorse1 :: [[Int]]
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 :: Int -> [Int]
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 :: [Int] -> [Int]
complementaria = map (1-)

-- 2ª solución
-- ===========

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

-- 3ª solución
-- ===========

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

-- 4ª solución
-- ===========

-- Observando 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.

serieThueMorse4 :: [[Int]]
serieThueMorse4 = [0] : map (concatMap paso4) serieThueMorse4
  where paso4 x = [x,1-x]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: [[Int]] -> Spec
specG serieThueMorse = do
  it "e1" $
    take 4 serieThueMorse `shouldBe`
    [[0],[0,1],[0,1,1,0],[0,1,1,0,1,0,0,1]]


spec :: Spec
spec = do
  describe "def. 1" $ specG serieThueMorse1
  describe "def. 2" $ specG serieThueMorse2
  describe "def. 3" $ specG serieThueMorse3
  describe "def. 4" $ specG serieThueMorse4

-- La verificación es
--    λ> verifica
--
--    4 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_serieThueMorse :: NonNegative Int -> Bool
prop_serieThueMorse  (NonNegative n) =
  all (== serieThueMorse1 !! n)
      [serieThueMorse2 !! n,
       serieThueMorse3 !! n,
       serieThueMorse4 !! n]

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=20}) prop_serieThueMorse
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> (serieThueMorse1 !! 23) !! (2^22)
--    1
--    (1.08 secs, 839,419,224 bytes)
--    λ> (serieThueMorse2 !! 23) !! (2^22)
--    1
--    (0.61 secs, 839,413,592 bytes)
--    λ> (serieThueMorse3 !! 23) !! (2^22)
--    1
--    (1.43 secs, 839,413,592 bytes)
--    λ> (serieThueMorse4 !! 23) !! (2^22)
--    1
--    (1.57 secs, 1,007,190,024 bytes)

from itertools import count, islice
from typing import Iterator

# Solución
# ========

# 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]
def complementaria(xs: list[int]) -> list[int]:
    return [1 - x for x in xs]

# 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]
def termSerieThueMorse(n: int) -> list[int]:
    if n == 0:
        return [0]
    xs = termSerieThueMorse(n-1)
    return xs + complementaria(xs)

def serieThueMorse() -> Iterator[list[int]]:
    return (termSerieThueMorse(n) for n in count())

# Verificación
# ============

def test_serieThueMorse() -> None:
    assert list(islice(serieThueMorse(), 4)) == \
        [[0], [0, 1], [0, 1, 1, 0], [0, 1, 1, 0, 1, 0, 0, 1]]
    print("Verificado")

# La verificación es
#    >>> test_serieThueMorse()
#    Verificado