CODEWITHSUNDEEP
listhaskell
Martin Drautzburg
Martin Drautzburg

Reputation: 5243

Haskell group list until group satisfies a predicate

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.

Upvotes: 4

Views: 820

Answers (4)

user2407038
user2407038

Reputation: 14578

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'

Upvotes: 2

rmcclellan
rmcclellan

Reputation: 446

The simplest approach is to use the linear recursion method recommended in sicp, that is, factor out your state (in this case the "current sublist" and the "current list of sublists" into arguments to a tail-call recursive helper function.

This simple solution requires that p not be sensitive to reversing the list.

groupWhile :: [Int] -> ([Int]->Bool) -> [[Int]]
groupWhile = groupWhileHelp [] []
  where groupWhileHelp a [] [] _ = reverse a
        groupWhileHelp a b [] _ = reverse $ reverse b : a
        groupWhileHelp a b (x:xs) p | p $ x : b = groupWhileHelp a (x:b) xs p
        groupWhileHelp a b (x:xs) p = groupWhileHelp (reverse b : a) [x] xs p

Another simple, classic approach is to use foldl (this one reverses the list every time, removing that restriction on p while increasing computation time). Either recursion scheme could in principle reverse the list each time or not, of course.

groupWhile :: [Int] -> ([Int]->Bool) -> [[Int]]
groupWhile l p = reverse $ foldl (addOne p) [] l where
  addOne _ [] x = [[x]]
  addOne p (xs:xss) x | p $ xs ++ [x] = (xs ++ [x]):xss
                      | otherwise = [x]:xs:xss

Upvotes: 1

Paul
Paul

Reputation: 8172

There might be more elegant solutions, but this is a simple way:

groupWhile :: [a] -> ([a] -> Bool) -> [[a]]
groupWhile ys p = go [] p ys
    where
        go xs _ []                = [reverse xs]
        go xs p (y:ys) | p (y:xs) = go (y:xs) p ys
        go xs p (y:ys)            = reverse xs : go [y] p ys

Note: Because snocing onto the end of a list (xs ++ [y]) is really inefficient (O(n)) we cons in go's second case ((y:xs)) and build up a reverse list this way. Then, when we are done with the current chunk (no more ys or p xs is false) we reverse the xs again to get them into the right order.

Upvotes: 1

J. Abrahamson
J. Abrahamson

Reputation: 74334

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.

Upvotes: 3

Related Questions