Проверка палиндрома, которая игнорирует не алфавитно-цифровые символы и регистр Haskell

Question

Необходимо создать программу, которая проверяет, является ли данная строка палиндромом, должна ли она работать независимо от регистра, и должна игнорировать не алфавитно-цифровые символы, только используя функции ord и chr в Data.char и обычные функции,ничего больше.Мне удалось создать обычную проверку палиндрома:

reverseStr::String->String
reverStr s | s == [] = []
reverseStr (h:t) = reverseStr t ++ [h]

isPalindrome :: String -> Bool
isPalindrome s = s == reverseStr s

Я начал работу над функцией нормализации регистра:

normalizeCase::String->String
normalizeCase h | h == [] = []
normalizeCase (h) = if ord h > 64 && ord h < 123
    then map (chr $ (ord h + 32)) [h]
    else h

Но я получаю следующие ошибки:

• Couldn't match expected type ‘Char -> Char’
              with actual type ‘Char’
• In the first argument of ‘map’, namely ‘(chr $ (ord h + 32))’
  In the expression: map (chr $ (ord h + 32)) [h]
  In the expression:
    if ord h > 64 && ord h < 123 then
        map (chr $ (ord h + 32)) [h]
    else
        h

  |
6 |   then map (chr $ (ord h + 32)) [h]   |             ^^^^^^^^^^^^^^^^^^


    • Couldn't match type ‘Char’ with ‘[Char]’
  Expected type: String
    Actual type: Char
• In the expression: h
  In the expression:
    if ord h > 64 && ord h < 123 then
        map (chr $ (ord h + 32)) [h]
    else
        h
  In an equation for ‘normalizeCase’:
      normalizeCase [h]
        = if ord h > 64 && ord h < 123 then
              map (chr $ (ord h + 32)) [h]
          else
              h
  |
7 |   else h   |        ^

Я все еще очень плохо знаком с Haskell и не знаю, как правильно реализовать ord или chr, чтобы он работал с этим средством проверки, поэтому любая помощь будет принята!

Answer 1

В этом коде:

normalizeCase::String->String
normalizeCase h | h == [] = []
normalizeCase (h) = if ord h > 64 && ord h < 123
    then map (chr $ (ord h + 32)) [h]
    else h

Ваш второй шаблон (h) (эквивалентный просто h) соответствует любому списку (если он еще не сопоставлен спервый шаблон, h | h == []);поэтому h здесь список, и ord h не имеет смысла, поскольку ord ожидает Char, а не [Char].

Предполагая, что h был символом, тогда chr $ ord h + 32 также будет символом, но map ожидает функцию в качестве первого аргумента;это источник ошибки, которую ожидали Char -> Char, но вы дали Char.Для второго аргумента map вы передаете [h], который представляет собой список одного элемента h (который в вашем коде также является списком, поэтому вы предоставляете [[Char]], когда хотите [Char]).

Также при условии, что h был символом, ваше условие ord h > 64 && ord h < 123 соответствует любому символу между заглавными буквами A и строчными буквами z, включая несколькосимволы, которые вам не нужны ([]^_`).Тот факт, что h является списком символов, является источником ошибки, которую ожидалось Char, но вы дали [Char].

Вы также, кажется, смешиваете рекурсивный стильс map - в этом случае вы должны либо использовать map или определять функцию по кейсам.

Вот как ваш код может выглядеть с исправленными этими ошибками,Во-первых, используя рекурсию:

normalizeCase :: String -> String

-- Given an empty list, return an empty list.
-- This happens if the original input was empty,
-- or when we reach the end of the recursion.
normalizeCase [] = []

-- Given a non-empty list,
-- test the first character ‘c’.
normalizeCase (c : cs) = if c >= 'A' && c <= 'Z'

  -- If it’s uppercase, lowercase it and
  -- prepend it to the result of normalizing
  -- the remainder of the string ‘cs’.
  then chr (ord c + 32) : normalizeCase cs

  -- Otherwise, don’t change it, but still
  -- prepend it to the result of normalizing
  -- the remainder of the string ‘cs’.
  else c : normalizeCase cs

Или, используя map:

normalizeCase :: String -> String

-- Given any string:
normalizeCase s

  -- For each character:
  = map

    -- If it’s uppercase, lowercase it.
    (\ c -> if c >= 'A' && c <= 'Z'
      then chr (ord c + 32)
      else c)

    -- Over the whole string.
    s

Char, можно сравнивать напрямую (c >= 'A'), что более читабельно, но есливы также должны использовать ord для сравнения, это будет ord c >= 65.

Я знаю, что вы не должны использовать какие-либо другие стандартные функции для этой задачи, но для дальнейшего использования,это также может быть реализовано очень просто, используя toLower из Data.Char:

import Data.Char (toLower)

normalizeCase :: String -> String
normalizeCase s = map toLower s

-- Alternatively, a point-free/eta-reduced version:
normalizeCase = map toLower

Для дополнительной задачи удаления не алфавитно-цифровых символов, вы можете использовать filter, представление списка с условием защитыили напишите прямую рекурсивную версию самостоятельно.