Haskell 99 个问题 #8：无法理解 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 参数一起使用。

Answer 2

正如 Jubobs 指出的那样，f 具有签名 f :: Eq a => a -> (Maybe a -> [a]) -> (Maybe a -> [a]) 在 foldr 签名的上下文中，这意味着 a 是 a， b 是 (Maybe a -> [a])。所以 foldr 确实构建了一个复杂的函数。

我们来看列表"aab"，一个很简单的输入。折叠展开为

(f 'a' (f 'a' (f 'b' (const []))))

将 Nothing 传递给该构造，您可以开始扩展它。最外层的调用有

x = 'a'
r = <the inner stuff>
a@(Just q) fails to match Nothing
_ matches Nothing

所以它的结果是'a' : r (Just 'a')。代入 r 我们得到：

'a' : f 'a' (f 'b' (const [])) (Just 'a')

然后对 f 的新的最外层调用有

x = 'a'
r = (f 'b' (const []))
a@(Just q) matches Just 'a'
guard 'a' == 'a' is true

所以 r a 分支被采用，即它只是转发到链中的下一个。函数的结果是r (Just 'a')，整个表达式的结果目前是'a' : r (Just 'a')。再次替换r：

'a' : f 'b' (const []) (Just 'a')

给f的新参数：

x = 'b'
r = const []
a@(Just q) matches Just 'a'
guard 'b' == 'a' is false
_ matches Just 'a'

我们再次选择第二个选项，因为守卫失败了。守卫基本上说，"if the previous character (q, a is Nothing if there was no previous character) is the same as the current (x), don't put it in the output, otherwise do".

所以函数结果是'b' : const [] (Just 'b')，我们目前看到的完整表达式结果是'a' : 'b' : const [] (Just 'b').

const 函数忽略它的第二个参数，returns 第一个。它看起来像这样：

const :: a -> b -> a
const x _ = x

在我们表达式的调用中，参数匹配如下：

x = []
_ = Just 'b'

因此结果是 []。整个表达式现在是 'a' : 'b' : []，或者在字符串语法中是 "ab"。重复的 'a' 已被删除。

如果你愿意，你可以在纸上玩这个游戏以获得更长的表达。

该解决方案基本上使用 foldr 来构建一个使用连续传递样式的函数，以便它可以携带状态。这是一种时髦的技术。通过折叠携带状态的一种更直观的方法是使折叠结果成为实际累加器和您要携带的状态的元组，然后在最后提取正确的结果。对于你的问题，这可能是这样的：

compress s = fst $ foldr f ([], Nothing) s
  where
    f cur (acc, (Just prev)) | cur == prev = (acc, (Just prev))
    f cur (acc, _) = (cur : acc, Just cur)

这应该也能正常工作。但是请注意，这 颠倒了 状态的顺序，即它向后遍历字符串。我不确定一个人与另一个人的表现或懒惰是什么。我觉得CPS的方案比较懒，但是我不确定。

Haskell 99 个问题 #8：无法理解 foldr

Haskell 99 questions #8: Can't understand foldr

haskell

Problem 8