Haskell group list until group satisfies a predicate

Question

How can I group a list such that each group is "closed" as soon as a given predicate no longer holds. Something like

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

such that

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]]

I need this for a card game, where I want to group events into rounds, such that each round has four cards in it. However not all events are "card" events (the even numbers in the above example).

None of the Data.List and Data.List.Split functions seem to do such things. Predicates always seem to be applied to the source list elements.

Answer 1

At it's most basic, we have

   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

though that does a lot of reversing. We can compute it more directly by using two functions from 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

Here inits builds the list of possible groups, ordered by inclusion and tails builds the "continuation", the remainder of the list provided we pick the current group. They're produced together and whenever we cons a new successfully found group on to our results we continue anew on the "current continuation" tailAs. Otherwise, we recur the pop function.

Answer 2

Quite simple when you reduce it to its basics: scan through sublists of a given list in ascending order by length and return the longest list which satisfies the predicate. Then just recurse on whats left.

groupWhile _    [] = []
groupWhile pred xs = let (a,b) = splitAtFunc pred xs in a : groupWhile pred b

splitAtFunc f xs = last $ filter (f . fst) (zip (inits xs) (tails xs))

I'm pretty sure that calling inits and tails will traverse the list twice while but you can easily fuse the two functions:

initsAndTails xs = ([], xs) : case xs of
                                []      -> []
                                x : xs' -> map (\(a,b) -> (x:a, b)) $ initsAndTails xs'