如何使用foldr编写此函数？ [英] How can this function be written using foldr?

问题描述

I have this simple function which returns a list of pairs with the adjacents elements of a list.

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

我在使用 foldr 。我做了一些研究，但似乎没有给我提示。如何做到这一点？

I'm having problems trying to write adjacents using foldr. I've done some research but nothing seems to give me a hint. How can it be done?

推荐答案

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

Tricky folds like this one can often be solved by having the fold build up a function rather than try to build the result directly.

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)

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

Here, the idea is to let the result be a function of type Maybe a -> [(a, a)] where the Maybe contains the previous element, or Nothing if we're at the beginning of the list.

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

Let's take a closer look at what's going on here:

1. 如果我们同时拥有一个前一个元素和一个当前元素，我们创建一个pair并将当前元素传递给递归的结果，这是将生成（只是上一次）=（prev，curr）：g（只是curr）
   <$ p
   $ b

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)

如果没有以前的元素，我们只传递当前元素到下一步。 b
$ b

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

f curr g Nothing     = g (Just curr)

列表末尾的基本情况 const [] 会忽略前一个元素。

通过这样做，结果与原定义一样懒：

By doing it this way, the result is as lazy as your original definition:

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

这篇关于如何使用foldr编写此函数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！