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.

Adding a map

    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

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.

                                   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

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 = Random.nextInt(tup._1.length)
      (tup._1.take(n) :+ tup._2) ::: tup._1.drop(n)
    }.flatten)

The output is

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)

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

[1] Stream vs Views vs Iterators http://stackoverflow.com/questions/5159000/stream-vs-views-vs-iterators

Accessed 02/2016

[2] Why iterator doesn't have any reset method? http://stackoverflow.com/questions/7689261/why-iterator-doesnt-have-any-reset-method

Accessed 06/2014

[3] Scala - Combine two lists in an alternating fashion http://stackoverflow.com/questions/19810938/scala-combine-two-lists-in-an-alternating-fashion

Accessed 06/2014

Scala, Merging Lists in an interspersed way.

Posted on Sunday, February 14, 2016

zip map and flatten

zipAll map and flatten

Grouped

Got something!

Other solution

Debugging code

No comments:

Post a Comment