haskell - 将foldl 转换为fold1

Question

我使用以下折叠来获取列表的最终单调递减序列。

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 类型通用？

Answer 1

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 any Ord 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]