将 foldl 转换为 fold1

Question

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

foldl (\acc x -> if x<=(last acc) then acc ++ [x] else [x]) [(-1)] a

所以 [9,5,3,6,2,1] 会 return [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 是一个 空列表 ，此函数将出错（而您可能想要 return 空列表）；和
代码效率不是很高，因为 last 和 (++) 运行在 O(n).

第一个问题可以通过使用 模式匹配 来轻松解决，以防止出现这种情况。但对于后者，您最好使用 reverse 方法。比如：

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) 中的运行s 所以 g 运行中的所有操作都在 中O(1)（考虑到课程比较效率等）使算法本身 O(n).

对于您的示例输入，它给出：

*Main> f [9,5,3,6,2,1]
[6,2,1]

Answer 2

foldl1的类型是：

Foldable t => (a -> a -> a) -> t a -> a

你的函数参数，

\acc x -> if x<=(last acc) then acc ++ [x] else [x]

有类型：

(Ord a) => [a] -> a -> [a]

当 Haskell 的类型检查器尝试对您的函数进行类型检查时，它会尝试将类型 a -> a -> a（foldl1 的第一个参数的类型）与类型 [a] -> a -> [a]（你的函数的类型）。

要统一这些类型需要将 a 与 [a] 统一，这将导致无限类型 a ~ [a] ~ [[a]] ~ [[[a]]]... 等等。

之所以在使用 foldl 时有效，是因为 foldl 的类型是：

Foldable t => (b -> a -> b) -> b -> t a -> b

因此 [a] 与 b 统一，a 与另一个 a 统一，因此完全没有问题。

foldl1 的局限性在于它只能采用只处理一种类型的函数，或者换句话说，累加器需要与输入列表的类型相同（例如，折叠时Int 的列表，foldl1 只能 return 和 Int，而 foldl 可以使用任意累加器。所以你不能使用 foldl1).

关于使所有 Ord 值通用，一种可能的解决方案是为声明自己的 "least-bound" 值的值创建一个新的类型类，然后您的函数将使用该值.您不能创建此函数，因为它对所有 Ord 值都是通用的，因为并非所有 Ord 值都具有您可以使用的最小序列边界。

class LowerBounded a where
    lowerBound :: a

instance LowerBounded Int where
    lowerBound = -1

finalDecreasingSequence :: (Ord a, LowerBounded a) => [a] -> [a]
finalDecreasingSequence = foldl buildSequence lowerBound
  where buildSequence acc x
    | x <= (last acc) = acc ++ [x]
    | otherwise       = [x]

您可能还想阅读一些关于 how Haskell does its type inference 的内容，因为它有助于找出与您遇到的错误类似的错误。

将 foldl 转换为 fold1

Converting a foldl into fold1

haskell

fold