haskell - 使用折叠将字符串拆分为给定长度的字符串列表

Question

我想使用 fold 将字符串拆分为给定长度的字符串列表。

split :: n -> String -> [String]
split 4 "abcdefghijklmnopqrst" -> ["abcd","efgh","ijkl","mnop","qrst"]

这可以使用 foldr 来完成吗？ ?你能提供一个解释，让我对如何使用折叠来解决这样的问题有一些直觉吗？
编辑:我添加了递归解决方案

split :: Int -> String -> [String]
split len xs
  | len >= length xs = [xs]
  | otherwise = take len xs : split len (drop len xs)

Answer 1

要将递归代码转换为 foldr，您需要进一步内联和融合 length 、 take 和 drop 的定义，以便您的代码一次解构输入列表一个元素，就像 foldr 那样:

split :: Int -> [a] -> [[a]]
split len xs
  | len >= length xs = [xs]
  | otherwise = take len xs : split len (drop len xs)
  where
  take :: Int -> [a] -> [a]
  take 0 xs = xs
  take 0 [] = []
  take n (x:xs) = x : take (n-1) xs
  -- and for `drop` and `len >= length` as well
  -- ......

所以我们需要为此添加一个计数器。

split2 :: Int -> [a] -> [[a]]
split2 len xs = go xs 0
  where
  go [] _  = [[]]    -- [] : []
  go (x:xs) i 
    | i < len = [x] : go xs (i+1)
    | otherwise =     go xs 0

(请在这里修复一个或多个错误，好吗)。
这当然不会产生正确的结果，但它已经遵循 foldr 模式!它同时进行计数和跳过，并正确选择点从 0 重新开始计数，该点对应于使用 drop ped 列表的递归调用 - 已经免费完成，只需沿着输入列表一个元素一次——就像 foldr 那样。我们只需要保存那些我们目前忘记的元素:

split3 :: Int -> [a] -> [[a]]
split3 len xs = go xs 0 []
  where
  go [] _ ys = [reverse ys]
  go (x:xs) i ys
    | i < len = go xs (i+1) (x:ys)
    | otherwise = reverse (x:ys) : go xs 0 []

这直接映射到 foldr 递归模式，我们将 LHS 上的 go (x:xs) 替换为 g x r ，将 RHS 上的 go xs 替换为 r :

split4 :: Int -> [a] -> [[a]]
split4 len xs = foldr g z xs 0 []
  where
  z _ ys = [reverse ys]
  g x r i ys 
    | i < len = r (i+1) (x:ys)
    | otherwise = reverse (x:ys) : r 0 []

-- > split4 4 "123456"
-- ["12345","6"]

再次，请修复逐一错误。
但是，这并不是完全懒惰，即 (!! 0) . head . split4 3 $ "12"++undefined 会发散而不是返回字符 '1' ，因为它可以说是应该的。
为了实现这一点，我们必须立即返回结构，即使其中有孔，然后再填充这些孔:

split5 :: Int -> [a] -> [[a]]
split5 len xs = foldr g z xs 1
  where
  z _ = [[]]
  g x r i
    | i < len = let (a:b) = r (i+1) in (x:a):b
    | otherwise = [x] : r 1

有了这个，

> split5 4 "123456"
["1234","56"]

> take 2 . head . split5 4 $ "12" ++ undefined
"12"

这里仍然存在一个极端情况，即返回值不太正确。一定要找到它，并尝试修复它。