12

I have a chained list like

["root", "foo", "bar", "blah"]

And I'd like to convert it to a list of tuples, using adjacent pairs. Like so

[("root", "foo"), ("foo", "bar"), ("bar", "blah")]

At the moment, I'm using this to do it:

 zipAdj x = tail (zip ("":x) (x++[""]))

However, I don't really like this method. Can anyone think of a better way? If it's glaringly obvious I apologise, I'm fairly new to Haskell.

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
Alex
  • 285
  • 2
  • 8
  • 3
    Why not just use `zipAdj x = zip x $ tail x`? Am I missing something? Or even `zip <*> tail` if you like silly pointfree code. – C. A. McCann Dec 22 '10 at 03:15
  • If you submit an answer, I'll accept it. If you care about such things... – Alex Dec 22 '10 at 03:35
  • Well I'm not exactly lacking for accepted answers but I guess it's the "proper" way to do it anyway, if that really is all you needed. – C. A. McCann Dec 22 '10 at 03:45
  • What you ask for are "pairwise combinations". With that name you'll find tons of implementations in the web (though the zip + tail looks fine) – tokland Dec 23 '10 at 17:26
  • Note the "proper" way in the accepted answer doesn't produce exactly the same output as the OP's original `zipAdj`. The OP's code outputs an extra pair `("blah", "")`, guaranteeing that the output has the same length as the input (although by adding an arbitrary "null" element). `zip` + `tail` reduces the list length by 1, and maps both empty lists and singleton lists to `[]`. Given that the OP's desired output example doesn't have this extra pair, I doubt that's what he wanted, but it does show that there are potential reasons to want a different definition than the zip + tail version. – Ben Mar 27 '15 at 04:09
  • @Ben, `tail [] = undefined`, so a singleton and an empty list do not do the same things. – dfeuer Sep 16 '15 at 04:55
  • 1
    @dfeuer But `zip [] undefined = []`, so `zip Adj x = zip x $ tail x` does indeed do the same thing to singletons and empty lists. – Ben Sep 16 '15 at 06:01

3 Answers3

24

Okay, here's the comment as an answer:

Just zipAdj x = zip x $ tail x will suffice. zip stops upon reaching the end of the shorter of the two lists, so this simply pairs each item in the list with its successor, which seems to be all you want.

And for the sake of explaining the pointless version: zip <*> tail uses the Applicative instance for "functions from some type", which basically amounts to a lightweight inline Reader monad--in this case the list is the "environment" for the Reader. Usually this just obfuscates matters but in this case it almost makes it clearer, assuming you know to read (<*>) here as "apply both of these to a single argument, then apply the first to the second".

C. A. McCann
  • 76,893
  • 19
  • 209
  • 302
8

One possible solution:

pairs [] = []
pairs (x:[]) = []
pairs (x:y:zs) = (x, y) : pairs (y : zs)

Definitely not as small as yours, and can probably be optimized quite a bit.

Joshua Rodgers
  • 5,317
  • 2
  • 31
  • 29
0

It's possible to generalize the zipAdj in the question to work with arbitrary Traversable containers. Here's how we'd do it if we wanted the extra element on the front end:

import Data.Traversable

pairDown :: Traversable t => a -> t a -> t (a, a)
pairDown x = snd . mapAccumL (\old new -> (new, (old,new))) x

*Pairing> take 10 $ pairDown 0 [1..]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]
*Pairing> pairDown 0 [1..10]
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]

To stick the extra element on the end, we can use mapAccumR:

import Data.Traversable

pairUp :: Traversable t => t a -> a -> t (a, a)
pairUp xs x = snd $ mapAccumR (\old new -> (new, (new,old))) x xs

This effectively traverses the container backwards.

*Pairing> pairUp [0..10] 11
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10),(10,11)]
*Pairing> take 10 $ pairUp [0..] undefined
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]

It's impossible to generalize the apparently-desired function in quite this fashion, but it's possible to generalize it a bit differently:

import Data.Foldable
import Prelude hiding (foldr)

pairAcross :: Foldable f => f a -> [(a,a)]
pairAcross xs = foldr go (const []) xs Nothing
  where
    go next r Nothing = r (Just next)
    go next r (Just prev) = (prev, next) : r (Just next)

This gives

*Pairing> pairAcross [1..10]
[(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]
dfeuer
  • 48,079
  • 5
  • 63
  • 167