Functional programming in Scala, Chapter 3, List implementation

Doing the exercise in chapter 3. Finished implementing the List class.

object Example {
  sealed trait List[+A] {
    def head: A = this match {
      case Nil => throw new NoSuchElementException
      case Cons(x, _) => x
    }
    def tail: List[A] = this match {
      case Nil => throw new NoSuchElementException
      case Cons(_, x) => x
    }
    def setHead[B >: A](x: B): List[B] = this match {
      case Nil => Nil
      case Cons(y1, ys) => Cons(x, ys)
    }
    @annotation.tailrec
    final def drop(n: Int): List[A] = {
      require(n >= 0)
      this match {
        case Nil => Nil
        case ys@Cons(x, xs) => n match {
          case 0 => ys
          case _ => xs.drop(n - 1)
        }
      }
    }
    @annotation.tailrec
    private final def takeHelper[B >: A](n: Int, list: List[B], acc: List[B]): (List[B], List[B]) = list match {
      case Nil => (list, acc)
      case Cons(x, xs) => n match {
        case 0 => (list, acc)
        case _ => takeHelper(n - 1, xs, acc ++ List(x))
      }
    }
    @annotation.tailrec
    private final def takeWhileHelper[B >: A](f: B => Boolean, list: List[B], acc: List[B]): (List[B], List[B]) = list match {
      case Nil => (list, acc)
      case Cons(x, xs) => f(x) match {
        case false => (list, acc)
        case true => takeWhileHelper(f, xs, acc ++ List(x))
      }
    }
    def take(n: Int): List[A] = {
      require(n >= 0)
      val (_, acc) = takeHelper(n, this, Nil: List[A])
      acc
    }
    def takeWhile(f: A => Boolean): List[A] = {
      val (_, acc) = takeWhileHelper(f, this, Nil)
      acc
    }
    @annotation.tailrec
    final def dropWhile(f: A => Boolean): List[A] = this match {
      case Nil => Nil
      case ys@Cons(x, xs) => if(f(x)) xs.dropWhile(f) else ys
    }
    // naive implementation of foldRight
//    def foldRight[B](z: B)(f: (A, B) => B): B = this match {
//      case Nil => z
//      case Cons(x, xs) => f(x, xs.foldRight(z)(f))
//    }
    @annotation.tailrec
    final def foldLeft[B](z: B)(f: (B, A) => B): B = this match {
      case Nil => z
      case Cons(x, xs) => xs.foldLeft(f(z, x))(f)
    }
    // foldRight via foldLeft
    def foldRight[B](z: B)(f: (A, B) => B): B = {
      foldLeft((x: B) => x)((g, a) => {b => g(f(a, b))})(z)
    }
    def reduceLeft[B >: A](f: (B, B) => B): B = {
      tail.foldLeft[B](head)(f)
    }
    def reduceRight[B >: A](f: (B, B) => B): B = {
      tail.foldRight[B](head)(f)
    }
    def map[B](f: A => B): List[B] = foldRight(Nil: List[B])((x, xs) => Cons(f(x), xs))
    def filter[B >: A](f: B => Boolean) = foldRight(Nil: List[B])((x, xs) => {
      if(f(x)) Cons(x, xs)
      else xs
    })
    def filter1[B >: A](f: B => Boolean) = {
      flatMap(x => {
        if(f(x)) List(x)
        else Nil
      })
    }
    // potential stackoverflow error
    def zip[B](other: List[B]): List[(A, B)] = {
      (this, other) match {
        case (Nil, _) => Nil
        case (_, Nil) => Nil
        case (Cons(x, xs), Cons(y, ys)) => Cons((x, y), xs.zip(ys))
      }
    }
    def zipWith[B, C](other: List[B], f: (A, B) => C): List[C] = {
      this.zip(other).map(x => f(x._1, x._2))
    }
    def forall(f: A => Boolean): Boolean = {
      val satisfied = takeWhile(f)
      if(satisfied.length == length) true else false
    }
    def exists(f: A => Boolean): Boolean = {
      val dropped = dropWhile(f)
      if(dropped.length == length) false else true
    }
    def hasSubsequence[B >: A](list: List[B]): Boolean = (this, list) match {
      case (Nil, Nil) => true
      case (Nil, _) => false
      case (_, Nil) => true
      case (list1@Cons(x, xs), list2@Cons(y, ys)) => {
        if(x == y) xs.hasSubsequence(ys)
        else xs.hasSubsequence(list2)
      }
    }
    def flatMap[B](f: A => List[B]): List[B] = List.concatenate(this.map(f))
    def length: Int = foldLeft(0)((x, _) => x + 1)
    def reverse: List[A] = foldLeft(Nil: List[A])((xs, x) => Cons(x, xs))
    def append[B >: A](a: B): List[B] = foldRight(List(a))(Cons(_, _))
    def ++[B >: A](other: List[B]): List[B] = {
      foldRight(other)((x, xs) => Cons(x, xs))
    }
    def mkString(sep: String, start: String, end: String) = {
      val middle = foldLeft("")((string, x) => {
        string match {
          case "" => x.toString
          case _ => string + sep + x.toString
        }
      })
      start + middle + end
    }
    override def toString = mkString(", ", "List(", ")")
  }
  case object Nil extends List[Nothing]
  case class Cons[+A](h: A, t: List[A]) extends List[A]
  object List {
    implicit val init = Nil
    // variadic function
    def apply[A](as: A*): List[A] = {
      if(as.isEmpty) Nil
      else Cons(as.head, apply(as.tail: _*)) // the _* type annotation allows us to pass a Seq to a variadic method
    }
    def concatenate[A](as: List[A]*): List[A] = {
      as.reduceLeft(_ ++ _)
    }
    def concatenate[A](as: List[List[A]]): List[A] = {
      as.reduceLeft(_ ++ _)
    }
  }
}


object Test {
  import Example._
  val l1 = List[Int](1, 2, 3, 4)
//  l1.head
//  l1.tail
//  l1.drop(2)
//  l1.setHead(13)
//  l1.dropWhile(_ < 3)
//  l1.foldLeft[Int](0)(_ + _) // compute sum
//  l1.foldRight(0)(_ + _) // compute sum
//  l1.foldRight[List[Int]](MNil)(Cons[Int](_, _)) // returns the same list
//  l1.foldLeft[List[Int]](MNil)((xs, x) => Cons[Int](x, xs)) // reverses the list
//  l1.length
//  l1.reduceLeft(_ + _)
//  l1.reduceRight(_ + _)
//  List.concatenate(List(1, 2), List(3, 4), List(5, 6))
//
//  def add1(xs: List[Int]): List[Int] = {
//    xs.foldRight(MNil: List[Int])((x, xs) => Cons(x + 1, xs))
//  }
//  add1(List(2, 4, 6))

//  l1.toString
//  l1.map(_ + 1)
//  l1.flatMap(x => List(x, math.pow(x, 2)))
//  l1.filter(_ > 2)
//  l1.filter1(_ > 2)
//  List(1, 2, 3).zipWith(List(4, 5, 6), (x: Int, y: Int) => x + y)
//  l1.take(2)
//  l1.takeWhile(_ < 3)

  l1.forall(_ > 0)
  l1.exists(_ < 0)
  l1.dropWhile(_ < 3)
  l1.hasSubsequence(List(1, 2))
  l1.hasSubsequence(List(2, 3))
  l1.hasSubsequence(List(3, 4))
}