Questão 5: Um palíndromo é uma palavra ou uma frase que tenha a propriedade de poder ser lida tanto da direita para a esquerda como da esquerda para a direita com igual significado.
Em um palíndromo, normalmente são desconsiderados os sinais ortográficos (diacrítico ou de pontuação), assim como o espaços entre palavras. As seguintes frases são exemplos de palíndromo:
- Ande Edna
- Ame o poema
- Após a sopa
- Socorram-me, subi no ônibus em Marrocos
Escreva uma função recursiva em Haskell que receba uma String
e retorne True se
for palíndromo, e False caso contrário. Assuma que
é composta exclusivamente de caracteres alfabéticos ou espaço em branco. Note que na verificação dos palíndromos, caracteres maiúsculos e minúsculos devem ser considerados equivalentes. Você está desafiado(a) a fazer este exercício sem obter a String
de trás para frente. (Note que neste exercício, como nos anteriores, você não está impedido de criar funções auxiliares para executar a tarefa solicitada.) Exemplo:
palindromo “wendel”
False
palindromo “ande edna”
True
palindromo “ande EDNA”
True
palindromo “apos a sopa”
True
palindromo “wendel”
False
palindromo “ande edna”
True
palindromo “ande EDNA”
True
palindromo “apos a sopa”
True
False
palindromo “ande edna”
True
palindromo “ande EDNA”
True
palindromo “apos a sopa”
True
Passo 1
O enunciado pede uma função recursiva em Haskell que receba uma String s e devolva True se for palíndromo, False caso contrário. É conteúdo de recursão em listas, tratamento de caracteres e definição de funções auxiliares. Vamos precisar: normalizar a string (ignorar espaços e caixa) e depois testar recursivamente se ela é igual de frente pra trás, mas sem realmente inverter a string.
Passo 2
Primeiro, vamos normalizar a string para facilitar a verificação. Isso significa remover espaços e converter tudo para minúsculas. Podemos criar uma função auxiliar normalize que faz isso de forma recursiva:
Em Haskell, strings são listas de Char, então podemos definir:
normalize :: String -> String
normalize [] = []
normalize (c:cs)
| c == ’ ’ = normalize cs
| otherwise = toLower c : normalize cs
Aqui usamos pattern matching para separar cabeça e cauda, guardas para pular espaços e toLower (de Data.Char) para converter.
Em Haskell, strings são listas de Char, então podemos definir:
normalize :: String -> String
normalize [] = []
normalize (c:cs)
| c == ’ ’ = normalize cs
| otherwise = toLower c : normalize cs
Aqui usamos pattern matching para separar cabeça e cauda, guardas para pular espaços e toLower (de Data.Char) para converter.
Passo 3
Com a string normalizada, definimos outra função recursiva verifica que testa palíndromo em três passos:
- Se a lista for vazia ou tiver um só caractere, é palíndromo (retorna True).
- Caso contrário, comparamos o primeiro e o último caractere.
- Se forem iguais, chamamos verifica novamente na sublista que tira o primeiro e o último (usando tail e init).
Em código:
verifica :: String -> Bool
verifica [] = True
verifica [_] = True
verifica xs = head xs == last xs && verifica (init (tail xs))
Passo 4
Basta agora juntar tudo na função principal palindromo, que primeiro normaliza e depois chama verifica. Não usamos nenhuma inversão de lista inteira, só head, last, tail e init, obedecendo ao enunciado.
Resposta
import Data.Char (toLower)
palindromo :: String -> Bool
palindromo s = verifica (normalize s)
where
normalize :: String -> String
normalize [] = []
normalize (c:cs)
| c == ’ ’ = normalize cs
| otherwise = toLower c : normalize cs
palindromo s = verifica (normalize s)
where
normalize :: String -> String
normalize [] = []
normalize (c:cs)
| c == ’ ’ = normalize cs
| otherwise = toLower c : normalize cs
verifica :: String -> Bool
verifica [] = True
verifica [_] = True
verifica xs = head xs == last xs && verifica (init (tail xs))