### Scala, Merging Lists in an interspersed way.

Here is what I am trying to do...
Take several Lists and combine them in an interspersed way.

For example giving the following two lists..

 val a = List(1, 1)     val b = List(2, 2, 2, 2)

If I merged them together in an interspersed way I would be roughly equivalent this list.

 val ab = List(2, 1, 2,  2, 1, 2)

How can I do this in Scala?

I am going to start playing around and see what it takes to get this accomplished and hopefully learn something along the way.

## zip map and flatten

You can use zip to stitch together two different Lists.   The lists do not need to be the same size.  The resulting new List will only contains X elements (as Tuples) where X is the length of the shorter List.

For example.

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zip(b))

This will output

 List((a,1), (b,2))

You can see the 3,4 have been cut off from the b List.
Suppose this is what I want.  How do I flatten the list?  So that I have List(a, 1, b, 2) ?

You can use the flatten function!  But the flatten function needs the elements within the list to be traversable.  What I have now is just a List of Tuples (which are not traversable).  I need to use map to convert the tuples into something traversable like a List.

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zip(b))     println(a.zip(b).map(tup => List(tup._1, tup._2)))

This outputs

 List((a,1), (b,2)) List(List(a, 1), List(b, 2))

This is now a List of Lists (which are traversable!)

Now flatten it

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zip(b))     println(a.zip(b).map(tup => List(tup._1, tup._2)))     println(a.zip(b).map(tup => List(tup._1, tup._2)).flatten)

Here is the output of this

 List((a,1), (b,2)) List(List(a, 1), List(b, 2)) List(a, 1, b, 2)

If both your lists were the same length this would work!  You would get one list interspersed within the other list.

But for in my particular case I am going to have Lists of different lengths so this will not work for me.

## zipAll map and flatten

You can use zipAll to stitch together two different Lists.  The list do not need to be the same size.  The resulting new List will contain X elements (as Tuples) where X is the length of the longer List.

For example.

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zipAll(b, None, None))

This will output

 List((a,1), (b,2), (None,3), (None,4))

What is up with None, None?   Well those locations are used to fill in the blanks if you want to do that (I do not).

For example

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zipAll(b, 3, 8))

This will output

 List((a,1), (b,2), (3,3), (3,4))

If a is shorter than b then fill in empty a slots with a 3.  If b is shorter than a then fill in empty slots with an 8.

I don't want to create additional values for my final list so I will leave mine as None.

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zipAll(b, None, None))     println(a.zipAll(b, None, None).map(                                 tup => List(tup._1, tup._2)))

This outputs.

 List(List(a, 1), List(b, 2), List(None, 3), List(None, 4))

Now to flatten it

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zipAll(b, None, None))     println(a.zipAll(b, None, None).map(                                tup => List(tup._1, tup._2)))     println(a.zipAll(b, None, None).map(                                tup => List(tup._1, tup._2)).flatten)

This gives me…

 List((a,1), (b,2), (None,3), (None,4)) List(List(a, 1), List(b, 2), List(None, 3), List(None, 4)) List(a, 1, b, 2, None, 3, None, 4)

This list has one problem it has None values I do not want.

Removing the None

 val a = List("a", "b")     val b = List(1, 2, 3, 4)     println(a.zipAll(b, None, None))     println(a.zipAll(b, None, None).map(                                   tup => List(tup._1, tup._2)))     println(a.zipAll(b, None, None).map(                                   tup => List(tup._1, tup._2)).flatten)     println(a.zipAll(b, None, None).map(              tup => List(tup._1, tup._2)).flatten.filter(_!=None))

Outputs

 List((a,1), (b,2), (None,3), (None,4)) List(List(a, 1), List(b, 2), List(None, 3), List(None, 4)) List(a, 1, b, 2, None, 3, None, 4) List(a, 1, b, 2, 3, 4)

But…. I think there is a better… ?  More proper way to do this using Options.

