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) = []
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)
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:
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)
If there is no previous element, we just pass the current one to the next step.
f curr g Nothing = g (Just curr)
The base case const [] at the end of the list just ignores the previous element.
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
zip xs (tail xs) is far better. zip is lazy and works on infinite lists, so there's no real benefit to abandoning it.
foldr. For example, zip can be implemented using the same technique.
foldl in terms of foldr is not just a neat trick, but actually a useful concept in general. Thanks!I don't think your function is a good fit for a fold, because it looks at two elements rather than one.
I think the best solution to the problem is
adjacents [] = []
adjacents xs = zip xs (tail xs)
But we can shoehorn it into a travesty of a fold if you like. First an auxilliary function.
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
I feel like I've cheated slightly by making and throwing away the last element with the error value, but hey ho, I already said I don't think foldr is a good way of doing this, so I guess this hack is an example of it not being a fold.
prependPair, this requires that the fold is evaluated all the way to the end before any result can be generated, which also means that it no longer works on infinite lists.zip is the right solution. foldr is a good function for writing good code when appropriate. Here it isn't.You can also try unfoldr instead of foldr.
import Data.List
adjacents xs = unfoldr f xs where
f (x:rest@(y:_)) = Just ((x,y), rest)
f _ = Nothing
(x,y) : adjacents (y:xs)is better than[(x,y)] ++ adjacents (y:xs), and Marcin is right that zip is good:zip xs (tail xs)is clear and clean.mapandfilter) are elementary recursion schemes - they look at only one element at each step. As AndrewC shows, you have to "double" the input in order to see two elements at a step. There is a recursion scheme you can use to avoid doubling the input - paramorphism.Paratraverses the input like a fold but also lets you look at the "rest of input" at the recursive step. Unfortunatelyparaisn't in the Prelude or Data.List.