import Ratio

-- función lineal; x --> (a,b) = ax + b

type FL = (Ratio Integer, Ratio Integer)

-- Composición
-- x --> (a, b) · (c, d) = c(ax + b) + d = (acx) + (bc + d)
-- (a, b) · (c, d) = (ac, bc + d)

(·) :: FL -> FL -> FL
(a,b) · (c,d) = (a*c, b*c + d)

-- Potencia. FIXME
(··) :: FL -> Integer -> FL
f ·· 1 = f
f ·· n = f · (f ·· (n-1))

phi :: FL
ji :: FL

-- sube; completo (10)
phi = (3,1)·ji

-- sube; unitario (1)
psi = (3,1)

-- baja (0)
ji = (1%2,0)

-- "True" es "sube", "False" es "baja". Convierte num. binario en FL
convierte :: [Bool] -> FL
convierte [] = (0,0)
convierte xs = foldl1 (·) $ map (\k -> if k then psi else ji) xs

-- a binario/FL desde cadena
b :: String -> [FL]
b [] = []
b (x:xs) = siguiente:(b xs) where siguiente = if x == '0' then ji else psi

aplica :: FL -> Ratio Integer -> Ratio Integer
aplica (a,b) x = a*x + b

r :: String -> Ratio Integer -> Ratio Integer
r xs n = (aplica $ foldl1 (·) $ b xs) n