Scala List Implementation Exercises

sealed trait List[+A] {
  override def toString = {
    def toScalaList(t: List[A]): scala.List[A] = t match {
      case Empty => Nil
      case Cons(h, t) => h :: toScalaList(t)
    }
    toScalaList(this).toString
  }
}
final case object Empty extends List[Nothing]
final case class Cons[A](h: A, t: List[A]) extends List[A]

object List {
  def foldRight[A, B](as: List[A], b: B, f: (A, B) => B): B = as match {
    case Empty => b
    case Cons(h, t) => f(h, foldRight(t, b, f))
  }

  def foldLeft[A, B](as: List[A], b: B, f: (B, A) => B): B = as match {
    case Empty => b
    case Cons(h, t) => foldLeft(t, f(b, h), f)
  }

  def reduceRight[A](as: List[A], f: (A, A) => A): A = as match {
    case Empty => error("bzzt. reduceRight on empty list")
    case Cons(h, t) => foldRight(t, h, f)
  }

  def reduceLeft[A](as: List[A], f: (A, A) => A): A = as match {
    case Empty => error("bzzt. reduceLeft on empty list")
    case Cons(h, t) => foldLeft(t, h, f)
  }

  def unfold[A, B](b: B, f: B => Option[(A, B)]): List[A] = f(b) match {
    case Some((a, b)) => Cons(a, unfold(b, f))
    case scala.None => Empty
  }
}

sealed trait Natural {
  override def toString = {
    def toInt(n: Natural): Int = n match {
      case Zero => 0
      case Succ(x) => 1 + toInt(x)
    }
    toInt(this).toString
  }
}
final case object Zero extends Natural
final case class Succ(c: Natural) extends Natural

object Exercises {

  def add(x: Natural, y: Natural): Natural = sys.error("todo")

  def sum(is: List[Int]): Int = sys.error("todo")

  def length[A](as: List[A]): Int = sys.error("todo")

  def map[A, B](as: List[A], f: A => B): List[B] = sys.error("todo")

  def filter[A](as: List[A], f: A => Boolean): List[A] = sys.error("todo")

  def append[A](x: List[A], y: List[A]): List[A] = sys.error("todo")

  def flatten[A](as: List[List[A]]): List[A] = sys.error("todo")

  def flatMap[A, B](as: List[A], f: A => List[B]): List[B] = sys.error("todo")

  def maximum(is: List[Int]): Int = sys.error("todo")

  def reverse[A](as: List[A]): List[A] = sys.error("todo")
}