Interleave List of Lists in Haskell

I was wondering how could I write a function in Haskell that interleaves a list of lists into a single lists, for example, if I had a function called

interleavelists :: [[a]] -> [a]

it should be able to interleave the elements.

Example: [[1,2,3] [4,5,6] [7,8]] --> [1,4,7,2,5,8,3,6].

The lists can be both finite or infinite... Can I use foldr?

Solution

The quickest way to write it is to use transpose from Data.List.

import Data.List

interleavelists :: [[a]] -> [a]
interleavelists = concat . transpose

transpose picks the first element of each non-empty list of its argument, putting them into one list, and after that, transposes the list of tails of the argument's elements. concatenating the lists of transpose's result interleaves the lists as desired. It works if some element lists are infinite, but if the list of lists itself has infinitely many elements, it of course never gets past the list of heads. But handling that case is problematic anyway.

Using foldr to interleave the lists is not trivial. Suppose you had

interleavelists xss = foldr something zero xss

interleavelists [] should probably produce [], so that'd be the zero value. And

interleavelists [xs] = xs

seems natural, so

something xs [] = xs

But what if the second argument isn't []? Then you want to insert the elements of the first argument of something at varying distances into the second argument. But at which distances? If all lists have the same length, the distances for each list are constant, then you could pass the distance as a further parameter,

interleavelists = snd . foldr insertAtDistance (0, [])
  where
    insertAtDistance xs (d, ys) = (d+1, helper d xs ys)
    helper _ [] ws = ws
    helper k (b:bs) cs = b : us ++ helper k bs vs
      where
        (us,vs) = splitAt k cs

That isn't very pretty, and if the lists are not all the same length will produce what probably isn't the desired output. But if the lists all have the same length, it does the job.