3.6

Not everything works out so nicely. Implement a function, init, that returns a List consisting of all but the last element of a List. So, given List(1,2,3,4), init will return List(1,2,3). Why can’t this function be implemented in constant time like tail?

def init[A](l: List[A]): List[A]

Solution

def init[A](l: List[A]): List[A] = {
  init(l, Nil)
}

private def init[A](in: List[A], out: List[A]): List[A] = in match {
  case Nil => Nil
  case Cons(last, Nil) => out
  case Cons(head, tail) => init(tail, append(out, List(head)))
}

// Note: It makes use of append function provided in code
def append[A](a1: List[A], a2: List[A]): List[A] =
  a1 match {
    case Nil => a2
    case Cons(h,t) => Cons(h, append(t, a2))
  }

Run

object Solution {
 def main(args:Array[String]): Unit = {
   import List._

   println("init for List(1,2,3,4): " + init(List(1,2,3, 4)))
   println("init for List(1): " + init(List(1)))
   println("init for List(): " + init(List()))
 }
}

Output

init for List(1,2,3,4): Cons(1,Cons(2,Cons(3,Nil)))
init for List(1): Nil
init for List(): Nil