list - 使用 foldr 将列表分成指定大小的子列表

Question

我正在上一门函数式编程类(class)，我很难摆脱 OOP 的思维方式，也很难找到很多问题的答案。

我必须创建一个函数，它接受一个有序列表并使用 fold 的变体将其转换为指定大小的子列表。

这是不对的，但这是我所拥有的:

splitList :: (Ord a) => Int -> [a] -> [[a]]
splitList size xs
    | [condition] = foldr (\item subList -> item:subList) [] xs
    | otherwise =

我一直在搜索，我发现 foldr 是更适合我想要的变体，我想我已经了解 fold 的工作原理，我只是不知道如何我将设置守卫，以便当 length sublist == size 时，haskell 会重置累加器并继续处理下一个列表。

如果我没有正确解释自己，这是我想要的结果:

> splitList 3 [1..10]
> [[1,2,3],[4,5,6],[7,8,9],[10]]

谢谢!

Answer 1

虽然 Fabián 和 chi 的答案完全正确，但实际上有一个选项可以使用 foldr 来解决这个难题。考虑以下代码:

splitList :: Int -> [a] -> [[a]]
splitList n =
  foldr (\el acc -> case acc of
            []                      -> [[el]]
            (h : t) | length h < n  -> (el : h) : t
            _                       -> [el] : acc 
            ) []

这里的策略是通过扩展其头部来构建一个列表，只要它的长度小于所需的长度。但是，此解决方案有两个缺点:

• 它做的事情与您的示例略有不同；

  splitList 3 [1..10] 生成 [[1],[2,3,4],[5,6,7],[8,9,10] ]

• 它的复杂度是 O(n * length l)，因为我们在每个元素上测量最多 n 大小的列表的长度，这会产生线性操作数。

---

让我们先解决第一个问题。为了从头开始计数，我们需要从左到右遍历列表，而 foldr 从右到左遍历。有一个常见的技巧叫做“继续传递”，它可以让我们反转行走的方向:

splitList :: Int -> [a] -> [[a]]
splitList n l = map reverse . reverse $
  foldr (\el cont acc ->
            case acc of
              [] -> cont [[el]]
              (h : t) | length h < n -> cont ((el : h) : t)
              _ -> cont ([el] : acc)
           ) id l []

在这里，我们没有在累加器中构建列表，而是构建了一个函数，该函数将向正确的方向转换列表。参见 this question了解详情。副作用是反转列表，因此我们需要通过对整个列表及其所有元素应用 reverse 来应对。这是线性和尾递归的。

---

现在让我们来解决性能问题。问题是 length 在临时列表上是线性的。有两种解决方案:

• 使用另一个缓存长度的结构以进行恒定时间访问
• 自己缓存值

因为我猜这是一个列表练习，让我们选择后一个选项:

splitList :: Int -> [a] -> [[a]]
splitList n l = map reverse . reverse . snd $
  foldr (\el cont (countAcc, listAcc) ->
            case listAcc of
              []                     -> cont (countAcc, [[el]])
              (h : t) | countAcc < n -> cont (countAcc + 1, (el : h) : t)
              (h : t)                -> cont (1, [el] : (h : t))
           ) id l (1, [])

在这里，我们使用一个计数器来扩展我们的计算状态，该计数器在每个点都存储列表的当前长度。这使我们能够不断检查每个元素，并最终导致线性时间复杂度。