gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-01 23:43:00 25 4
gpt4 key购买 nike

我正在上一门函数式编程类(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]]

谢谢!

最佳答案

虽然 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, [])

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

关于list - 使用 foldr 将列表分成指定大小的子列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/64745696/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com