CODEWITHSUNDEEP
listhaskellfoldinterleave
user1950055
user1950055

Reputation: 157

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?

Upvotes: 10

Views: 7150

Answers (4)

Daniel Fischer
Daniel Fischer

Reputation: 183858

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.

Upvotes: 28

Will Ness
Will Ness

Reputation: 71065

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]

Upvotes: 5

zurgl
zurgl

Reputation: 1930

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]

Upvotes: 2

Chris
Chris

Reputation: 4231

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...

Upvotes: 5

Related Questions