Haskell实现sliceBy列表切片的otherwise分支编写方法

规则说明 #

sliceBy的分组规则为：

• 连续满足判定函数f（返回True）的元素构成一个组，连续不满足f（返回False）的元素构成相邻的下一个组，两类组交替排列
• 返回结果必须以「满足f的组」开头，如果列表第一个元素不满足f，则在结果最前面补一个空的满足f的组

预期运行效果 #

sliceBy odd [1..5] == [[1],[2],[3],[4],[5]]
sliceBy odd [1,3,2,4,5,7,4,6] == [[1,3],[2,4],[5,7],[4,6]]
sliceBy even [1,3,2,4,5,7,4,6] == [[],[1,3],[2,4],[5,7],[4,6]]

原有代码问题 #

你写的初始框架存在三个核心问题：

1. 单元素基础情况错误：当元素不满足f时，单元素结果应为[[],[x]]而非[[x]]
2. f x为True时直接开新组的逻辑错误：后续连续满足f的元素需要和当前元素合并到同一个组，不能拆分
3. 未定义otherwise分支的分组逻辑

正确实现代码 #

通过内部辅助递归函数维护「返回结果第一个组永远是满足f的组」的不变量，递归到列表末尾时返回空的满足f的组作为终止符，代码如下：

sliceBy :: (a -> Bool) -> [a] -> [[a]]
sliceBy _ [] = []
sliceBy f xs = go xs
  where
    go [] = [[]]
    go (y:ys) =
      let rest@(rHead:rTail) = go ys
      in if f y
         -- 当前元素满足f，追加到第一个（满足f的）组头部
         then (y : rHead) : rTail
         -- 当前元素不满足f
         else if null rHead
              -- 第一个组是空的f=True组，当前元素追加到后续第一个f=False组头部
              then [] : (y : head rTail) : tail rTail
              -- 第一个组是非空f=True组，插入空f=True组，新建f=False组放当前元素
              else [] : [y] : rest

逻辑验证 #

以sliceBy even [1,3,2,4,5,7,4,6]为例，递归从后往前执行完全符合预期：

1. 递归到末尾[]返回终止符[[]]
2. 处理6（满足even），追加到空组头部得到[[6]]
3. 处理4（满足even），追加到第一个组头部得到[[4,6]]
4. 处理7（不满足even，第一个组非空），插入空组+新组得到[[],[7],[4,6]]
5. 处理5（不满足even，第一个组为空），追加到第二个组头部得到[[],[5,7],[4,6]]
6. 处理2（满足even），追加到第一个空组头部得到[[2],[5,7],[4,6]]
7. 处理4（满足even），追加到第一个组头部得到[[2,4],[5,7],[4,6]]
8. 处理3（不满足even，第一个组非空），插入空组+新组得到[[],[3],[2,4],[5,7],[4,6]]
9. 处理1（不满足even，第一个组为空），追加到第二个组头部得到[[],[1,3],[2,4],[5,7],[4,6]]，和预期结果完全一致

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