3

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?

acrespo
  • 1,134
  • 1
  • 10
  • 33
  • 3
    write it with zip, or look at how zip is implemented. – Marcin Oct 24 '12 at 20:20
  • 7
    `(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. – AndrewC Oct 24 '12 at 20:25
  • 4
    Folds (and `map` and `filter`) 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. `Para` traverses the input like a fold but also lets you look at the "rest of input" at the recursive step. Unfortunately `para` isn't in the Prelude or Data.List. – stephen tetley Oct 24 '12 at 20:42

3 Answers3

6

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:

  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.

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
hammar
  • 138,522
  • 17
  • 304
  • 385
  • This is very well put together indeed, but I still think `zip xs (tail xs)` is far better. `zip` is lazy and works on infinite lists, so there's no real benefit to abandoning it. – AndrewC Oct 24 '12 at 21:08
  • 3
    @AndrewC: Unquestionably. However, it can still be instructional to see how these functions can be written in terms of `foldr`. For example, `zip` can be implemented using the same technique. – hammar Oct 24 '12 at 21:15
  • 1
    This made me realize that the standard implementation technique of `foldl` in terms of `foldr` is not just a neat trick, but actually a useful concept in general. Thanks! – David Oct 25 '12 at 23:24
2

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.

AndrewC
  • 32,300
  • 7
  • 79
  • 115
  • The problem with this approach is that by pattern matching on the second argument in `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. – hammar Oct 24 '12 at 21:05
  • @hammar Yes, it's a bad solution, I already said so! `zip` is the right solution. `foldr` is a good function for writing good code when appropriate. Here it isn't. – AndrewC Oct 24 '12 at 21:06
2

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
Roman Cheplyaka
  • 37,738
  • 7
  • 72
  • 121