Pairs of items from a list

Question

I want to convert [1,2,3,4] to [[1 2] [2 3] [3 4]] or [(1 2) (2 3) (3 4)] . In clojure I have (partition 2 1 [1,2,3,4]) . How can I do this in haskell? I suspect that there is such a function in the standard api, but I can not find it.

Answer 1

The standard trick for this is a zip list with its own tail :

 > let xs = [1,2,3,4] in zip xs (tail xs) [(1,2),(2,3),(3,4)] 

To understand why this works, align the list and its tail visually.

  xs = 1 : 2 : 3 : 4 : [] tail xs = 2 : 3 : 4 : [] 

and note that zip creates a tuple from each column.

There are two more subtle reasons why this always does the right thing:

• zip stops when an item ends in a list. This makes sense here, since we cannot have a “incomplete pair” at the end, and also ensure that we do not get pairs from the same list of elements.
• When xs empty, you can expect tail xs throw an exception. However, since zip first checks its first argument when it sees that it is an empty list, the second argument is never evaluated.

All of the above value is also valid for zipWith , so you can use the same method whenever you need to apply a function to neighboring elements.

For a general solution, such as the Clojure partition , there is nothing in the standard libraries. However, you can try something like this:

 partition' :: Int -> Int -> [a] -> [[a]] partition' size offset | size <= 0 = error "partition': size must be positive" | offset <= 0 = error "partition': offset must be positive" | otherwise = loop where loop :: [a] -> [[a]] loop xs = case splitAt size xs of -- If the second part is empty, we're at the end. But we might -- have gotten less than we asked for, hence the check. (ys, []) -> if length ys == size then [ys] else [] (ys, _ ) -> ys : loop (drop offset xs) 

Answer 2

Just to add another answer using a different approach:

For n = 2, you just need a zip list with your tail. For n = 3, you want to fasten the list with the tail and tail of the tail. This template goes on and on, so all we need to do is summarize it:

 partition n = sequence . take n . iterate tail 

But this only works for offset 1. To summarize the offsets, we just need to look at the modified list. It will always have the form:

 [[1..something],[2..something+1],..] 

So, all that remains to be done is to select each offset element, and everything should be fine. I shamelessly stole this version from @ertes from this question :

 everyNth :: Int -> [a] -> [a] everyNth n = map head . takeWhile (not . null) . iterate (drop n) 

Now the whole function becomes:

 partition size offset = everyNth offset . sequence . take size . iterate tail