Pergunta 1

Apresente uma definição recursiva da função unlines :: [String] -> String} que junta todas as strings da lista numa só, separando-as pelo caracter '\\n'. Por exemplo, unlines ["Prog", "Func"] == "Prog\\nFunc".

<aside> 📝 Resolução:

unlines :: [String] -> String
unlines [] = ""
unlines [x] = x
unlines (h:t) = h ++ "\\n" ++ unlines t

</aside>

Pergunta 2

O formato csv (comma separated values) serve para descrever tabelas de uma forma textual: cada linha da tabela corresponde a uma linha do texto, enquanto que os elementos de cada linha se encontram separados por vírgulas. Por exemplo, a string "2,3,6,4\\n12,3,12,4\\n3,-4,5,7" pode ser usada para descrever a matriz:

|  2  3  6  4 |
| 12  3 12  4 |
|  3 -4  5  7 |

Alínea a)

Considere o tipo type Mat = [[Int]] para representar matrizes e a seguinte definição da função stringToMat que converte strings desse formato em matrizes:

stringToMat :: String -> Mat
stringToMat = map stringToVector . lines

Apresente a definição da função stringToVector e indique explicitamente o seu tipo.

<aside> ⚠️ Visto que a função lines divide a string original em linhas, a função stringToVector vai receber uma linha da matriz em formato textual e tem de a converter numa linha numérica. Como no tipo Mat uma linha é uma lista de inteiros (a matriz em si é uma lista de linhas), o tipo da função stringToVector tem de ser stringToVector :: String -> [Int]. Também poderia ser definido o tipo type Vector = [Int] e a função ficaria assim com o tipo stringToVector :: String -> Vector.

</aside>

<aside> 📝 Versão 1 (com função span)

stringToVector :: String -> [Int]
stringToVector "" = []
stringToVector s =
    case span (/= ',') s of
        (a,"") -> [read a]
        (a,b) -> read a : stringToVector (tail b)

Aqui, a string é percorrida, não caracter a caracter, mas vírgula a vírgula. É importante pegar apenas na cauda de b para remover a vírgula.

NOTA: span f l == (takeWhile f l, dropWhile f l)

</aside>

<aside> 📝 Versão 2 (com fold, mas também poderia ser usada recursividade com uma função auxiliar)

stringToVector' :: String -> [Int]
stringToVector' = map read . foldr (\\c (h_acc:t_acc) ->
        case c of
            ',' -> "" : h_acc : t_acc
            x -> (x : h_acc) : t_acc
    ) [""]

Aqui, percorremos a string e vamos colocando os caracteres no primeiro elemento da lista acumuladora. Quando encontramos uma vírgula, criamos um novo elemento no início do acumulador. No fim, aplicamos a função read com um map para converter estes elementos em números.

</aside>

<aside> 📝 Versão 3 (a mais simples, mas com um pequeno “truque”)

stringToVector'' :: String -> [Int]
stringToVector'' s = read ("[" ++ s ++ "]")

Aqui, aproveitamos o facto da função read conseguir converter uma string diretamente para uma lista de inteiros, desde que a string tenha parênteses retos.

</aside>

Alínea b)

Defina a função transposta :: String -> String que recebe a tabela em formato textual e devolve a tabela transposta também em formato textual.

<aside> 📝 Resolução:

transposta :: String -> String
transposta = unlines . map (intercalate "," . map show) . transpose . stringToMat

Aqui é essencial decompôr o problema em partes. Se considerarmos estes 3 passos:

1. Converter a string numa matriz.
2. Calcular a transposta da matriz.
3. Converter a matriz numa string.

Vemos que o primeiro passo corresponde à primeira alínea do exercício e o segundo passo é um exercício que aparece nas fichas 2 e 5. Assim, a única coisa “nova” nesta alínea é converter a matriz numa string, mas que também se torna fácil se considerarmos que apenas temos de fazer o inverso do que foi feito na alínea a), ou seja, converter os números em strings (com a função show), colocar uma vírgula entre estas strings (com a função intercalate ","), formando assim as linhas da matriz, e por fim juntar estas strings usando a função unlines do exercício 1.

NOTA: As funções transpose e intercalate já se encontram definidas no módulo Data.List. Contudo, também podiam ser manualmente definidas de forma trivial, por exemplo:

myTranspose :: Mat -> Mat
myTranspose [] = []
myTranspose ([]:_) = []
myTranspose m = map head m : myTranspose $ map tail m

myIntercalate :: String -> [String] -> String
myIntercalate _ [] = ""
myIntercalate _ [x] = x
myIntercalate delim (h:t) = h ++ delim ++ myIntercalate delim t

A função myIntercalate é exatamente igual à função unlines do exercício 1, mas com um separador diferente de “\n”.

</aside>

Pergunta 3

Considere o seguinte tipo de dados para representar uma lista em que os elementos podem ser acrescentados à esquerda (Esq) ou à direita (Dir) da lista. Nula representa a lista vazia.

data Lista a = Esq a (Lista a) | Dir (Lista a) a | Nula