使用foldr单遍遍历无++拆分列表为同值子列表的代码问题排查

代码问题分析 #

你实现的代码核心错误有两点：

1. foldr 是从列表右端向左端遍历，你设计的b标志位逻辑不符合遍历顺序要求：处理元素8时触发新建组分支，b被设为True；接下来处理左侧的7时命中b=True分支，直接把7加入8所在的组，后续处理更左侧的7时，因和当前组首元素相等再次加入同一组，最终生成错误的[7,7,8]分组。
2. 多余的b标志位逻辑设计错误，该标志原本用来控制是否新建组，但实际不需要这个参数，仅通过判断当前元素和上一个已处理的右侧元素是否相等，即可实现连续相同元素分组。

修改方案 #

方案1：标准连续相同元素分组（对应标准group函数功能） #

你给出的示例预期输出大概率存在笔误，标准连续相同元素分组的实现如下：

splitList :: Eq a => [a] -> [[a]]
splitList = fst . foldr func ([], undefined)
  where
    func cur ([], _) = ([[cur]], cur)
    func cur (res@(firstGroup:rest), lastVal)
      | cur == lastVal = ((cur : firstGroup) : rest, cur)
      | otherwise = ([cur] : res, cur)

运行结果：

ghci> splitList [1,2,2,4,5,7,7,8,9]
[[1],[2,2],[4],[5],[7,7],[8],[9]]

方案2：匹配你给出的示例预期输出 #

如果确实需要得到你给出的[[1],[2,2],[4,5],[7,7],[8,9]]结果（规则为连续相同元素分组后，相邻的长度为1的组合并），修改后代码如下，仍满足单遍遍历、无++运算符的要求：

splitList :: [Int] -> [[Int]]
splitList = getRes . foldr func ([], 0, 0)
  where
    func c ([], _, _) = ([[c]], 1, c)
    func c (res@(x:xs), lastGroupLen, lastVal)
      | c == lastVal = ((c:x):xs, length x + 1, c)
      | lastGroupLen == 1 = ((c:x):xs, 2, c)
      | otherwise = ([c]:res, 1, c)
    getRes (r, _, _) = r

运行结果：

ghci> splitList [1,2,2,4,5,7,7,8,9]
[[1],[2,2],[4,5],[7,7],[8,9]]

内容的提问来源于stack exchange，提问作者Bohdan Chornopolskyi