Running this code

 val a:List[Option[String]] = List(Some("a"), Some("b"))     val b:List[Option[Int]] = List(Some(1), Some(2), Some(3), Some(4))     println(a.zipAll(b, None, None))     println(a.zipAll(b, None, None).map(                                tup => List(tup._1, tup._2)))     println(a.zipAll(b, None, None).map(                                tup => List(tup._1, tup._2)).flatten)     println(a.zipAll(b, None, None).map(                        tup => List(tup._1, tup._2)).flatten.flatten)

Outputs

 List((Some(a),Some(1)), (Some(b),Some(2)), (None,Some(3)), (None,Some(4))) List(List(Some(a), Some(1)), List(Some(b), Some(2)), List(None, Some(3)), List(None, Some(4))) List(Some(a), Some(1), Some(b), Some(2), None, Some(3), None, Some(4)) List(a, 1, b, 2, 3, 4)

(I still need to fiddle with options more to understand them better… maybe for now I will let them be)

Anyway… back to my list I have

 List(a, 1, b, 2, 3, 4)

Which is not what I want…. I want

 List(1, a, 2, 3, b, 4)
(or something close to this)

## Grouped

Maybe the grouped function may come to the rescue.
What does grouped do?

Given this code.

 val a = List("a", "b")     val b = List(1, 2, 3, 4, 5, 6, 7)     println(a.grouped(3).toList)     println(b.grouped(3).toList)

This will output

 List(List(a, b)) List(List(1, 2, 3), List(4, 5, 6), List(7))

So what does grouped do?   It takes the List and splits it into a List of Lists where each contained List contains at most the number of elements you asked to group by.  In this case I said three, so it goes down the list grabs the first three and makes a list, then goes down the list grabs the next three and makes another list…. And so on.  If there are not enough remaining items in the List the last element contains a List of whatever remains.

I think I can use it to my advantage

Given this code.

 val a = List("a", "b")     val b = List(1, 2, 3, 4, 5, 6, 7)     val split = {       if (a.length < b.length) math.ceil(b.length.toDouble / a.length).toInt       else math.ceil(b.length.toDouble / a.length).toInt     }     println(split)     println(a.grouped(split).toList)     println(b.grouped(split).toList)

This will output

 4 List(List(a, b)) List(List(1, 2, 3, 4), List(5, 6, 7))

That will split my larger list into the exact number of elements in my smaller list.  I think I can use this to my advantage and somehow zip these and weasel the values of the shorter List into the larger one.

Given this code.

 val a = List("a", "b")     val b = List(1, 2, 3, 4, 5, 6, 7)     val split = {       if (a.length < b.length) math.ceil(b.length.toDouble / a.length).toInt       else math.ceil(b.length.toDouble / a.length).toInt     }     println(split)     println(a.grouped(split).toList)     println(b.grouped(split).toList)     println(b.grouped(split).toList.zip(a))     println(b.grouped(split).toList.zip(a).map(                                    tup => tup._2 :: tup._1))     //Put the element from the smaller list at the head     println(b.grouped(split).toList.zip(a).map(                                    tup => tup._2 :: tup._1).flatten)     //Put the element from the smaller list at the end     println(b.grouped(split).toList.zip(a).map(                                    tup => tup._1 :+ tup._2).flatten)     //Put the element from the smaller list in the middle of the     //larger segment     println(b.grouped(split).toList.zip(a).map{tup =>       val n = tup._1.length/2       (tup._1.take(n) :+ tup._2) ::: tup._1.drop(n)     }.flatten)     //Put the element from the smaller list randomly within the     //larger segment     println(b.grouped(split).toList.zip(a).map{tup =>       val n = Random.nextInt(tup._1.length)       (tup._1.take(n) :+ tup._2) ::: tup._1.drop(n)     }.flatten)

