abstract class IntList
case class Nil() extends IntList
case class Cons(h: Int, t: IntList) extends IntList

object MyList {

  // Applies a binary operator to all elements of list as and a start value,
  // going right to left.
  def foldRight[B](as: IntList, b: B, f: (Int, B) => B): B = as match {
    case Nil() => b
    case Cons(h, t) => f(h, foldRight(t, b, f))
  }

  // Applies a binary operator to a start value and all elements of list as,
  // going left to right.
  def foldLeft[B](as: IntList, b: B, f: (B, Int) => B): B = as match {
    case Nil() => b
    case Cons(h, t) => foldLeft(t, f(b, h), f)
  }

  // Generate list of integers by applying f to b until it returns None
  def unfold(b: Int, f: Int => Option[(Int, Int)]): IntList = f(b) match {
    case None => Nil()
    case Some((a, b)) => Cons(a, unfold(b, f))
  }

}

object ListFuns {
  import MyList._

  // return the sum of the elements of is
  def sum(is: IntList): Int = //error("todo")
    foldLeft(is, 0, (_:Int) + (_:Int))

  // return the number of elements of as
  def length(as: IntList): Int = //error("todo")
    foldLeft(as, 0, (y:Int, _) => y + 1)

  // apply function f to the elements of as
  // and return the list of the results
  def map(as: IntList, f: Int => Int): IntList = //error("todo")
    foldRight(as, Nil(), (x:Int, xs:IntList) => Cons(f(x), xs))

  // return the elements of as for which f returns true
  def filter(as: IntList, f: Int => Boolean): IntList = //error("todo")
    foldRight(as, Nil(),
              (x: Int, xs:IntList) => if(f(x)) Cons(x, xs) else xs)

  // return the list consisting of the elements of xs
  // followed by the elements of ys
  def append(xs: IntList, ys: IntList): IntList = //error("todo")
    foldRight(xs, ys, (a, as:IntList) => Cons(a, as))

  // append the lists that are returned by mapping f to the elements of as
  def flatMap(as: IntList, f: Int => IntList): IntList = //error("todo")
    foldRight(as, Nil(),
      (b, bs:IntList) => append(f(b), bs)
    )

  // return the maximum number in is
  def maximum(is: IntList): Int = //error("todo")
    foldLeft(is, Int.MinValue, (x:Int, y:Int) => x max y)

  // turn the order of the elements of as around
  def reverse(as: IntList): IntList = //error("todo")
    foldLeft(as, Nil(), (xs:IntList, x:Int) => Cons(x, xs))

  // generate the list of integers from i until j
  def fromUntil(i: Int, j: Int): IntList = // error("todo")
    unfold(i, x => if(x > j) None else Some((x,x + 1)))
}