Haskell实现签名为[a] -> Bool的回文判断函数报错如何解决

报错原因 #

1. 逻辑错误 #

你在非空分支的比较逻辑写错了对象：当前代码是把去掉首元素的子列表xs和完整输入x:xs的反转结果对比，本身不符合回文的判断规则。回文的核心判断逻辑是整个输入列表和它的反转结果完全相等。

2. 类型错误（核心报错原因） #

相等比较运算符==的类型为Eq a => a -> a -> Bool，要求被比较的元素必须实现Eq类型类才支持相等判断。你当前给出的palindrome :: [a] -> Bool签名没有对类型参数a加Eq a约束，编译器无法确认任意类型的元素都支持相等比较，因此会抛出类型不匹配的编译错误。

解决方案 #

标准安全实现（带Eq约束） #

这是符合Haskell类型安全要求的常规实现，仅签名多了必要的Eq a约束：

rev :: [a] -> [a]
rev [] = []
rev (x:xs) = rev xs ++ [x]

palindrome :: Eq a => [a] -> Bool
palindrome xs = xs == rev xs

如果需要用递归拆分的写法，逻辑如下：

palindrome :: Eq a => [a] -> Bool
palindrome [] = True
palindrome [_] = True
palindrome (x:xs) = x == last xs && palindrome (init xs)

强制无约束签名实现 #

如果你必须严格使用[a] -> Bool的签名，需要开启编译器扩展给所有类型提供默认的Eq实例，该方案会丢失类型安全，遇到不支持判等的类型时会在运行时报错：

{-# LANGUAGE FlexibleInstances, UndecidableInstances, OverlappingInstances #-}

rev :: [a] -> [a]
rev [] = []
rev (x:xs) = rev xs ++ [x]

instance {-# OVERLAPS #-} Eq a where
  (==) = error "该类型不支持相等比较，无法判断回文"

palindrome :: [a] -> Bool
palindrome xs = xs == rev xs

内容的提问来源于stack exchange，提问作者Art Red