How to make the list of lists into a single list by interleaving elements in haskell?

Question

how to take the input list of list and

string = [ [ 1, 2, 3, 4 ],
           [ 5, 6, 7, 8 ],
           [ 9, 10,11,12],
           [ 13,14,15,16] ]

output list like this format in haskell?

[ 1,
  2,5,
  3,6,9,
  4,7,10,13]

by using this format

rearrange     :: [[a]] -> [a]
rearrange xs  = ??

Answer 1

I misread the OP as wanting to exhaust all the elements in the 2D list. Here's a version of the function I originally used that has the correct behavior:

pyramidT :: [[a]] -> [[a]]
pyramidT [] = [[]]
pyramidT (row:rows) = zipWith (:) row ([]:(pyramidT rows)) 

rearrangeT :: [[a]] -> [a]
rearrangeT = concat . pyramidT

-- Ghci> pyramidT testData
-- [[1],[2,5],[3,6,9],[4,7,10,13]]

-- Ghci> rearrangeT testData
-- [1,2,5,3,6,9,4,7,10,13]

(previous post:)

Here's a recursive solution. I don't like that I don't have an appropriate higher-order function to replace the helper h with. The value h a b is meant to emulate zipWith (:) a b, but doing something appropriate whenever a and b are not the same length.

import Data.List

-- | Compute the list of diagonals
pyramid :: [[a]] -> [[a]]
pyramid [] = [[]]
pyramid (row:rows) = h row ([]:(pyramid rows)) where
  h [] rs = rs                      -- pad left input with "empty" elements
  h ls [] = map (:[]) ls            -- pad right input with []s
  h (l:ls) (r:rs) = (l:r):(h ls rs) -- act as zipWith would

-- | Compute the interleaving 
rearrange :: [[a]] -> [a]
rearrange = concat . pyramid

testData :: [[Int]
testData = [[1,2,3,4]
           ,[5,6,7,8]
           ,[9,10,11,12]
           ,[13,14,15,16]]

-- Ghci> pyramid testData
-- [[1],[2,5],[3,6,9],[4,7,10,13],[8,11,14],[12,15],[16]]

-- Ghci> rearrange testData
-- [1,2,5,3,6,9,4,7,10,13,8,11,14,12,15,16]

Answer 2

Observe that the task really tells you to think of constructing each line separately:

[ 1,
  2,5,
  3,6,9,
  4,7,10,13]

This is a good hint that you should consider building list of lists, and then concat them.

In order to construct a list of lists, it would be useful to go along the first list, and append it as the head to the other lists, until run out of the elements in the first list. So, it is a zipWith (:), folded somehow over the list of lists.

How would the last line get folded? Where do you get the lists to add the head to for the last line? How do you get the right number of lists? Well, if we can get a infinite supply of empty lists, the last line will zipWith that into singletons (lists with just one value).

Prelude> zipWith (:) [13..16] (repeat [])
[[13],[14],[15],[16]]

Now, the induction step: the penultimate line ([9..12]) must append a new head to the list of tails ([[13],[14],[15],[16]]), but in such a way, that the first element produces a singleton [9], and the second element 10 is appended to the first singleton [13] of the list of tails. So we must add a empty list to the head of tails:

Prelude> zipWith (:) [9..12] $ [] : zipWith (:) [13..16] (repeat [])
[[9],[10,13],[11,14],[12,15]]

It is pretty easy to see how to fold now

rearrange = concat . foldr (\hs ts -> zipWith (:) hs ([]:ts)) (repeat [])

Let's check:

Prelude> :t rearrange
rearrange :: [[a]] -> [a]
Prelude> rearrange [[1..4], [5..8], [9..12], [13..16]]
[1,2,5,3,6,9,4,7,10,13]

Answer 3

It looks like you want to restructure the elements by diagonals.

Here's some guidance...

Write the resulting list as a concatenation:

[a0] ++ [a1,b0] ++ [a2,b1,c0] ++ ...

and express each of the components in terms of a helper function:

[a0] ++ ...       = go 1 [ as, bs, cs, ds, ...]
[a1,b0] ++ ...    = go 2 [ tail as, bs, cs, ds, ...
[a2,b1,c0] ++ ... = go 3 [ tail (tail as), tail bs, cs, ds, ...]

where

as = [a0, a1, a2, ...]
bs = [b0, b1, b2, ...]
etc.

The recursion will look like:

go n [lists of lists] = some-list ++ go (n+1) [new lists of lists]

More specifically, go n [list1, list2, ...] will takes the heads of the first n lists into a list and concatenate it with

go (n+1) [list1', list2', ...]

where

listk' = tail listk      if k <= n
       = listk           otherwise

I.e., go n applies head to the first n-lists to create the next diagonal, and it applies tail to the first n lists to pass on to go (n+1).

http://lpaste.net/100055

Answer 4

This smacks of a nested for loop. We might accomplish this in an imperative language like this (in an unholy hybrid pseudocode)

int **xs; -- assuming an infinite list of infinite lists
int* output = [];
for (i = 0; ; i++)
  for (j = 0; j <= i; j++)
    output.append(xs[IDX1][IDX2])

This can easily be expressed as a list comprehension, which you attempted:

[(xs !! IDX1) !! IDX2 | i <- [0..], j <- [0..i]]

I'll leave the indexing to you; it isn't difficult to work out.

Note that this is for infinite lists. If this input lists are finite, you'll have to add some sort of bounds checking to make sure you don't exceed any indices.

Here's an example with infinite lists:

ys = map (\i -> [10*i,10*i+1..]) [0..]

This results in the lists:

[[0,1,2..],
 [10,11,12..],
 [20,21,22..],
 [30,31,32..],
 ...]

If we define

rearrange xs = [(xs !! IDX1) !! IDX2 | i <- [0..], j <- [0..i]]

then

take 10 $ rearrange ys 

outputs

[0,1,10,2,11,20,3,12,21,30]