Haskell: List manipulation

Question

I want to write a function which takes a input list and manipulates it in the following way:

Step 1: Take the first element of the list and the last element of the list and put it together in a sublist.

Step 2: Take the second element of the list and the second last element of the list and put it together in the next sublist.

Step 3: Take the third element of the list and the third last element of the list and put it together in next sublist.

Continue this according to the same scheme (for a list of n elements)...

If the number of elements of the input list is odd the n/2 element of the input list will be added as last sublist of the output list.

Example:

[1,2,3,4,5,6,7]

-- should be transformed to

[[1,7],[2,6],[3,5],[4]]

I already wrote a function which takes every 2 elements of a list and puts it together in sublists and I am wondering if this code might help me with my problem above:

g2 :: [a] -> [[a]]
g2 [] = []
g2 (x1:x2:xs) = [x1,x2]: g2 xs
g2 xs = [xs]

Answer 1

Here's one that does it in one pass:

pairs :: [a] -> [[a]]
pairs xs = fst (go xs xs) where
  go (x:xs) (_:_:ys) = f x (go xs ys)
  go (x:xs) [_]      = ([[x]],xs)
  go xs     []       = ([],xs)

  f x (xs,y:ys) = ([x,y]:xs,ys)

How does it work? Let's look at the first two arguments of go first, and in particular this line:

  go (x:xs) (_:_:ys) = f x (go xs ys)

Those two arguments are both from the same list (xs), but we take 2 items off of one, and only one off of the other. Why? So we know when we hit the halfway point. Look at this function for comparison:

halfway xs = go xs xs
  where
    go (_:xs) (_:_:ys) = go xs ys
    go xs _ = xs

>>> halfway [1..6]
[4,5,6]

Now, once we get to the halfway point we'll need to "zip" it with the other list. But it needs to be in reverse! How do we do this? A handy way to reverse any function in one pass is to first write it as a fold. Here's zip written as a fold:

zip = foldr (\x k (y:ys) -> (x,y) : k ys) (const [])

To "reverse" it, you just apply is as a foldl rather than as a foldr (you also have to flip the closure).

For our uses, we basically build up the base as we go (in the form of k). So no our function looks like this:

pairs :: [a] -> [[a]]
pairs xs = go xs xs (const []) where
  go (y:ys) (_:_:zs) k = go ys zs (f y k)
  go (y:ys) [_]      k = [y] : k ys
  go ys     []       k = k ys

  f x k (y:ys) = [x,y] : k ys -- same `f` as from `zip`

There's still one problem: the list is returned in the wrong order. To fix this, we replace the list with a difference list, and swap the order of the appends.

Finally, we un-CPS the function, and we get the above.