Haskell groupBy 取决于累加器值

Question

我有一个视图对列表，它表示内容标签及其宽度的列表，我想将它们分组到行中（如果下一个内容标签不适合一行，则将其放入另一行）。所以我们有：viewList = [(View1, 45), (View2, 223.5), (View3, 14) (View4, 42)].

我想编写一个函数 groupViews :: [a] -> [[a]] 将此列表分组为子列表列表，其中每个子列表仅包含宽度总和小于最大指定宽度的视图（假设 250 ). 所以对于排序的 viewList 这个函数将 return : [[(View3, 14), (View4, 42), (View1, 45)],[(View2, 223.5)]]

它看起来类似于 groupBy。但是，groupBy 不维护累加器。我尝试使用 scanl + takeWhile(<250) 组合，但在这种情况下，我只能收到第一个有效的子列表。也许以某种方式使用 iterate + scanl + takeWhile ？但这看起来很麻烦而且根本不起作用。任何帮助将不胜感激。

Answer 1

我将从这样的递归定义开始：

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

像 groupViews 250 snd (sortOn snd viewList) 那样调用。我首先注意到的是它可以表示为左折：

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)

我认为这很好，但如果您愿意，您可以进一步将其分解为一次扫描以累积宽度以最大宽度为模，然后通过另一次扫描将元素分组为升序运行。例如，这是一个适用于整数宽度的版本：

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

鉴于groupBy和span本身是由手动递归函数定义的，我们修改后的函数将使用相同的机制。

让我们首先定义一个通用函数groupAcc，它接受累加器的初始值，然后定义一个函数，它接受列表中的一个元素、当前累加器状态并可能产生一个新的累加值（没有表示元素不被接受):

{-# 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)]]

如果我们愿意，我们可以通过假设 z 是一个 Monoid 来简化 groupAcc，因此可以使用 mempty，这样：

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

Answer 3

我不知道通过组合标准库中的函数来实现这一点的巧妙方法，但我认为你可以做得比从头开始实现更好。

这个问题属于 class 我以前见过的问题："batch up items from this list somehow, and combine its items into batches according to some combination rule and some rule for deciding when a batch is too big"。多年前，当我在写 Clojure 时，我 built a function 抽象出这种批处理组合的想法，只要求您指定批处理的规则，并且能够在数量惊人的地方使用它。

以下是我认为可以在 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 本身的调用中完成。

嗯，我不知道，也许工作量仍然太大，尤其是如果您不相信可以重用该类型。但我确实认为，认识到这是一个更普遍的问题的特定案例并尝试解决更普遍的问题是很有用的。

Haskell groupBy 取决于累加器值

Haskell groupBy depending on accumulator value

algorithm

haskell

functional-programming

fold