haskell的foldr总是采用双参数lambda吗？

Question

Haskell newb在这里

我正在研究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

根据解决方案,该折叠器采用两个参数,x和acc.似乎所有折叠者都采用这些参数; 这有什么例外吗？像折叠器需要3个或更多？如果没有,这个约定是多余的,公式可以用更少的代码编写吗？

Answer 1

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)

它的意思是一样的.现在我们已经生成了两个参数的函数,它返回一个参数的函数.为了将其与类型统一起来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返回我们应用于[]反转列表的函数.在这种情况下,我们给了[a] -> [a]所谓类型函数的别名DiffList,但它与编写完全没有什么不同

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

这是3个参数的函数.

Answer 2

与 haskell 中的所有事物一样，请查看事物的类型来指导您的方式，您可以对ghci.

看看这个foldr我们看到：

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

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

foldr是一个函数，它需要

1 ) 一个函数，有两个参数，一个是 type a，一个是 type b，并返回一些类型b

2）类型的值b

3）类型值列表a

并返回一个类型的值b

其中a和b是类型变量（有关它们的详细教程，请参阅此处），可以用您喜欢的任何类型填充。