CODEWITHSUNDEEP
listhaskell
Ron Wiese
Ron Wiese

Reputation: 193

Haskell: List manipulation

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]

Upvotes: 2

Views: 1024

Answers (4)

Micha Wiedenmann
Micha Wiedenmann

Reputation: 20873

Two more, the second is using unfoldr:

pair xs = take (length xs `div` 2) $ zip xs (reverse xs)
-- Note: uses tuples instead of lists

import Data.List
pairs2 = unfoldr (\xs ->
    if length xs < 2 
    then Nothing
    else Just ([head xs, last xs], init.tail $ xs))

xs = [2,3,4,7,6]
pair xs   -- [(2,6),(3,7)]
pair2 xs  -- [[2,6],[3,7]]

Upvotes: 1

oisdk
oisdk

Reputation: 10091

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.

Upvotes: 7

Steven Fontanella
Steven Fontanella

Reputation: 794

Note that we have to use drop 1 instead of tail here to avoid errors for odd-length lists.

g2 :: [a] -> [[a]]
g2 [] = []
g2 xs = [first xs] ++ (g2 . drop 1 $ init xs)
    where first (x:[]) = [x]
          first xs = [head xs, last xs]

Upvotes: 2

Abe Voelker
Abe Voelker

Reputation: 31622

Here's one using transpose

import Data.List

g2 xs =
  transpose [take (x + y) xs, take x (reverse xs)]
    where (x, y) = (length xs) `divMod` 2

Upvotes: 4

Related Questions