如何使用foldr编写此函数？

Question

我有这个简单的函数,它返回列表的邻接元素的对列表.

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

我在尝试编写邻接时遇到问题foldr.我做了一些研究,但似乎没有什么能给我一个暗示.怎么做到呢？

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. 如果我们同时有一个previous元素和一个current元素,我们建立一个对并将当前元素传递给递归的结果,该函数将生成列表的尾部.

   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