如何根据长度将 [String] 拆分为 [[String]]

Question

我正在尝试将字符串列表拆分为字符串列表列表，就像标题中那样[String] -> [[String]]

这必须根据字符长度来完成，以便输出中的列表不超过 10。因此，如果输入长度为 20，则将分解为 2 个列表，如果长度为 21，则分解为 3 个列表。

我不知道用什么来做到这一点，我什至不知道如何将一个列表分解为一个列表列表，更不用说基于一定的长度了。

例如，如果限制是5并且输入是：

["abc","cd","abcd","ab"]

输出将是：

[["abc","cd"],["abcd"],["ab"]]

我想指出正确的方向以及使用什么方法，列表理解？递归？

Answer 1

这是一个直观的解决方案：

import Data.List (foldl')

breakup :: Int -> [[a]] -> [[[a]]]
breakup size = foldl' accumulate [[]]
  where accumulate broken l
         | length l > size = error "Breakup size too small."
         | sum (map length (last broken ++ [l])) <= size
               = init broken ++ [last broken ++ [l]]
         | otherwise = broken ++ [[l]]

现在，让我们逐行浏览一下：

breakup :: Int -> [[a]] -> [[[a]]]

由于您暗示您可能希望概括该函数以接受不同的大小限制，因此我们的类型签名反映了这一点。我们还可以推广到[String](即[[Char]]) 之外，因为我们的问题并不特定于[[Char]]，并且同样适用于任何[[a]]。

breakup size = foldl' accumulate [[]]

我们使用左折叠是因为我们想要将列表从左到右转换为我们的目标，这将是子列表的列表。尽管我们不关心效率，但我们使用的Data.List.foldl'是 Prelude 自己的，foldl因为这是标准做法。您可以在此处阅读有关foldlvs. 的更多信息。foldl'

我们的折叠函数称为accumulate。它将考虑一个新项目并决定是将其放置在最后创建的子列表中还是开始一个新的子列表。为了做出这一判断，它使用size我们传入的 。我们从初始值 开始[[]]，即一个带有一个空子列表的列表。

现在的问题是，你应该如何设定accumulate你的目标？

  where accumulate broken l

我们使用broken来指代我们迄今为止构建的目标，并且l（对于“列表”）来指代下一个要处理的项目。我们将针对不同的情况使用警卫：

         | length l > size = error "Breakup size too small."

如果项目本身超出了大小限制，我们需要引发错误，因为无法将其放置在满足大小限制的子列表中。（或者，我们可以通过将返回值包装在 monad 中来构建一个安全函数Maybe，这绝对是你应该自己尝试的事情。）

         | sum (map length (last broken ++ [l])) <= size
               = init broken ++ [last broken ++ [l]]

防护条件为sum (map length (last broken ++ [l])) <= size，该防护的返回值为init broken ++ [last broken ++ [l]]。翻译成简单的英语，我们可能会说，“如果该项目可以放入最后一个子列表而不超出大小限制，则将其附加到那里。”

         | otherwise = broken ++ [[l]]

另一方面，如果最后一个子列表中没有足够的“空间”来容纳该项目，我们将启动一个新的子列表，仅包含该项目。当accumulate助手应用于输入列表中的下一个项目时，它将决定是否将该项目放入此子列表中或启动另一个子列表，遵循相同的逻辑。

你有它。别忘了import Data.List (foldl')爬到山顶。正如另一个答案指出的那样，如果您计划处理 100,000 个字符串，这不是一个高性能的解决方案。但是，我相信这个解决方案更容易阅读和理解。在很多情况下，可读性是更重要的优化。

谢谢你提出这个有趣的问题。祝 Haskell 好运，编码愉快！