List.scala

package uk.drkr.fpinscala.chapter3

import scala.annotation.tailrec

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

object List {
  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _*))

  /*
  Exersize 3.1
    q: what is the result of the match expression
    a: Third case matches first, with x as the first element in the list and y
    being the second, so the result is x + y, which is 3
   */
  val x = List(1, 2, 3, 4, 5) match {
    case Cons(x, Cons(2, Cons(4, _))) => x
    case Nil => 42
    case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
    case Cons(h, t) => h + sum(t)
    case _ => 101
  }

  /*
  Exersize 3.2
    q a: implement function tail for removing the first element of a List (in constant time)
    q b: what are the options to handle empty lists
    a b: Handle Nil first, and either
         * Return the empty list back
         * Throw an exception
   */
  def tail[A](l: List[A]): List[A] =
    l match {
      case Nil => throw new IllegalArgumentException("Cannot tail an empty List")
      case Cons(_, a) => a
    }

  /*
  Exersize 3.3
    q: implement function setHead for replacing the first element of a List with a different value
   */
  def setHead[A](l: List[A], v: A): List[A] =
    l match {
      case Nil => throw new IllegalArgumentException("Cannot setHead an empty List")
      case Cons(_, a) => Cons(v, a)
    }

  /*
  Exersize 3.4
    q: Generalize tail to the function drop, which removes the first n elements from a list.
       Time taken should be proportional to the number of elements being dropped
   */
  @tailrec
  def drop[A](l: List[A], n: Int): List[A] =
    // behavior of negative n is opaque
    if (n <= 0) l
    else l match {
      case Nil => throw new IllegalArgumentException("Cannot drop on empty List")
      case Cons(_, l) => drop(l, n - 1)
    }

  /*
  Exersize 3.5
    q: Implement dropWhile, which removes elements from the List prefix as long as they match a predicate
       (function that returns a bool)
  */
  @tailrec
  def dropWhile[A](l: List[A], f: A => Boolean): List[A] =
    l match {
      case Cons(h, t) if f(h) => dropWhile(t, f)
      case _ => l
    }

  /*
  Exersize 3.6
    q: Implement a function, init that returns a List consisting of all but the last element of a List
       Why can't this function be implemented in constant time like tail?
    a: Because (at least using a naive recursive approach) the singly linked data structure requires
       that we recurse through the entire list, copying each element into a new list
   */
  def init[A](l: List[A]): List[A] =
    l match {
      case Nil => throw new IllegalArgumentException("Cannot init an empty List")
      case Cons(_, Nil) => Nil
      case Cons(h, t) => Cons(h, init(t))
    }

}