3

我有这个简单的函数，它返回一个包含列表相邻元素的对列表。

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

我在尝试使用foldr. 我已经做了一些研究，但似乎没有任何提示。怎么做到呢？

4

3 回答 3

6

像这样的棘手折叠通常可以通过让折叠构建一个函数而不是尝试直接构建结果来解决。

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)]如果我们位于列表的开头。MaybeNothing

让我们仔细看看这里发生了什么：

  1. 如果我们同时拥有前一个元素和当前元素，我们将创建一对并将当前元素传递给递归的结果，递归的结果是生成列表尾部的函数。

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

  2. 如果没有前一个元素，我们只需将当前元素传递到下一步。

    f curr g Nothing     = g (Just curr)

  3. const []列表末尾的基本情况只是忽略了前一个元素。

通过这样做，结果与您的原始定义一样懒惰：

> adjacents (1 : 2 : 3 : 4 : undefined)
[(1,2),(2,3),(3,4)*** Exception: Prelude.undefined
于 2012-10-24T20:57:36.573 回答
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 就是一个例子它不是一个折叠。

于 2012-10-24T20:55:46.590 回答
2

您也可以尝试unfoldr代替foldr.

import Data.List
adjacents xs = unfoldr f xs where
  f (x:rest@(y:_)) = Just ((x,y), rest)
  f _ = Nothing
于 2012-10-25T07:39:16.497 回答