How can I alternate items from 2 lists in scala

Question

I would like to combine two lists of arbitrary length so that the elements from the 2nd list are inserted after each nth element into the 1st list. If the length of the 1st list is less than n, no insertion results.

So having

val a = List(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) val b = List(101,102,103) val n = 3 

I want the resulting List to look like this:

 List(1,2,3,101,4,5,6,102,7,8,9,103,10,11,12,13,14,15) 

This works for me using foldLeft on a , but I wonder how can I make the same logic using Scalaz?

Thanks for answers. They were useful to me!

Answer 1

Meet my friend apomorphism

 def apo[A, B](v: B)(f: B => Option[(A, Either[B, List[A]])]): List[A] = f(v) match { case None => Nil case Some((a, Left(b))) => a :: apo(b)(f) case Some((a, Right(as))) => a :: as } 

Your rotation method can be implemented as follows

 def interleave[A](period: Int, substitutes: List[A], elems: List[A]): List[A] = apo((period, substitutes, elems)){ case (_, _, Nil) => None case (_, Nil, v :: vs) => Some((v, Right(vs))) case (0, x :: xs, vs) => Some((x, Left((period, xs, vs)))) case (n, xs, v :: vs) => Some((v, Left((n - 1, xs, vs)))) } 

This gives:

 scala> interleave(3, b, a) res1: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103 , 10, 11 , 12, 13, 14, 15) 

A good point is a calculation that ends when a or b is Nil, as opposed to foldLeft. The bad news is alternation, no more tail recursive

Answer 2

How about this:

  def process[A](xs: List[A], ys: List[A], n: Int): List[A] = if(xs.size <= n || ys.size == 0) xs else xs.take(n):::ys.head::process(xs.drop(n),ys.tail,n) 

---

 scala> process(a,b,n) res8: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) scala> val a = List(1,2,3,4,5,6,7,8,9,10,11) a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) scala> process(a,b,n) res9: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11) scala> val a = List(1,2,3,4,5,6,7,8,9) a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> process(a,b,n) res10: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9) scala> val a = List(1,2,3,4,5,6,7,8) a: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8) scala> process(a,b,n) res11: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8) 

---

Your request: “If the length of the 1st list is less than n, there are no insert results”, then my code should change to:

  def process[A](xs: List[A], ys: List[A], n: Int): List[A] = if(xs.size < n || ys.size == 0) xs else xs.take(n):::ys.head::process(xs.drop(n),ys.tail,n) 

Answer 3

It becomes very simple with zipAll . In addition, you can select the number of elements in the second array (in this case 1):

 val middle = b.grouped(1).toList val res = a.grouped(n).toList.zipAll(middle, Nil, Nil) res.filterNot(_._1.isEmpty).flatMap(x => x._1 ++ x._2) 

Or, if you want, single-line:

 a.grouped(n).toList.zipAll(b.map(List(_)), Nil, Nil).filterNot(_._1.isEmpty).flatMap(x => x._1 ++ x._2) 

You can also create an implicit class so that you can call a.interleave(b, 3) or with the optional thrid parameter a.interleave(b, 3, 1) .

Answer 4

What about:

 def interleave[A](xs: Seq[A], ys: Seq[A], n: Int): Seq[A] = { val iter = xs grouped n val coll = iter zip ys.iterator flatMap { case (xs, y) => if (xs.size == n) xs :+ y else xs } (coll ++ iter.flatten).toIndexedSeq } scala> interleave(a, b, n) res34: Seq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) scala> interleave(1 to 2, b, n) res35: Seq[Int] = Vector(1, 2) scala> interleave(1 to 6, b, n) res36: Seq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102) scala> interleave(1 to 7 b, n) res37: Seq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102, 7) scala> interleave(1 to 7, Nil, n) res38: Seq[Int] = Vector(1, 2, 3, 4, 5, 6, 7) scala> interleave(1 to 7, Nil, -3) java.lang.IllegalArgumentException: requirement failed: size=-3 and step=-3, but both must be positive 

In short, but this is not the most effective solution. If you call it with lists, for example, append ( :+ and ++ ) operations are expensive ( O(n) ).

EDIT: Sorry. Now I notice that you want to have a solution with Scalaz. However, the answer may be useful, so I will not delete it.

Answer 5

Without Scalaz and recursion.

 scala> a.grouped(n).zip(b.iterator.map{ Some(_) } ++ Iterator.continually(None)).flatMap{ case (as, e) => if (as.size == n) as ++ e else as }.toList res17: List[Int] = List(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) 

General way:

 def filled[T, A, That](a: A, b: Seq[T], n: Int)(implicit bf: CanBuildFrom[A, T, That], a2seq: A => Seq[T]): That = { val builder = bf() builder.sizeHint(a, a.length / n) builder ++= a.grouped(n).zip(b.iterator.map{ Some(_) } ++ Iterator.continually(None)).flatMap{ case (as, e) => if(as.size == n ) as ++ e else as } builder.result() } 

Using:

 scala> filled("abcdefghijklmnopqrstuvwxyz", "1234", 3) res0: String = abc1def2ghi3jkl4mnopqrstuvwxyz scala> filled(1 to 15, 101 to 103, 3) res1: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3, 101, 4, 5, 6, 102, 7, 8, 9, 103, 10, 11, 12, 13, 14, 15) scala> filled(1 to 3, 101 to 103, 3) res70: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2, 3, 101) scala> filled(1 to 2, 101 to 103, 3) res71: scala.collection.immutable.IndexedSeq[Int] = Vector(1, 2) 

Answer 6

I think this is the easiest solution.

 val bi = b.toIterator a.zipWithIndex.flatMap {case (el, i) => if (bi.hasNext && (i-1)%n == n-1) List(bi.next, el) else List(el) } 

Answer 7

here is the one you want:

 import scala.annotation.tailrec @tailrec final def interleave[A](base: Vector[A], a: List[A], b: List[A]): Vector[A] = a match { case elt :: aTail => interleave(base :+ elt, b, aTail) case _ => base ++ b } ... interleave(Vector.empty, a, b)