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

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

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

Versão 1 (com função span, mas também podia ser usada recursividade com acumulador)

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 elemento a elemento, mas vírgula a vírgula.

Versão 2 (com fold)

stringToVector' :: String -> [Int]
stringToVector' = uncurry join . foldr (\c (acc_elem, acc_vec) ->
        case c of
            ',' -> ("", join acc_elem acc_vec)
            x -> (x : acc_elem, acc_vec)
    ) ("",[])
    where join = (:) . read

Aqui, percorremos a string elemento a elemento com dois acumuladores, um que armazena o número atual e outro que armazena todos os números. Passamos um elemento do primeiro para o segundo acumulador quando encontramos uma vírgula. No fim, pegamos apenas no segundo acumulador.

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.

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

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

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

myTranspose :: Mat -> Mat
myTranspose [] = []
myTranspose ([]:_) = []
myTranspose m = heads : myTranspose tails
    where (heads,tails) = unzip [ (h, t) | (h:t) <- 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”.

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

3.a) Defina a função semUltimo :: Lista a -> Lista a que recebe uma Lista não vazia e devolve a Lista sem o seu elemento mais à direita.

semUltimo :: Lista a -> Lista a
semUltimo (Esq a Nula) = Nula
semUltimo (Esq a l) = Esq a (semUltimo l)
semUltimo (Dir l a) = l

O último elemento de uma Lista é o primeiro elemento Dir, visto que mais nada pode estar à direita deste elemento. Caso a lista não tenha elementos Dir, então é o último elemento Esq.

3.b) Defina Lista como instância da classe Show de forma a que a lista Esq 1 (Dir (Dir (Esq 9 Nula) 3) 4) seja apresentada como [1, 9, 3, 4].

instance Show a => Show (Lista a) where
    show l = "[" ++ showAux l ++ "]"
        where
            showAux Nula = ""
            showAux (Esq a Nula) = show a
            showAux (Esq a l) = show a ++ "," ++ showAux l
            showAux (Dir Nula a) = show a
            showAux (Dir l a) = showAux l ++ "," ++ show a

A função showAux permite-nos colocar os parênteses retos apenas no início e no fim da lista. Temos ainda de ter em atenção os dois casos em que a Lista só tem um elemento, para não colocar vírgulas desnecessárias.

4) Relembre a definição do tipo das árvores binárias e da função que faz uma travessia inorder de uma árvore.

data BTree a = Empty | Node a (BTree a) (BTree a) deriving Show

inorder :: BTree a -> [a]
inorder Empty = []
inorder (Node r e d) = inorder e ++ (r:inorder d)

4.a) Defina uma função numera :: BTree a -> BTree (a,Int) que coloca em cada nodo da árvore argumento o número de ordem desse nodo numa travessia inorder. A função deve percorrer a árvore uma única vez.

Por exemplo, numera (Node ‘a’ (Node ‘b’ Empty Empty) (Node ‘c’ Empty Empty)) deve dar como resultado (Node (‘a’,2) (Node (‘b’,1) Empty Empty) (Node (‘c’,3) Empty Empty)).

Sugestão: Comece por definir uma função numeraAux :: Int -> Btree a -> (Int,BTree (a,Int)) que recebe um inteiro (o primeiro número a ser usado) e retorna a árvore numerada bem como o número de elementos dessa árvore.

numera :: BTree a -> BTree (a,Int)
numera = snd . numeraAux 0


numeraAux :: Int -> BTree a -> (Int,BTree (a,Int))
numeraAux _ Empty = (0, Empty)
numeraAux n (Node e l r) = (novo_n + n_dir, Node (e,novo_n) novo_l novo_r)
    where (n_esq, novo_l) = numeraAux n l
          novo_n = n_esq + n + 1
          (n_dir, novo_r) = numeraAux novo_n r

A função numeraAux começa por receber o valor 0, pois inicialmente ainda não foi percorrido nenhum elemento. Ao chegar a um elemento da árvore, começa por percorrer os elementos à sua esquerda, dando-nos as variáveis n_esq e novo_n, correspondentes ao número de elementos à esquerda e à nova árvore gerada à esquerda. Assim, sabemos que o número correspondente ao elemento que estamos a percorrer é igual ao número de elementos à sua esquerda mais o número de elementos que já viu em cima (inicialmente é 0, corresponde à variável n) mais 1 (pois começamos com 0). Por último, numeramos os elementos à direita, tendo como valor base o valor correspondente ao elemento atual, pois todos os elementos à direita serão percorridos depois e terão valores maiores. Depois de geradas as novas árvores à esquerda e à direita, podemos definir o novo Node. É importante colocar como primeiro elemento do par a soma de todos os elementos, incluíndo os elementos da direita, para o elemento de cima saber quantos elementos tem abaixo de si.

4.b) A função inorder não é injetiva: há muitas árvores diferentes que dão origem à mesma travessia: por exemplo, as árvores Node 1 Empty (Node 2 Empty Empty) e Node 2 (Node 1 Empty Empty) Empty têm como travessia a lista [1,2].

Defina a função unInorder :: [a] -> [BTree a] que, dada uma lista, calcula (a lista de) todas as árvores cuja travessia inorder corresponde a essa lista.

unInorder :: [a] -> [BTree a]
unInorder [] = [Empty]
unInorder xs = [Node x l r | (ls,x,rs) <- splits xs,
                             l <- unInorder ls,
                             r <- unInorder rs ]
    where 
        splits :: [a] -> [([a],a,[a])]
        splits xs = [ (take i xs, xs !! i, tail (drop i xs)) | i <- [0..length xs - 1]]

Esta função é bastante complexa, por isso é importante dividi-la em passos lógicos. Dada uma lista como [1,2,3], sabemos que uma árvore cuja travessia inorder corresponda a esta lista terá que ter um dos elementos da lista como raiz, os elementos à sua esquerda na esquerda e os elementos à sua direita na direita. Por exemplo, se a raiz for 2, à esquerda da raiz terá que estar o elemento 1 e à direita o elemento 3. Por outro lado, se a raiz for 3, já teremos os outros dois elementos à esquerda e nenhum à direita. Assim, começamos por definir uma função splits que, dada uma lista, gera todas as possíveis divisões da mesma, ou seja, todos os conjuntos de raiz + elementos à esquerda + elementos à direita.

Para a lista [1,2,3], o resultado esperado será [([],1,[2,3]), ([1],2,[3]), ([1,2],3,[])]. Agora, apenas precisamos de chamar esta função na nossa função principal e, para cada conjunto de 3 valores, gerar todas as árvores possíveis com o elemento central como raiz. A forma mais fácil de gerar todas estas combinações é com compreensão de listas. Temos ainda de ter o cuidado de chamar a função recursivamente para as listas da esquerda e da direita e de definir o caso de paragem como uma lista de um só elemento, em vez de uma lista vazia.