P19 - 旋转列表 N 位
Rotate a list N places to the left
官方模块:
Problems.P19核心函数:rotate
题目描述
将列表向左旋转 N 位。N 为正数时左移，N 为负数时右移（等价于左移负数位）。
函数签名
1rotate :: [a] -> Int -> [a]
思路
旋转操作可以理解为切分后交换：
- 左移 n 位：
drop n xs ++ take n xs - 右移 n 位 = 左移
length xs - n位
关键在于处理负数 N 和 N 超出列表长度的情况。先用 mod 把 N 归一化到 [0, length xs - 1] 范围。
实现
方法一：splitAt + 交换
1rotate :: [a] -> Int -> [a]
2rotate xs n = let (left, right) = splitAt (n `mod` length xs) xs
3 in right ++ left
n mod length xs 把任意整数归一化到合法范围。然后用 splitAt 切分，交换前后两部分。
注意：
length xs对空列表会报错，需要单独处理。
方法二：安全处理空列表
1rotate :: [a] -> Int -> [a]
2rotate [] _ = []
3rotate xs n = let k = n `mod` length xs
4 (left, right) = splitAt k xs
5 in right ++ left
先处理空列表 case，避免 length [] 导致除以零。
方法三：纯递归
1rotate :: [a] -> Int -> [a]
2rotate xs 0 = xs
3rotate [] _ = []
4rotate (x:xs) n
5 | n > 0 = rotate (xs ++ [x]) (n - 1)
6 | otherwise = rotate (last xs : init xs) (n + 1)
每次左移一位：把头部移到尾部，递归 n-1 次。直观但效率低（O(n × m)）。
理解 mod 的作用
Haskell 的 mod 对负数也返回非负结果：
13 `mod` 8 -- 3
2(-3) `mod` 8 -- 5
所以 n mod length xs 可以统一处理正负旋转：
1rotate "abcdefgh" 3 → k = 3 → "defghabc" (左移3)
2rotate "abcdefgh" (-2) → k = 6 → "ghabcdef" (右移2 = 左移6)
测试
1>>> rotate "abcdefgh" 3
2"defghabc"
3
4>>> rotate "abcdefgh" (-2)
5"ghabcdef"
6
7>>> rotate [1,2,3,4,5] 0
8[1,2,3,4,5]
9
10>>> rotate [1,2,3,4,5] 7 -- 7 mod 5 = 2
11[3,4,5,1,2]
12
13>>> rotate [] 3
14[]