This will output

 4 List(List(a, b)) List(List(1, 2, 3, 4), List(5, 6, 7)) List((List(1, 2, 3, 4),a), (List(5, 6, 7),b)) List(List(a, 1, 2, 3, 4), List(b, 5, 6, 7)) List(a, 1, 2, 3, 4, b, 5, 6, 7) List(1, 2, 3, 4, a, 5, 6, 7, b) List(1, 2, a, 3, 4, 5, b, 6, 7) List(1, a, 2, 3, 4, 5, b, 6, 7)

(well the last one is random so it could be different)

If I change my Lists to the original ones I had…

 val a = List(1, 1)     val b = List(2, 2, 2, 2)     val split = {       if (a.length < b.length) math.ceil(b.length.toDouble / a.length).toInt       else math.ceil(b.length.toDouble / a.length).toInt     }     println(split)     println(a.grouped(split).toList)     println(b.grouped(split).toList)     println(b.grouped(split).toList.zip(a))     println(b.grouped(split).toList.zip(a).map(                                    tup => tup._2 :: tup._1))     //Put the element from the smaller list at the head     println(b.grouped(split).toList.zip(a).map(                                    tup => tup._2 :: tup._1).flatten)     //Put the element from the smaller list at the end     println(b.grouped(split).toList.zip(a).map(                                    tup => tup._1 :+ tup._2).flatten)     //Put the element from the smaller list in the middle of the     //larger segment     println(b.grouped(split).toList.zip(a).map{tup =>       val n = tup._1.length/2       (tup._1.take(n) :+ tup._2) ::: tup._1.drop(n)     }.flatten)     //Put the element from the smaller list randomly within the     //larger segment     println(b.grouped(split).toList.zip(a).map{tup =>       val n = Random.nextInt(tup._1.length)       (tup._1.take(n) :+ tup._2) ::: tup._1.drop(n)     }.flatten)

The output is

 2 List(List(1, 1)) List(List(2, 2), List(2, 2)) List((List(2, 2),1), (List(2, 2),1)) List(List(1, 2, 2), List(1, 2, 2)) List(1, 2, 2, 1, 2, 2) List(2, 2, 1, 2, 2, 1) List(2, 1, 2, 2, 1, 2) List(2, 1, 2, 1, 2, 2)

The code that splits it in the middle gives me exactly what I want.   Or ... what I wanted originally.   But do I really need this "pretty" looking split?

Putting the smaller element as the new head of the list is the fastest of all the options (Given that this is a List).

# Got something!

After a bunch of fiddling here is what I came up with.

 def mergeList[T](a:List[T], b:List[T]):List[T] = (a, b) match {     case (Nil, Nil)                       => Nil     case (Nil, b)                         => b     case (a, Nil)                         => a     case (a, b)  if(a.length > b.length)  => mergeList(b, a)     case (a, b)                           => {       val split = math.ceil(b.length.toDouble / a.length).toInt       b.grouped(split).toList.zip(a).map(tup => tup._2 :: tup._1).flatten     }   }

Now let me use it

 val a = List(List.fill(2)(2), List.fill(4)(4), List.fill(3)(3), List.fill(7)(7), List.fill(5)(5), Nil)    println(a)    println(a.foldLeft(List.empty[Int])(mergeList(_,_)))

Here is the output

 List(List(2, 2), List(4, 4, 4, 4), List(3, 3, 3), List(7, 7, 7, 7, 7, 7, 7), List(5, 5, 5, 5, 5), List()) List(5, 7, 3, 2, 5, 7, 4, 3, 5, 7, 4, 2, 5, 7, 3, 4, 5, 7, 4)

Looks like it worked!  (but it has a bug… read on)

# Other solution

Looking around I found a few other solutions.  One I found here http://stackoverflow.com/questions/19810938/scala-combine-two-lists-in-an-alternating-fashion 

 def intersperse[A](a : List[A], b : List[A]): List[A] = a match {   case first :: rest => first :: intersperse(b, rest)   case _             => b }

