list - Haskell 组列表直到组满足谓词

Question

如何对列表进行分组，以便一旦给定谓词不再成立，每个组就会“关闭”。类似的东西

groupWhile :: [Int] -> ([Int]->Bool) -> [[Int]]

这样

groupWhile [1,2,3,5,7,1,3,5,7] (\xs ->  (<=4) $ length $ filter odd xs) 
     = [[1,2,3,5,7],[1,3,5,7]]

我需要这个来玩纸牌游戏，我想将事件分组为几轮，这样每轮都有四张牌。然而，并非所有事件都是“卡片”事件(上例中的偶数)。

Data.List 和 Data.List.Split 函数似乎都没有做这样的事情。谓词似乎总是应用于源列表元素。

Answer 1

最基本的是，我们有

   groupWhile as pred = collect [] as where
     collect acc []     = reverse acc
     collect acc (x:xs) =
       let acc'  = x:acc
           racc' = reverse acc'
       in if pred racc'
          then racc' : collect [] xs
          else collect acc' xs

虽然这会造成很多逆转。我们可以使用 Data.List 中的两个函数更直接地计算它。

import Data.List (inits, tails)

-- forall finite (ls :: [a]) . length (inits ls) == length (tails ls)

groupWhile :: [a] -> ([a] -> Bool) -> [[a]]
groupWhile as p = pop (inits as) (tails as) where
  pop [] [] = [] 
  pop (initAs:is) (tailAs:ts)
    | p initAs  = initAs : groupWhile tailAs p
    | otherwise = pop is ts

这里 inits 构建了可能的组列表，按包含顺序排序，tails 构建了“延续”，即列表的其余部分(前提是我们选择当前组)。它们是一起生成的，每当我们将一个新的成功找到的组添加到我们的结果中时，我们就会重新继续“当前延续”tailAs。否则，我们将重复 pop 函数。