P06 - 判断回文
Palindromes
官方模块:
Problems.P06核心函数:isPalindrome
题目描述
判断一个列表是否为回文（palindrome），即正着读和反着读相同。元素类型需要支持相等比较。
函数签名
1isPalindrome :: Eq a => [a] -> Bool
Eq a 约束是因为需要比较元素是否相等。
思路
回文的判定方法有多种：
- 反转比较：反转列表后与原列表比较
- 头尾递推：比较首尾元素，然后递归处理中间部分
- 双指针：用
zip配对前后元素逐一比较
实现
方法一：反转比较（最简单）
1isPalindrome :: Eq a => [a] -> Bool
2isPalindrome xs = xs == reverse xs
一行搞定。如果反转后和原列表相同，就是回文。
这是理解上最直接的方法，复杂度 O(n)——reverse 是 O(n)，== 也是 O(n)。
方法二：递归检查首尾
1isPalindrome :: Eq a => [a] -> Bool
2isPalindrome [] = True
3isPalindrome [_] = True
4isPalindrome (x:xs) = x == last xs && isPalindrome (init xs)
比较第一个和最后一个，然后递归检查去掉首尾的内部列表。
注意：
last和init都是 O(n) 操作，因此这个方法的总复杂度是 O(n²)，不如方法一。
方法三：使用 zip 成对比较（推荐）
1isPalindrome :: Eq a => [a] -> Bool
2isPalindrome xs = and . zipWith (==) xs . reverse $ xs
将原列表和反转列表用 zipWith 逐对比较，and 检查是否全部相等。如果列表很长，可以只比较前半部分来优化：
1isPalindrome :: Eq a => [a] -> Bool
2isPalindrome xs = and . zipWith (==) xs . reverse $ xs
3 where
4 half = length xs `div` 2
方法四：使用 foldr 构建反转并比较
1isPalindrome :: Eq a => [a] -> Bool
2isPalindrome xs = xs == foldr (:) [] xs
foldr (:) [] xs 用右 fold 重新构造列表——对于列表来说是恒等操作？不对，实际上 foldr (:) [] xs == xs 是恒等的。
要检查回文，正确用法是依赖 reverse，或者用 foldl 构建反转：
1isPalindrome :: Eq a => [a] -> Bool
2isPalindrome xs = xs == foldl (\acc x -> x : acc) [] xs
测试
1>>> isPalindrome [1,2,3]
2False
3
4>>> isPalindrome "madamimadam"
5True
6
7>>> isPalindrome [1,2,4,8,16,8,4,2,1]
8True
9
10>>> isPalindrome ""
11True
12
13>>> isPalindrome "a"
14True