Проблема начинающего в Haskell - не удалось сопоставить тип 'Bool' с '[Char]' - PullRequest
Новая
       67

Проблема начинающего в Haskell - не удалось сопоставить тип 'Bool' с '[Char]'

3 голосов
/ 05 октября 2019

Мне нужно сделать проверку палиндрома, используя рекурсию в Haskell для домашнего задания. Функция должна взять строку и вернуть Bool. Когда я пытаюсь скомпилировать, я получаю сообщение об ошибке: "Couldn't match type ‘Bool’ with ‘[Char]’."

Я новичок в Haskell, так что я уверен, что просто упускаю из виду что-то глупое, но я решил обратиться за помощьютак или иначе. Я вставил свой код ниже, а также полную ошибку, которую я получаю. 

isPalindrome :: String -> Bool
isPalindrome s
  | isPalindrome ((null s) || (length s == 1)) = True
  | isPalindrome ((s !! 0) /= (s !! (length s - 1))) = False
  | otherwise = isPalindrome (tail (init s))

Моя реализация проверяет, является ли входная строка пустой или имеет размер один, и возвращает true, если онаявляется. Если это не так, он проверяет, отличаются ли первый и последний символы, и, если они есть, возвращает false. В противном случае он вызывает себя снова, передавая строку с обрезанными первым и последним символами. 

main.hs:15:19: error:
    • Couldn't match type ‘Bool’ with ‘[Char]’
      Expected type: String
        Actual type: Bool
    • In the first argument of ‘isPalindrome’, namely
        ‘((null s) || (length s == 1))’
      In the expression: isPalindrome ((null s) || (length s == 1))
      In a stmt of a pattern guard for
                     an equation for ‘isPalindrome’:
        isPalindrome ((null s) || (length s == 1))
   |
15 |   | isPalindrome ((null s) || (length s == 1)) = True
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^
main.hs:16:19: error:
    • Couldn't match type ‘Bool’ with ‘[Char]’
      Expected type: String
        Actual type: Bool
    • In the first argument of ‘isPalindrome’, namely
        ‘((s !! 0) /= (s !! (length s - 1)))’
      In the expression: isPalindrome ((s !! 0) /= (s !! (length s - 1)))
      In a stmt of a pattern guard for
                     an equation for ‘isPalindrome’:
        isPalindrome ((s !! 0) /= (s !! (length s - 1)))
   |
16 |   | isPalindrome ((s !! 0) /= (s !! (length s - 1))) = False
   |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

1 Ответ

5 голосов
/ 05 октября 2019

f x - это вызов функции f с аргументом x. Но вам не нужно вызывать эту функцию, если тестовое выражение x уже все, что вам нужно: 

isPalindrome :: String -> Bool
isPalindrome s
  --   f               x
  | {- isPalindrome -} ((null s) || (length s == 1))        -- here
              = True
  | {- isPalindrome -} ((s !! 0) /= (s !! (length s - 1)))  -- and here
              = False
  | otherwise = isPalindrome (tail (init s))

isPalindrome :: String -> Bool означает, что первый аргумент isPalindrom, как ожидается, будетString. Но на самом деле подразумевается логическое значение, используемое в качестве защиты, для выбора подходящего курса действий. Отсюда и сообщение об ошибке. У нас уже есть это Bool.

Вызов функции в последней строке - это рекурсивный вызов, который действительно должен быть выполнен.

{- ... -} - это многострочные комментарии в Haskell.

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

isPalindrome :: String -> Bool
isPalindrome []     = True           -- (null s)
isPalindrome [_]    = True           -- (length s == 1)
isPalindrome -- [a, ..., b] | a /= b
             (x:xs) | x /= last xs
                    = False          --  ((s !! 0) /= (s !! (length s - 1))) 
isPalindrome -- [a, ...xs, b] 
             (_:xs) = isPalindrome   --  xs
                                   (init xs)

Приведенный выше код содержит некоторыемнимые шаблоны списков в комментариях и их эквиваленты в Haskell в самом коде.

На самом деле, как указывает @ chepner в комментариях, шаблоны часто помогают избежать неэффективности: вычисление length равно O (n) , тогда как сопоставление с шаблономс [_] равно O (1) .

Конечно, этот конкретный код все еще очень неэффективен, так как два других пункта также выполняют операции O (n) (last и init). Существует алгоритм O (n) .

...