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 sum(ints: List[Int]): Int = ints match {
    foldLeft(l, 0.0)(_+_)
  }

  def product(ds: List[Double]): Double = ds match {
    foldLeft(l, 1.0)(_*_)
  }

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

  def tail[A](as: List[A]): List[A] = as match {
    case Nil => Nil
    case Cons(_,t) => t
  }

  def drop[A](l: List[A], n: Int) l match {
    case Nil => println("Empty list given")
    case Cons(_,t)=> drop(t,n-1)
  }

  def dropWhile[A](l:List[A])(f: A=>Boolean):List[A] = l match {
    case _ => l
    case Cons(h,t)=> if (f(h)) dropWhile(t,f)
  }

  def setHead[A](l: List[A], h: Int): List[A] = l match {
    case Cons(_,t) => Cons(h, t)
    case _ => h
  }

  def init[A](l: List[A]): List[A] = l match {
    case Nil => Nil
    case Cons(h,t) => t
  }

  def foldRight[A,B](l: List[A], z: B)(f: (A,B)=>B): B =
    l match {
      case Nil => z
      case Cons(x,xs) => f(x, foldRight(xs,z)(f))
    }

  @annotation.tailrec
  def foldLeft[A,B](l: List[A], z: B)(f: (B, A) => B): B = l match {
    case Nil => z
    case Cons(h,t) => foldLeft(t, f(z,h))(f)
  }

  def reverse[A](l: List[A]): List[A] =
    foldLeft(l, List[A]())((acc,h) => Cons(h,acc))


  def sum2(l: List[Int]) =
    foldRight(l, 0.0)(_+_)

  def product2(l: List[Double]) =
    foldRight(l, 1.0)(_*_)

  def append[A](l1: List[A], l2: List[A]): List[A] =
    foldLeft(l1, l2)(Cons(_,_))

  def concat[A](l: List[List[A]]): List[A] =
    foldRight(l, Nil:List[A])(append)

  def add1(l: List[Int]): List[Int] =
    foldRight(l, Nil:List[Int])(h,t)=>(Cons(h+1, t))

  def doubleToString(l: List[Double]): List[String] =
    foldRight(l, Nil:List[String])(h,t)=>(Cons(h toString, t))

  def map[A,B](l: List[A])(f: A=>B): List[B] =
    foldRight(l, Nil:List[B])((h,t)=Cons(f(h),t))

  def flatMap[A,B](l: List[A])(f: A=>List[B]): List[B] =
     concat(map(l)(f))

  def filter[A](l: List[A])(f: A=>A): List[A] =
    foldRight(l, Nil:List[A])((h,t) => if (f(h)) Cons(h,t) else t)

  def filterViaFlatMap[A](l: List[A])(f: A=>A): List[A] =
    flatMap(l)(a)=>if (f(a)) List(a) else Nil

  def fPairwise[A,B,C](a: List[A], b: List[B])(f: (A,B)=>C): List[C] = (a,b) match {
    case (Nil, _) => Nil
    case (_, Nil) => Nil
    case (Cons(h1,t1), Cons(h2,t2)) => Cons(f(h1,h2), addPairwise(t1,t2)(f))
  }

  def take[A]( n: Int): List[A] =
    filter(this)(a)=>(a<n)

  def takeWhile[A](l: List)(f: A=>Boolean): List[A] = l match {
    case _ => Nil
    case Cons(h,t) => if f(h) => h :: takeWhile(t)(f)
  }


  def forall(f: A=>Boolean): Boolean =
    takeWhile(this, f) match {
      case _ => false
      case this => true
    }

  def exists(f: A=>Boolean): Boolean =
    takeWhile(this, f) match {
      case _ => false
      case Cons(h,t) => true
    }



  def length[A](l: List[A]): Int =
    foldLeft(l, 0)((_, acc)=>acc+1)

  @annotation.tailrec
  def startsWith[A](l: List[A], prefix: List[A]): Boolean = (l,prefix) match {
    case (_,Nil) => true
    case (Cons(h,t),Cons(h2,t2)) if h == h2 => startsWith(t, t2)
    case _ => false
  }

  @annotation.tailrec
  def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = sup match {
    case Nil => sub == Nil
    case _ if startsWith(sup, sub) => true
    case Cons(_,t) => hasSubsequence(t, sub)
  }


  val example = Cons(1, Cons(2, Cons(3, Nil)))
  val example2 = List(1,2,3)
  val total = sum(example)

}