Combining multiple Lists of arbitrary length

Question

I am looking for an approach to join multiple Lists in the following manner:

ListA a b c
ListB 1 2 3 4
ListC + # * § %
..
..
..

Resulting List: a 1 + b 2 # c 3 * 4 § %

In Words: The elements in sequential order, starting at first list combined into the resulting list. An arbitrary amount of input lists could be there varying in length.

I used multiple approaches with variants of zip, sliding iterators but none worked and especially took care of varying list lengths. There has to be an elegant way in scala ;)

Answer 1

val lists = List(ListA, ListB, ListC)

lists.flatMap(_.zipWithIndex).sortBy(_._2).map(_._1)

It's pretty self-explanatory. It just zips each value with its position on its respective list, sorts by index, then pulls the values back out.

Answer 2

Here's a recursive solution that's O(n). The accepted solution (using sort) is O(nlog(n)). Some testing I've done suggests the second solution using transpose is also O(nlog(n)) due to the implementation of transpose. The use of reverse below looks suspicious (since it's an O(n) operation itself) but convince yourself that it either can't be called too often or on too-large lists.

def intercalate[T](lists: List[List[T]]) : List[T] = {
    def intercalateHelper(newLists: List[List[T]], oldLists: List[List[T]], merged: List[T]): List[T] = {
      (newLists, oldLists) match {
        case (Nil, Nil) => merged
        case (Nil, zss) => intercalateHelper(zss.reverse, Nil, merged)
        case (Nil::xss, zss) => intercalateHelper(xss, zss, merged)
        case ( (y::ys)::xss, zss) => intercalateHelper(xss, ys::zss, y::merged)
      }
    }
    intercalateHelper(lists, List.empty, List.empty).reverse
  }

Answer 3

Here's how I would do it:

class ListTests extends FunSuite {
  test("The three lists from his example") {
    val l1 = List("a", "b", "c")
    val l2 = List(1, 2, 3, 4)
    val l3 = List("+", "#", "*", "§", "%")

    // All lists together
    val l = List(l1, l2, l3)

    // Max length of a list (to pad the shorter ones)
    val maxLen = l.map(_.size).max

    // Wrap the elements in Option and pad with None
    val padded = l.map { list => list.map(Some(_)) ++ Stream.continually(None).take(maxLen - list.size) }

    // Transpose 
    val trans = padded.transpose

    // Flatten the lists then flatten the options
    val result = trans.flatten.flatten

    // Viola 
    assert(List("a", 1, "+", "b", 2, "#", "c", 3, "*", 4, "§", "%") === result)
  }
}

Answer 4

Here's an imperative solution if efficiency is paramount:

def combine[T](xss: List[List[T]]): List[T] = {
  val b = List.newBuilder[T]
  var its = xss.map(_.iterator)
  while (!its.isEmpty) {
    its = its.filter(_.hasNext)
    its.foreach(b += _.next)
  }
  b.result
}

Answer 5

Here's a small recursive solution. Will show a streams approach later...

def flatList(lists: List[List[Any]]) = {
  def loop(output: List[Any], xss: List[List[Any]]): List[Any] = (xss collect { case x :: xs => x }) match {
    case Nil => output
    case heads => loop(output ::: heads, xss.collect({ case x :: xs => xs })) 
  }
  loop(List[Any](), lists)
}

And here is a simple streams approach which can cope with an arbitrary sequence of sequences, each of potentially infinite length.

def flatSeqs[A](ssa: Seq[Seq[A]]): Stream[A] = {
  def seqs(xss: Seq[Seq[A]]): Stream[Seq[A]] = xss collect { case xs if !xs.isEmpty => xs } match {
    case Nil => Stream.empty
    case heads => heads #:: seqs(xss collect { case xs if !xs.isEmpty => xs.tail })
  }
  seqs(ssa).flatten
}

I'm sure Luigi could shrink this to a one-liner ;) I have it about as small as I can get.

Answer 6

Here's something short but not exceedingly efficient:

def heads[A](xss: List[List[A]]) = xss.map(_.splitAt(1)).unzip
def interleave[A](xss: List[List[A]]) = Iterator.
  iterate(heads(xss)){ case (_, tails) => heads(tails) }.
  map(_._1.flatten).
  takeWhile(! _.isEmpty).
  flatten.toList