1) Defina a função digitAlpha :: String -> (String,String) que, dada uma string, devolve um par de strings: uma apenas com as letras presentes nessa string, e a outra apenas com os números presentes na string. Implemente a função de modo a fazer uma única travessia da string. Relembre que as funções isDigit, isAlpha :: Char -> Bool estão já definidas no módulo Data.Char.

digitAlpha :: String -> (String,String)
digitAlpha "" = ("","")
digitAlpha (h:t)
    | isAlpha h = (  digits, h:letters)
    | isDigit h = (h:digits,   letters)
    | otherwise = (  digits,   letters)
    where (digits, letters) = digitAlpha t

2) Defina a função nzp :: [Int] -> (Int,Int,Int) que, dada uma lista de inteiros, conta o número de valores negativos, o número de zeros e o número de valores positivos, devolvendo um triplo com essa informação. Certifique-se que a função que definiu percorre a lista apenas uma vez.

nzp :: [Int] -> (Int,Int,Int)
nzp [] = (0,0,0)
nzp (h:t)
    | h < 0 = (n + 1, z, p)
    | h == 0 = (n, z + 1, p)
    | otherwise = (n, z, p + 1)
    where (n, z, p) = nzp t

3) Defina a função divMod :: Integral a => a -> a -> (a, a) que calcula simultaneamente a divisão e o resto da divisão inteira por subtrações sucessivas.

divMod :: Integral a => a -> a -> (a, a)
divMod x y
    | x - y < 0 = (0,x)
    | otherwise = (q+1,r)
    where (q,r) = divMod (x - y) y

-- a versão acima funciona apenas para números positivos
-- a versão abaixo funciona para quaisquer valores inteiros

divMod' :: Integral a => a -> a -> (a, a)
divMod' x y 
    | x < 0 = let (q,r) = divMod' (-x) y in (if r == 0 then (-q,r) else (-q-1,-r+y))
    | y < 0 = let (q,r) = divMod' (-x) (-y) in (q,-r)
    | otherwise = if x - y < 0 then (0,x) else (let (q,r) = divMod' (x - y) y in (q+1,r))

4) Utilizando uma função auxiliar com um acumulador, otimize a seguinte definição recursiva que determina qual o número que corresponde a uma lista de digitos.

fromDigits :: [Int] -> Int
fromDigits [] = 0
fromDigits (h:t) = h*10^(length t) + fromDigits t

Note que

    fromDigits [1,2,3,4] = 1 * 10^3 + 2 * 10^2 + 3 * 10^1 + 4 * 10^0 
                         = 4 + 10 (3 + 10 (2 + 10 (1 + 10 * 0)))

fromDigits :: [Int] -> Int
fromDigits l = fromDigitsAux l 0

fromDigitsAux :: [Int] -> Int -> Int
fromDigitsAux [] acc = acc
fromDigitsAux (h:t) acc = fromDigitsAux t (h + 10 * acc)

5) Utilizando uma função auxiliar com acumuladores, otimize a seguinte definição que determina a soma do segmento inicial de uma lista com soma máxima.

maxSumInit :: (Num a, Ord a) => [a] -> a
maxSumInit l = maximum [sum m | m <- inits l]

maxSumInit :: (Num a, Ord a) => [a] -> a
maxSumInit l = maxSumInitAux l (sum l)

maxSumInitAux :: (Num a, Ord a) => [a] -> a -> a
maxSumInitAux [] acc = acc
maxSumInitAux l acc = if si > acc then maxSumInitAux il si else maxSumInitAux il acc
    where il = init l
          si = sum il

6) Otimize a seguinte definição recursiva da função que calcula o n-ésimo número da sequência de Fibonacci, usando uma função auxiliar com 2 acumuladores que representam, respectivamente, o n-ésimo e o n+1-ésimo números dessa sequência.

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fibAux (n-2) 0 1

fibAux :: Int -> Int -> Int -> Int
fibAux 0 n _ = n
fibAux i fib_n fib_n_mais_1 = fibAux (i - 1) fib_n_plus_1 (fib_n + fib_n_plus_1)

7) Defina a função intToStr :: Integer -> String que converte um inteiro numa string. Utilize uma função auxiliar com um acumulador onde vai construindo a string que vai devolver no final.

intToStr :: Integer -> String
intToStr 0 = "zero"
intToStr n = intToStrAux n ""

intToStrAux :: Integer -> String -> String
intToStrAux 0 ('-':acc) = acc
intToStrAux n acc = intToStrAux nn ((case r of 
        0 -> "-zero"
        1 -> "-um"
        2 -> "-dois"
        3 -> "-três"
        4 -> "-quatro"
        5 -> "-cinco"
        6 -> "-seis"
        7 -> "-sete"
        8 -> "-oito"
        9 -> "-nove") ++ acc)
    where (nn,r) = n `divMod` 10

8) Para cada uma das expressões seguintes, exprima por enumeração a lista correspondente. Tente ainda, para cada caso, descobrir uma outra forma de obter o mesmo resultado.

a) [x | x <- [1..20], mod x 2 == 0, mod x 3 == 0]

[6,12,18]

[x | x <- [1..20], mod x 6 == 0]

b) [x | x <- [y | y <- [1..20], mod y 2 == 0], mod x 3 == 0]

[6,12,18]

[x | x <- [1..20], mod x 6 == 0]

c) [(x,y) | x <- [0..20], y <- [0..20], x+y == 30]

[(10,20),(11,19),(12,18),(13,17),(14,16),(15,15),(16,14),(17,13),(18,12),(19,11),(20,10)]

[(x, 30 - x) | x <- [10..20]]

d) [sum [y | y <- [1..x], odd y] | x <- [1..10]]

[1,1,4,4,9,9,16,16,25,25]

[ x^2 | x <- [1..5], y <- [1..2]]

9) Defina cada uma das listas seguintes por compreensão.

a) [1,2,4,8,16,32,64,128,256,512,1024]

[ 2^x | x <- [0..10]]

b) [(1,5),(2,4),(3,3),(4,2),(5,1)]

[(x,y) | x <- [1..5], y <- [1..5], x + y == 6]

c) [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5]]

[[1..x] | x <- [1..5]]

d) [[1],[1,1],[1,1,1],[1,1,1,1],[1,1,1,1,1]]

[ replicate x 1 | x <- [1..5]]

e) [1,2,6,24,120,720]

[ product [y | y <- [1..x]] | x <- [1..6]]