How can i interleave elements of 2 lists in scala

Question

I'd like to combine two Lists of arbitrary length in such a way that elements from the 2nd List are inserted after every n-th element into the 1st List. If the 1st List length 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)

I have this working using a foldLeft on a, but I'm wondering how the same logic could be accomplished using Scalaz?

Thanks for everyone's answers. They were all helpful to me !

Answer 1

Meet my apomorphism friend

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 interleave method can be implemented like this

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)

The good point is the computation ends when a or b are Nil unlike foldLeft. The bad news is interleave is no more tail recursive

Answer 2

This gets very simple with zipAll. Moreover, you are able to choose the amount of elements of 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 prefer, one-liner:

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

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

Answer 3

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 is "If the 1st List length is less than n, no insertion 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 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

It is short, but it is not the most efficient solution. If you call it with Lists for example, the append-operations (:+ and ++) are expensive (O(n)).

EDIT: I'm sorry. I notice now, that you want to have a solution with Scalaz. Nevertheless the answer may be useful therefore I won't delete it.