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