P16 - 每隔 N 个删除一个元素
Drop every N’th element from a list
官方模块:
Problems.P16核心函数:dropEvery
← P15 每个元素重复 N 次 | P17 在 N 处切分列表 →
题目描述
删除列表中每隔 N 个位置的元素（从 1 开始计数）。
函数签名
1dropEvery :: [a] -> Int -> [a]
思路
两种思路：
- 带计数器递归：维护一个下标计数器，每到 N 就跳过
zip标号过滤：给每个元素标上位置序号，只保留序号不是 N 的倍数的
实现
方法一：递归 + 计数器
1dropEvery :: [a] -> Int -> [a]
2dropEvery [] _ = []
3dropEvery (x:xs) n = go x 1 xs
4 where
5 go x i [] = if i == n then [] else [x]
6 go x i (y:ys)
7 | i == n = go y 1 ys
8 | otherwise = x : go y (i + 1) ys
用一个计数器 i 跟踪当前位置，每到 N 就丢弃当前元素。
也可以把当前元素和计数器一起追踪，更简洁的写法：
1dropEvery :: [a] -> Int -> [a]
2dropEvery xs n = [x | (x, i) <- zip xs [1..], i `mod` n /= 0]
方法二：zip + 列表推导（推荐）
1dropEvery :: [a] -> Int -> [a]
2dropEvery xs n = map fst . filter (\(_, i) -> i `mod` n /= 0) $ zip xs [1..]
zip xs [1..] 给每个元素编号，filter 去掉序号是 n 的倍数的元素，map fst 取回原值。
方法三：take/drop 分块
1dropEvery :: [a] -> Int -> [a]
2dropEvery [] _ = []
3dropEvery xs n = take (n - 1) xs ++ dropEvery (drop n xs) n
取前 n-1 个保留，跳过第 n 个，递归处理剩余部分。这个实现最符合"间隔删除"的语义理解。
dropEvery 的求值过程
以 dropEvery "abcdefghik" 3 为例：
1dropEvery "abcdefghik" 3
2= take 2 "abcdefghik" ++ dropEvery (drop 3 "abcdefghik") 3
3= "ab" ++ dropEvery "defghik" 3
4= "ab" ++ ("de" ++ dropEvery "ghik" 3)
5= "ab" ++ ("de" ++ ("gh" ++ dropEvery "k" 3))
6= "ab" ++ ("de" ++ ("gh" ++ "k"))
7= "abdeghk"
测试
1>>> dropEvery "abcdefghik" 3
2"abdeghk"
3
4>>> dropEvery [1,2,3,4,5] 2
5[1,3,5]
6
7>>> dropEvery "a" 3
8"a"
9
10>>> dropEvery [] 3
11[]