Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 797
user1950055 Avatar asked Jan 06 '13 20:01

user1950055


4 Answers

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.

like image 177
Daniel Fischer Avatar answered Nov 11 '22 19:11

Daniel Fischer


Simple recursive version:

inter :: [[a]] -> [a]
inter [] = []
inter xs = inter2 (filter (\x -> not (null x)) xs)
   where inter2 xs = map head xs ++ inter (map tail xs)

Now, about foldr...

like image 21
Chris Avatar answered Nov 11 '22 19:11

Chris


The "standard" (or perhaps, famous) way of interleaving lists, back in the jolly days of SICP (and later, Reasoned Scheme), was

infixr 5 ++/

[]     ++/ ys = ys
(x:xs) ++/ ys = x:(ys ++/ xs)

It can be used with foldr,

*Main> foldr (++/) [] [[1,2,3],[4,5,6],[7,8]]
[1,4,2,7,3,5,8,6]

This obviously does not produce the result in the order you wanted, but it will OTOH work OK when the input list of lists is infinite. I don't think there is a way to satisfy both requirements at the same time, as we have no way of knowing whether an input list will be infinite or not.

The above results are what the function insertAtDistance from Daniel's answer would produce, if modified to always insert at a distance of 1, instead of d+1:

insertAtDistance xs (d, ys) = (1, helper d xs ys)

When defined with d+1 it produces "flat" interleaving, whereas foldr (++/) [] produces skewed interleaving:

*Main> take 20 $ foldr (++/) [] [cycle[i] | i<-[1..]]
[1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3]
like image 4
Will Ness Avatar answered Nov 11 '22 18:11

Will Ness


we could do what you want

testList = [[1,2,3],[4,5,6],[7,8]]

interleave l = foldr' (concat [map (\x -> f x idx) l | idx <- [0..]])  
    where
        f x n = if (length(x)<=n) then Nothing else Just (x !! n)
        foldr' (x:xs) = case x of 
                         Nothing -> []
                         Just a  -> (:) a (foldr' xs)   

As required interleave [[1,2,3] [4,5,6] [7,8]] => [1, 4, 7, 2, 5, 8, 3, 6]

like image 2
zurgl Avatar answered Nov 11 '22 17:11

zurgl