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 s e retorne True se s for palíndromo, e False caso contrário. Assuma que s é 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 s 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

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.

Passo 3

Com a string normalizada, definimos outra função recursiva verifica que testa palíndromo em três passos:
  1. Se a lista for vazia ou tiver um só caractere, é palíndromo (retorna True).
  2. Caso contrário, comparamos o primeiro e o último caractere.
  3. 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
verifica :: String -> Bool
verifica []  = True
verifica [_] = True
verifica xs  = head xs == last xs && verifica (init (tail xs))

Exercícios relacionados