haskell 的 foldr 是否总是采用两个参数的 lambda？

Question

Haskell 新来的

我正在 haskell 解决这个问题：

(**) Eliminate consecutive duplicates of list elements.
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.

Example:
* (compress '(a a a a b c c a a d e e e e))
(A B C A D E)

解决方案（我不得不查找）使用 foldr:

compress' :: (Eq a) => [a] -> [a]
compress' xs = foldr (\x acc -> if x == (head acc) then acc else x:acc) [last xs] xs

根据解法，这个foldr有两个参数，x和acc。似乎所有文件夹都采用这些参数；这有什么例外吗？像一个需要 3 个或更多的文件夹？如果不是，这个约定是不是多余，能不能用更少的代码写出公式？

Answer 1

与 haskell 中的所有内容一样，请查看类型的内容来指导您的操作，您可以对 ghci 中的任何函数执行此操作.

查看 foldr 我们看到：

Prelude> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

这个稍微抽象的字符串可以用英文写成：

foldr 是一个接受

的函数

1 ) 具有两个参数的函数，一个是 a 类型，一个是 b 类型，returns 是 b

类型

2 ) b

类型的值

3 ) a

类型值的列表

和returns类型的值b

其中 a 和 b 是类型变量（请参阅 here 以获得有关它们的良好教程），可以填写您喜欢的任何类型。

Answer 2

foldr 采用 2 个参数的函数，但这并不妨碍它采用 3 个参数的函数，前提是该函数具有正确的类型签名。

如果我们有一个函数

g :: x -> y -> z -> w

有

foldr :: (a -> b -> b) -> b -> [a] -> b

我们要将g传递给foldr，然后是(a -> b -> b) ~ (x -> y -> z -> w)（其中~是类型相等）。由于 -> 是右结合的，这意味着我们可以将 g 的签名写成

x -> y -> (z -> w)

和它的意思是一样的。现在我们已经生成了两个参数的函数，returns 一个参数的函数。为了将其与 a -> b -> b 类型统一，我们只需要排列参数：

a ->   |  x ->
b ->   |  y -> 
b      |  (z -> w)

这意味着 b ~ z -> w，所以 y ~ b ~ z -> w 和 a ~ x 所以 g 的类型确实必须是

g :: x -> (z -> w) -> (z -> w)

暗示

foldr g :: (z -> w) -> [x] -> (z -> w)

这当然不是不可能的，尽管可能性更大。我们的累加器是一个函数，对我来说这需要用 DiffLists 来证明：

type DiffList a = [a] -> [a]

append :: a -> DiffList a -> DiffList a
append x dl = \xs -> dl xs ++ [x]

reverse' :: [a] -> [a]
reverse' xs = foldr append (const []) xs $ []

请注意 foldr append (const []) xs returns 一个函数，我们将其应用于 [] 以反转列表。在这种情况下，我们为 [a] -> [a] 类型的函数指定了一个名为 DiffList 的别名，但这实际上与编写

没有什么不同

append :: a -> ([a] -> [a]) -> [a] -> [a]

它是 3 个参数的函数。

Answer 3

事实证明，您可以使用具有三参数函数的 foldr 来解决您的 compress 问题。

compress :: Eq a => [a] -> [a]
compress [] = []
compress (z:zs) = z : foldr f (const []) zs z
  where f x k w | x==w      = k x
                | otherwise = x : k x

让我们来剖析一下。首先，我们可以通过将最后两行更改为

来提高可读性

  where f x k = \w -> if x==w then k x else x : k x

这表明三元函数不过是二元函数 return 一元函数。以这种方式查看它的好处是 foldr 在传递二进制函数时最好理解。事实上，我们是传递一个二进制函数，这恰好 return 一个函数。

现在让我们关注类型：

f :: a -> (a -> [a]) -> (a -> [a])
f    x    k

所以，x::a 是我们要折叠的列表的元素。函数 k 是列表尾部折叠的结果。 f x k 的结果与 k.

的类型相同

\w -> if ....    :: (a -> [a])

这个匿名函数背后的总体思路如下。参数 k 与 OP 代码中的 acc 起着相同的作用，除了它是一个函数，期望列表中的 previous 元素 w before生成累积的压缩列表。

具体来说，我们在使用acc时使用nowk x，将当前元素传递给下一步，因为到那时x将成为前一个元素w。在顶层，我们将 z 传递给 return 由 foldr f (const []) 编辑的函数。

这个 compress 变体是惰性的，与发布的解决方案不同。事实上，发布的解决方案需要在开始生成某些内容之前扫描整个列表：这是由于 (\x acc -> ...) 在 acc 中是严格的，并且由于 last xs 的使用。相反，以上压缩以 "streaming" 方式输出列表元素。实际上，它也适用于无限列表：

> take 10 $ compress [1..]
[1,2,3,4,5,6,7,8,9,10]

话虽如此，我认为在这里使用 foldr 感觉有点奇怪：上面的代码可以说比显式递归的可读性差。

haskell 的 foldr 是否总是采用两个参数的 lambda？

Does haskell's foldr always take a two-parameter lambda?

haskell

fold