Haskell groupBy depending on battery size

Question

I have a list of pairs of views that represent a list of content shortcuts and their widths that I want to group in lines (if the next content label does not fit into the line and then puts it on 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 subscriptions, where each subscriber will only contain views with a sum of width less than the maximum specified width (for example, 250). Therefore, for sorted viewListthis function will return:[[(View3, 14), (View4, 42), (View1, 45)],[(View2, 223.5)]]

He looks like groupBy. However, it groupBydoes not support the battery. I tried using the scanl+ combination takeWhile(<250), but in this case I was able to get only the first valid sublist. Can somehow be used iterate+ scanl+ takeWhile? But it looks very bulky and not at all functional. Any help would be greatly appreciated.

Answer 1

I would start with such a recursive definition:

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

Called as 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)

, , , , , , - . , heres , :

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

, , .

Answer 2

, , , , .

, : "- , ", , Clojure, , , .

, Haskell:

glue :: Monoid a => (a -> Bool) -> [a] -> [a]
glue tooBig = go mempty
  where go current [] = [current]
        go current (x:xs) | tooBig x' = current : go x xs
                          | otherwise = go x' xs
          where x' = current `mappend` x

glue, Monoid ( ), glue :

import Data.Monoid (Sum(..))

data ViewGroup contents size = ViewGroup {totalSize :: size,
                                          elements :: [(contents, size)]}

instance Monoid b => Monoid (ViewGroup a b) where
  mempty = ViewGroup mempty []
  mappend (ViewGroup lSize lElts) (ViewGroup rSize rElts) = 
    ViewGroup (lSize `mappend` rSize) 
              (lElts ++ rElts)

viewGroups = let views = [("a", 14), ("b", 42), ("c", 45), ("d", 223.5)]
             in glue ((> 250) . totalSize) [ViewGroup (Sum width) [(x, Sum width)] 
                                           | (x, width) <- views]

main = print (viewGroups :: [ViewGroup String (Sum Double)])

[ViewGroup {totalSize = Sum {getSum = 101.0}, 
            elements = [("a",Sum {getSum = 14.0}),
                        ("b",Sum {getSum = 42.0}),
                        ("c",Sum {getSum = 45.0})]},
ViewGroup {totalSize = Sum {getSum = 223.5}, 
           elements = [("d",Sum {getSum = 223.5})]}]

, , , , , , , Monoid ... Monoid glue.

, , , , , . , , .

Answer 3

, groupBy span , .

groupAcc, , , , (Nothing ):

{-# LANGUAGE LambdaCase #-}

import Data.List (sortOn)
import Control.Arrow (first, second)

spanAcc :: z -> (a -> z -> Maybe z) -> [a] -> ((z, [a]), [a])
spanAcc z0 p = \case
  xs@[]      -> ((z0, xs), xs)
  xs@(x:xs') -> case p x z0 of
    Nothing  -> ((z0, []), xs)
    Just z1  -> first (\(z2, xt) -> (if null xt then z1 else z2, x : xt)) $
                spanAcc z1 p xs'

groupAcc :: z -> (a -> z -> Maybe z) -> [a] -> [(z, [a])]
groupAcc z p = \case
  [] -> [] ;
  xs -> uncurry (:) $ second (groupAcc z p) $ spanAcc z p xs

:

threshold :: (Num a, Ord a) => a -> a -> a -> Maybe a
threshold max a z0 = let z1 = a + z0 in if z1 < max then Just z1 else Nothing

groupViews :: (Ord z, Num z) => [(lab, z)] -> [[(lab, z)]]
groupViews = fmap snd . groupAcc 0 (threshold 250 . snd)

, , :

groupFinal :: (Num a, Ord a) => [(lab, a)] -> [[(lab, a)]]
groupFinal = groupViews . sortOn snd

ghci :

> groupFinal [("a", 45), ("b", 223.5), ("c", 14), ("d", 42)]
[[("c",14.0),("d",42.0),("a",45.0)],[("b",223.5)]]

If we want, we can simplify it groupAccby assuming it zis Monoid, so it memptycan be used, so that:

groupAcc2 :: Monoid z => (a -> z -> Maybe z) -> [a] -> [(z, [a])]
groupAcc2 p = \case
  [] -> [] ;
  xs -> let z = mempty in
        uncurry (:) $ second (groupAcc z p) $ spanAcc z p xs