Haskell 99 个问题 #8 : Can't understand foldr

Question

我正在做 Haskell 的练习 99 questions .

Problem 8

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 in Haskell:

 > compress "aaaabccaadeeee" 

 "abcade"

我无法理解这个解决方案:

compress xs = foldr f (const []) xs Nothing
  where
    f x r a@(Just q) | x == q = r a
    f x r _ = x : r (Just x)

foldr需要三个参数。第一个参数是一个函数 (a -> b -> b) .第二个是初始累加器，第三个是列表。

是 (const [])传递给 foldr 的第二个参数?

函数 f :: Eq a => a -> (Maybe a -> [a]) -> Maybe a -> [a]接受三个参数，与 foldr 的预期不符.传入什么值？

最后 Nothing是为了什么？

Answer 1

你说

foldr takes three parameters

这是误导。 foldr的类型是

(a -> r -> r) -> r -> [a] -> r

哪里 r是可以被任何类型实例化的类型变量，包括函数类型。这就是这里发生的事情，并且确实通过第二个参数传递给 foldr 的事实给出了提示。 (应该匹配 r )是 const [] .

那个类型的 foldr这里使用的是以下内容:

foldr :: Eq a => (a -> (Maybe a -> [a]) -> Maybe a -> [a]) -> (Maybe a -> [a]) -> [a] -> Maybe a -> [a]
foldr ::         (a -> r                -> r             ) -> r                -> [a] -> r

一旦你知道 r实例化为 Maybe a -> [a] ，很明显 f此处有效地采用三个参数，而 foldr需要四个。

相同现象的一个更简单的例子是:

id id 2

在这里， id似乎有两个论点。外 id用于函数类型，内部 id与 Integer 一起使用争论。