Inserting at position in List

Question

This insert function is taken from :

http://aperiodic.net/phil/scala/s-99/p21.scala

  def insertAt[A](e: A, n: Int, ls: List[A]): List[A] = ls.splitAt(n) match {
    case (pre, post) => pre ::: e :: post
  }

I want to insert an element at every second element of a List so I use :

 val sl = List("1", "2", "3", "4", "5")          //> sl  : List[String] = List(1, 2, 3, 4, 5)
  insertAt("'a", 2, insertAt("'a", 4, sl))        //> res0: List[String] = List(1, 2, 'a, 3, 4, 'a, 5)

This is a very basic implementation, I want to use one of the functional constructs. I think I need to use a foldLeft ?

Answer 1

Group the list into Lists of size 2, then combine those into lists separated by the separation character:

  val sl = List("1","2","3","4","5")              //> sl  : List[String] = List(1, 2, 3, 4, 5)
  val grouped = sl grouped(2) toList              //> grouped  : List[List[String]] = List(List(1, 2), List(3, 4), List(5))
  val separatedList = grouped flatMap (_ :+ "a")  //> separatedList  : <error> = List(1, 2, a, 3, 4, a, 5, a)

Edit Just saw that my solution has a trailing token that isn't in the question. To get rid of that do a length check:

  val separatedList2 = grouped flatMap (l => if(l.length == 2) l :+ "a" else l)
                        //> separatedList2  : <error> = List(1, 2, a, 3, 4, a, 5)

Answer 2

You could also use sliding:

val sl = List("1", "2", "3", "4", "5")   

def insertEvery(n:Int, el:String, sl:List[String]) =
   sl.sliding(2, 2).foldRight(List.empty[String])( (xs, acc) => if(xs.length == n)xs:::el::acc else xs:::acc)

insertEvery(2,"x",sl) // res1: List[String] = List(1, 2, x, 3, 4, x, 5)

Answer 3

Forget about insertAt, use pure foldLeft:

def insertAtEvery[A](e: A, n: Int, ls: List[A]): List[A] = 
  ls.foldLeft[(Int, List[A])]((0, List.empty)) {
    case ((pos, result), elem) =>
      ((pos + 1) % n, if (pos == n - 1) e :: elem :: result else elem :: result)
  }._2.reverse

Answer 4

Recursion and pattern matching are functional constructs. Insert the new elem by pattern matching on the output of splitAt then recurse with the remaining input. Seems easier to read but I'm not satisfied with the type signature for this one.

def insertEvery(xs: List[Any], n: Int, elem: String):List[Any] = xs.splitAt(n) match {
  case (xs, List()) => if(xs.size >= n) xs ++ elem else xs
  case (xs, ys) => xs ++ elem ++ insertEvery(ys, n, elem)
}

Sample runs.

scala> val xs = List("1","2","3","4","5")
xs: List[String] = List(1, 2, 3, 4, 5)

scala> insertEvery(xs, 1, "a")
res1: List[Any] = List(1, a, 2, a, 3, a, 4, a, 5, a)

scala> insertEvery(xs, 2, "a")
res2: List[Any] = List(1, 2, a, 3, 4, a, 5)

scala> insertEvery(xs, 3, "a")
res3: List[Any] = List(1, 2, 3, a, 4, 5)

Answer 5

An implementation using recursion:

Note n must smaller than the size of List, or else an Exception would be raised.

scala> def insertAt[A](e: A, n: Int, ls: List[A]): List[A] = n match {
     |   case 0 => e :: ls
     |   case _ => ls.head :: insertAt(e, n-1, ls.tail)
     | }
insertAt: [A](e: A, n: Int, ls: List[A])List[A]


scala> insertAt("'a", 2, List("1", "2", "3", "4"))
res0: List[String] = List(1, 2, 'a, 3, 4)

Answer 6

Consider indexing list positions with zipWithIndex, and so

sl.zipWithIndex.flatMap { case(v,i) => if (i % 2 == 0) List(v) else List(v,"a") }