Haskell groupBy depending on accumulator value

Question

I have a list of pairs of views which represents list of content labels and their widths which I want to group in lines (if the next content label doesn't fit in line then put it into another line). So we have: viewList = [(View1, 45), (View2, 223.5), (View3, 14) (View4, 42)].

I want to write a function groupViews :: [a] -> [[a]] to group this list into a list of sublists where each sublist will contain only views with sum of widths less than the maximum specified width (let's say 250). So for a sorted viewList this function will return : [[(View3, 14), (View4, 42), (View1, 45)],[(View2, 223.5)]]

It looks similar to groupBy. However, groupBy doesn't maintain an accumulator. I tried to use scanl + takeWhile(<250) combination but in this case I was able to receive only first valid sublist. Maybe use iterate + scanl + takeWhile somehow? But this looks very cumbersome and not functional at all. Any help will be much appreciated.

Answer 1

I would start with a recursive definition like this:

groupViews :: Double -> (a -> Double) -> [a] -> [[a]]
groupViews maxWidth width = go (0, [[]])
  where
    go (current, acc : accs) (view : views)
      | current + width view <= maxWidth
      = go (current + width view, (view : acc) : accs) views
      | otherwise = go (width view, [view] : acc : accs) views
    go (_, accs) []
      = reverse $ map reverse accs

Invoked like groupViews 250 snd (sortOn snd viewList). The first thing I notice is that it can be represented as a left fold:

groupViews' maxWidth width
  = reverse . map reverse . snd . foldl' go (0, [[]])
  where
    go (current, acc : accs) view
      | current + width view <= maxWidth
      = (current + width view, (view : acc) : accs)
      | otherwise
      = (width view, [view] : acc : accs)

I think this is fine, though you could factor it further if you like, into one scan to accumulate the widths modulo the max width, and another pass to group the elements into ascending runs. For example, here’s a version that works on integer widths:

groupViews'' maxWidth width views
  = map fst
  $ groupBy ((<) `on` snd)
  $ zip views
  $ drop 1
  $ scanl (\ current view -> (current + width view) `mod` maxWidth) 0 views

And of course you can include the sort in these definitions instead of passing the sorted list from outside.