我使用以下折叠来获取列表的最终单调递减序列。
foldl (\acc x -> if x<=(last acc) then acc ++ [x] else [x]) [(-1)] a
因此 [9,5,3,6,2,1]
将返回 [6,2,1]
然而,对于foldl
,我需要为折叠提供一个开始,即[(-1)]
。我试图变成一个 foldl1
,以便能够处理任何范围的整数以及任何 Ord
,如下所示:
foldl1 (\acc x -> if x<=(last acc) then acc ++ [x] else [x]) a
但我遇到错误:
cannot construct infinite type: a ~ [a]
in the second argument of (<=) namely last acc
我的印象是 foldl1
基本上是:
foldl (function) [head a] a
但我想事实并非如此?您将如何使此折叠对于任何 Ord
类型通用?
最佳答案
I was under the impression that foldl1 was basically :
foldl (function) [head a] a
不,foldl1
基本上是:
foldl function <b>(head a) (tail a)</b>
所以初始元素不是head a
的列表,而是head a
。
How would you go about making this
fold
generic for anyOrd
type?
快速解决方法是:
foldl (\acc x -> if x<=(last acc) then acc ++ [x] else [x]) [<b>head a</b>] <b>(tail a)</b>
但是仍然存在两个问题:
- 如果
a
是一个空列表,这个函数将会出错(而你可能想返回空列表);和 - 由于
last
和(++)
的运行时间都为 O(n),所以代码效率不是很高。
通过使用模式匹配可以轻松解决第一个问题,以防止出现这种情况。但对于后者,您最好使用反向
方法。例如:
f :: Ord t => [t] -> [t]
f [] = [] -- case when the empty list is given
f a = reverse $ foldl (\acc@(ac:_) x -> if x <= ac then (x:acc) else [x]) [head a] (tail a)
此外,我个人不太喜欢函数式编程中的 if
-then
-else
,例如,您可以定义一个辅助函数像:
f :: Ord t => [t] -> [t]
f [] = [] -- case when the empty list is given
f a = reverse $ foldl g [head a] (tail a)
where g acc@(ac:_) x | x <= ac = (x:acc)
| otherwise = [x]
现在,reverse
的运行时间为 O(n),但这只执行一次。此外,(:)
构造在 O(1) 中运行,因此 g
中的所有操作在 O(1) 中运行em>(考虑到类(class)工作效率的比较,等等)使得算法本身O(n)。
对于您的示例输入,它给出:
*Main> f [9,5,3,6,2,1]
[6,2,1]
关于haskell - 将foldl 转换为fold1,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43162239/