-- import Lista2Q1b: minha solução do exercício que exibe naturais de forma "bonita"
data Natural = Zero | Suc Natural
  deriving (Show, Eq)

-- exemplos de uso de foldr

meufoldr :: (a -> b -> b) -> b -> [a] -> b
meufoldr _ base []     = base
meufoldr f base (x:xs) = f x (meufoldr f base xs)

meusum :: (Foldable t, Num a) => t a -> a
meusum = foldr (+) 0

meulength :: (Foldable t) => t a -> Integer
meulength = foldr (\elemento contagem -> contagem+1) 0

hashilength :: (Foldable t) => t a -> Integer
hashilength = foldr (const (+1)) 0

constroi :: Integer -> Natural
constroi 0 = Zero
constroi n = Suc $ constroi (n-1)

soma :: Natural -> Natural-> Natural
soma n Zero    = n
soma n (Suc m) = Suc (soma n m)

produto :: Natural -> Natural-> Natural
produto _ Zero    = Zero
produto n (Suc m) = soma n (produto n m)

potência :: Natural -> Natural-> Natural
potência _ Zero    = Suc Zero
potência n (Suc m) = produto n (potência n m)

unifoldnat :: (a -> a) -> a -> Natural -> a
unifoldnat _ base Zero    = base
unifoldnat f base (Suc n) = f (unifoldnat f base n)

grito :: Char -> Natural -> String
grito c = unifoldnat (c:) ""

somaFold :: Natural -> Natural -> Natural
somaFold n m = unifoldnat Suc n m

produtoFold :: Natural -> Natural -> Natural
produtoFold n = unifoldnat (somaFold n) Zero

potênciaFold :: Natural -> Natural -> Natural
potênciaFold n = unifoldnat (produtoFold n) (Suc Zero)

torreFold :: Natural -> Natural -> Natural
torreFold n = unifoldnat (potênciaFold n) (Suc Zero)

-- Rufino: fast-growing hierarchy fgh
fgh :: Integer -> Natural -> Natural -> Natural
-- fgh 0 = const Suc
fgh 0 n m = somaFold n m
fgh 1 n m = produtoFold n m
fgh i n m = unifoldnat (fgh (i-1) n) (Suc Zero) m

-- fgh i n Zero    = Suc Zero
-- fgh i n (Suc m) = (fgh (i-1) n) (fgh i n m)

-- ideia do Hashi
fghnat :: Natural -> Natural -> Natural -> Natural
fghnat Zero n    = somaFold n
fghnat (Suc i) n = unifoldnat (\f -> unifoldnat f (Suc Zero)) (produtoFold n) i

zero = constroi 0
um   = constroi 1
dois = constroi 2
tres = constroi 3