And trying to use it

 val a = List(List.fill(2)(2), List.fill(4)(4), List.fill(3)(3), List.fill(7)(7), List.fill(5)(5), Nil)    println(a)    println(a.foldLeft(List.empty[Int])(mergeList(_,_)))    println(a.foldLeft(List.empty[Int])(intersperse(_,_)))

Returns

 List(List(2, 2), List(4, 4, 4, 4), List(3, 3, 3), List(7, 7, 7, 7, 7, 7, 7), List(5, 5, 5, 5, 5), List()) List(5, 7, 3, 2, 5, 7, 4, 3, 5, 7, 4, 2, 5, 7, 3, 4, 5, 7, 4) List(2, 5, 7, 5, 3, 5, 7, 5, 4, 5, 7, 3, 7, 2, 7, 3, 7, 4, 7, 4, 4)

… Wait their answer has 2 more elements in the List.

… dang it they are right I have a bug in my code

The way I have it there can be a problem.  For example if I have a list of 9 elements and a List of 7 elements.   I can't use grouped to turn the 9 element array into a 7 element array.  So my idea as is will not work.

# Debugging code

Here is my fixed code

 def mergeList[T](a:List[T], b:List[T]):List[T] = (a, b) match {     case (Nil, Nil)                       => Nil     case (Nil, b)                         => b     case (a, Nil)                         => a     case (a, b)  if(a.length > b.length)  => mergeList(b, a)     case (a, b)                           => {       val grp = math.ceil(b.length.toDouble / a.length).toInt       b.grouped(grp).toList.zipAll(a, List.empty[T], b.head).map(                    tup => tup._2 :: tup._1).flatten     }   }

And using it (this time with a test to confirm it is correct)

 val a = List(List.fill(2)(2), List.fill(4)(4), List.fill(3)(3),                                    List.fill(7)(7), List.fill(5)(5), Nil)    println(a)    println(a.foldLeft(List.empty[Int])(mergeList(_,_)))    println(a.foldLeft(List.empty[Int])(intersperse(_,_)))    println((a.flatten.sorted ==            a.foldLeft(List.empty[Int])(mergeList(_,_)).sorted))
And here is the output.

 List(List(2, 2), List(4, 4, 4, 4), List(3, 3, 3), List(7, 7, 7, 7, 7, 7, 7), List(5, 5, 5, 5, 5), List()) List(5, 7, 3, 2, 7, 5, 4, 3, 7, 4, 5, 2, 7, 3, 4, 5, 7, 4, 7, 7, 5) List(2, 5, 7, 5, 3, 5, 7, 5, 4, 5, 7, 3, 7, 2, 7, 3, 7, 4, 7, 4, 4) true

That seems to work well enough.   I am guessing that the interspace function is much faster than what I came up with… at any rate it is much simpler.

One odd thing about my updated code.

 val grp = math.ceil(b.length.toDouble / a.length).toInt       b.grouped(grp).toList.zipAll(a, List.empty[T], b.head).map(                    tup => tup._2 :: tup._1).flatten

In the zipAll from what I understand you need to have List.Empty[T] to help give the compiler a hint at what type you want.   But I have an issue… my second List only has Ints.   I tried None[T] but that did not work to give it a hint.   So I used b.head, knowing it will never replaced a value as the a list is always longer and will never use the b.head (just need it to get it to compile)

I still have a long way to go in scala, but fiddling with this problem helped me learn a lot.

References

        Stream vs Views vs Iterators    http://stackoverflow.com/questions/5159000/stream-vs-views-vs-iterators
Accessed 02/2016
        Why iterator doesn't have any reset method?   http://stackoverflow.com/questions/7689261/why-iterator-doesnt-have-any-reset-method
Accessed 06/2014
        Scala - Combine two lists in an alternating fashion      http://stackoverflow.com/questions/19810938/scala-combine-two-lists-in-an-alternating-fashion
Accessed 06/2014