如何根据长度将[字符串]拆分为[[字符串]]

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，因为这是标准实践。您可以阅读更多关于foldl与foldl' 这里的文章。

我们的折叠函数叫做accumulate。它将考虑一个新的项目，并决定是将它放在上一个创建的子列表中，还是启动一个新的子列表。为了做出这个判断，它使用了我们传入的size。我们从[[]]的初始值开始，也就是说，一个包含一个空子列表的列表。

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

  where accumulate broken l

到目前为止，我们使用broken来引用我们构建的目标，使用l (用于"list")来引用要处理的下一个项。我们将在不同的案件中使用警卫：

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

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

         | 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')放在顶端。正如另一个答案所指出的，如果您计划处理10万个字符串，这不是一个可执行的解决方案。然而，我相信这个解决方案更容易阅读和理解。在许多情况下，可读性是最重要的优化。

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

Answer 2

你可以这样做：

splitByLen :: Int -> [String] -> [[String]]
splitByLen n s = go (zip s $ scanl1 (+) $ map length s) 0
  where go [] _ = []
        go xs prev = let (lst, rest) = span (\ (x, c) -> c - prev <= n) xs
                     in (map fst lst) : go rest (snd $ last lst)

然后：

*Main> splitByLen 5 ["abc","cd","abcd","ab"]
[["abc","cd"],["abcd"],["ab"]]

如果字符串比n长，则此函数将失败。现在，在这些情况下您想要做什么取决于您的需求，而这在您的问题中没有具体说明。

更新

根据@amar47shah的请求，我做了一个基准测试，比较了他的解决方案(breakup)和我的解决方案(splitByLen)：

import Data.List
import Data.Time.Clock
import Control.DeepSeq
import System.Random

main :: IO ()
main = do
  s <- mapM (\ _ -> randomString 10) [1..10000]
  test "breakup    10000" $ breakup    10 s
  test "splitByLen 10000" $ splitByLen 10 s
  putStrLn ""
  r <- mapM (\ _ -> randomString 10) [1..100000]
  test "breakup    100000" $ breakup    10 r
  test "splitByLen 100000" $ splitByLen 10 r

test :: (NFData a) => String -> a -> IO ()
test s a = do time1 <- getCurrentTime
              time2 <- a `deepseq` getCurrentTime
              putStrLn $ s ++ ": " ++ show (diffUTCTime time2 time1)

randomString :: Int -> IO String
randomString n = do
  l <- randomRIO (1,n)
  mapM (\ _ -> randomRIO ('a', 'z')) [1..l]

以下是研究结果：

breakup    10000: 0.904012s
splitByLen 10000: 0.005966s

breakup    100000: 150.945322s
splitByLen 100000: 0.058658s

Answer 3

这是另一种方法。从问题中可以清楚地看到，结果是一个列表，我们需要一个运行长度和一个内部列表来跟踪我们积累了多少(我们使用foldl'和这两个作为输入)。然后我们描述我们想要什么，基本上是：

1. 如果当前输入字符串本身的长度超过输入长度，则忽略该字符串(如果需要不同的行为，可以更改此字符串)。
2. 如果添加当前字符串后的新长度在输入长度之内，则将其添加到当前结果列表中。
3. 如果新长度超过输入长度，则将结果添加到输出中，并启动一个新的结果列表。

chunks len = reverse  . map reverse . snd . foldl' f (0, [[]]) where
  f (resSoFar@(lenSoFar, (currRes: acc)) curr
    | currLength > len = resSoFar -- ignore
    | newLen <= len    = (newLen, (curr: currRes):acc)
    | otherwise        = (currLength, [curr]:currRes:acc) 
    where
      newLen = lenSoFar + currLength
      currLength = length curr

每次将结果添加到输出列表中时，我们都会将其添加到前面，因此在最后需要reverse . map reverse。

> chunks 5 ["abc","cd","abcd","ab"]
[["abc","cd"],["abcd"],["ab"]]

> chunks 5 ["abc","cd","abcdef","ab"]
[["abc","cd"],["ab"]]