如何使用foldr编写此功能？（涉及IT技术）

Question

我有一个简单的函数，它返回一个列表，其中包含一个列表中相邻元素的成对组合。

adjacents :: [a] -> [(a,a)]
adjacents (x:y:xs) = [(x,y)] ++ adjacents (y:xs)
adjacents (x:xs) = []

我正在尝试使用foldr编写相邻的内容，但遇到了问题。我进行了一些研究，但似乎没有任何线索。如何完成这个操作？

- acrespo

---

用压缩实现它，或者看看如何实现压缩（zip）。 - Marcin

"(x,y) : adjacents (y:xs)" 比 "[(x,y)] ++ adjacents (y:xs)" 更好，Marcin说的 zip 函数也很好用："zip xs (tail xs)" 代码清晰简洁。 - AndrewC

折叠（folds）和 map 以及 filter 是基本的递归方案 - 它们在每一步只查看一个元素。正如 AndrewC 所示，您必须将输入“加倍”才能在一步中看到两个元素。有一种递归方案可以避免将输入加倍 - 即参数orphism。Para 类似于折叠（fold），遍历输入，但还允许您在递归步骤中查看“其余的输入”。不幸的是，para 不在预加载模块或数据列表中。 - stephen tetley

Answer 1

像这样的复杂折叠通常可以通过将折叠逐步构建成一个函数来解决，而不是直接构建结果。

adjacents :: [a] -> [(a, a)]
adjacents xs = foldr f (const []) xs Nothing
  where f curr g (Just prev) = (prev, curr) : g (Just curr)
        f curr g Nothing     = g (Just curr)

在这里，我们的想法是让结果成为一个类型为Maybe a -> [(a, a)]的函数，其中Maybe包含前一个元素，或者如果我们在列表开头则为Nothing。

让我们更仔细地看一下这里发生了什么：

1. If we have both a previous and a current element, we make a pair and pass the current element to the result of the recursion, which is the function which will generate the tail of the list.

   f curr g (Just prev) = (prev, curr) : g (Just curr)
   

2. If there is no previous element, we just pass the current one to the next step.

   f curr g Nothing     = g (Just curr)
   

3. The base case const [] at the end of the list just ignores the previous element.

通过这种方式进行操作，结果与你最初定义的方式一样简单。

> adjacents (1 : 2 : 3 : 4 : undefined)
[(1,2),(2,3),(3,4)*** Exception: Prelude.undefined

- hammar

---

这确实很好地组合在一起，但我仍然认为 zip xs (tail xs) 更好。zip 是惰性的并且适用于无限列表，因此放弃它没有真正的好处。 - AndrewC

毫无疑问。然而，看看如何使用foldr编写这些函数仍然可以作为指导。例如，可以使用相同的技巧来实现zip函数。 - hammar

这让我意识到，在使用foldr实现foldl的标准技术不仅是一个巧妙的技巧，而且实际上是一个通用的有用概念。谢谢！ - David

Answer 2

我认为你的函数不适合用于折叠，因为它查看两个元素而不是一个。

我认为解决这个问题的最佳方案是：

adjacents [] = []
adjacents xs = zip xs (tail xs)

但如果你愿意，我们可以把它塞进一个可笑的折叠中。首先是一个辅助函数。

prependPair :: a -> [(a,a)] -> [(a,a)]
prependPair x [] = [(x,b)]             where b = error "I don't need this value."
prependPair x ((y,z):ys) = ((x,y):(y,z):ys)

adjacents' xs = init $ foldr prependPair [] xs

我觉得用错误值制作并丢弃最后一个元素有点作弊，但是嘿，我已经说过了，我认为foldr不是做这件事的好方法，所以我想这个hack就是它不是fold的一个例子。

- AndrewC

---

这种方法的问题在于，在prependPair中对第二个参数进行模式匹配，这要求必须将fold完全评估到最后才能生成任何结果，这也意味着它不再适用于无限列表。 - hammar

@hammar 是的，这是一个糟糕的解决方案，我已经说过了！ zip是正确的解决方案。适当时使用foldr是编写良好代码的好方法，但在这里并不适用。 - AndrewC

Answer 3

你可以尝试使用unfoldr代替foldr。

import Data.List
adjacents xs = unfoldr f xs where
  f (x:rest@(y:_)) = Just ((x,y), rest)
  f _ = Nothing

- Roman Cheplyaka