Haskell group依赖于累加器值

Question

我有一对视图对列表,它们代表内容标签列表及其宽度我希望按行分组(如果下一个内容标签不符合行,则将其放入另一行).所以我们有:viewList = [(View1, 45), (View2, 223.5), (View3, 14) (View4, 42)].

我想写一个函数groupViews :: [a] -> [[a]]将这个列表分组到一个子列表列表中,其中每个子列表只包含宽度小于最大指定宽度的视图(比方说250).因此,对于已排序的viewList此函数将返回:[[(View3, 14), (View4, 42), (View1, 45)],[(View2, 223.5)]]

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

Answer 1

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

\n\n

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

\n\n

像这样调用groupViews 250 snd (sortOn snd viewList)。我注意到的第一件事是它可以表示为左折叠：

\n\n

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

\n\n

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

\n\n

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

\n\n

当然，您可以在这些定义中包含排序，而不是从外部传递排序列表。

\n