haskell - 检查列表是否为回文的数学函数

Question

我今天一直在尝试 Haskell，并编写了一个函数来检查整数列表是否是回文。我认为应该可以编写与数学函数相同的函数。这是我的代码:

isPalindrome :: [Int] -> Bool
isPalindrome x
    | length x <= 1 = True
    | head x == last x = isPalindrome (init (tail x))
    | otherwise = False

我尝试通过谷歌搜索来编写一个函数，最后得到了这个:

我真的不确定这是否是正确的方法/是否有正确的方法/是否有一种方法，我想知道它，并且我也很感谢有关代码的反馈

Answer 1

效率不是很高，因为使用 last 需要 𝓞(n) 时间、length 和 init一口井。

您可以使用reverse :: [a] -> [a]反转列表，然后检查两者是否相同:

isPalindrome :: Eq a => [a] -> Bool
isPalindrome x = <b>x == reverse x</b>

这仍然会做很多额外的工作，因为列表的一半，我们知道我们是安全的。为此，我们可以使用“兔子和乌龟”的方法来处理一半的列表:

half :: [a] -> [a]
half xs = go xs xs
  where
    go (_ : _ : xs) ~(y : ys) = <b>y :</b> go xs ys
    go _ _ = []

这将生成一个长度为 n 的列表，其中包含前 ⌊n/2⌋ 项。

那么我们可以使用:

isPalindrome :: Eq a => [a] -> Bool
isPalindrome x = and (zipWith (==) <b>(half x)</b> (reverse x))