val count = 1

def foo(x : Int) : Int = {
   val y = x*x
   val z = y*y
   z*z
} 

def twice(x: Int) = 2*x

abstract class Color
case class NamedColor(name: String) extends Color
case class RGBColor(r: Int, g: Int, b: Int) extends Color

def colorToStr(c: Color) : String = c match {
  case NamedColor(n)     => n
  case RGBColor(r, g, b) => "#%02x%02x%02x".format(r, g, b)
}


def length[T](xs: List[T]) : Int = xs match {
  case Nil     => 0
  case _ :: xs => 1 + length (xs)
}

def map[A,B](f : (A) => B, xs : List[A]) : List[B] =
  xs match {
    case Nil     => Nil
    case y :: ys => f(y) :: map(f, ys)
  }  

def filter[T](p : (T) => Boolean, xs : List[T]) : List[T] = 
  xs match {
    case Nil     => Nil
    case y :: ys => if (p(y)) y :: filter(p, ys)
                      else filter(p, ys)
  } 

def foldr[A,B](f : (A, B) => B, z : B, xs : List[A]) : B =
  xs match {
    case Nil     => z
    case y :: ys => f(y, foldr(f, z, ys))
  }

def foldl[A,B](f : (A, B) => A, z : A, xs : List[B]) : A = 
  xs match {
    case Nil     => z
    case y :: ys => foldl(f, f(z, y), ys) 
  }

def append[T](xs : List[T], ys : List[T]) : List[T] =
  xs match {
    case Nil     => ys
    case z :: zs => z :: append(zs, ys)     
  }

def flatten[T](xss : List[List[T]]) : List[T] = 
  xss match {
    case Nil => Nil
    case ys :: yss => append(ys, flatten(yss))  
  } 

def zip[A,B] (xs : List[A], ys : List[B]) : List[(A, B)] =
  (xs, ys) match {
    case (Nil, _)           => Nil
    case (_, Nil)           => Nil    
    case (x1::xs1, y1::ys1) => (x1, y1) :: zip(xs1, ys1)
  } 

def unzip[A,B] (xys : List[(A,B)]) : (List[A], List[B]) = 
  xys match {
    case Nil            => (Nil, Nil)
    case (x, y) :: xys1 => {
                             val (xs, ys) = unzip(xys1)
                             (x::xs, y::ys)
                           } 
  }
/*
def fromTo(i: Int, j: Int) : List[Int] =
  if (i>j) Nil else   i :: fromTo(i+1, j)
*/

def iterate[T](a: T, f: (T) => T, p: (T) => Boolean) : List[T] = 
  if (p(a)) Nil else  a :: iterate(f(a), f, p)

def isEmpty[T](xs: List[T]) : Boolean = xs match {
  case Nil  => true
  case _::_ => false 
}

/*
def head[T](xs: List[T]) : T = xs match {
  case y::ys => y
}

def tail[T](xs: List[T]) : List[T] = xs match {
  case y::ys => ys
}
*/

/*
def sieveAux(x: Int, y: Int, ys: List[Int]) : List[Int] = ys match {
  case Nil => Nil
  case z::zs if z<y  => z :: sieveAux(x, y, zs)
  case z::zs if y==z => sieveAux(x, x+y, zs)
  case z::zs         => sieveAux(x, x+y, ys)
}
*/

def sieve(xs: List[Int]) : List[Int] = xs match {
  case Nil   => Nil
  case y::ys => filter((z: Int) => z%y != 0, ys)
/*  case y::ys => sieveAux(y, y, ys) */
}

def primes(n: Int) : List[Int] = {
  val from2 = iterate(2, (x: Int) => x+1, (x: Int) => x>n)
  val seqs  = iterate(from2, sieve, isEmpty)
  map((ys:List[Int]) => ys match { case x::xs => x }, seqs)
}

/*
def last[T](xs: List[T]) : T = xs match {
  case x::Nil   => x
  case x::xs    => last(xs)
}

def primes(xs: List[Int]): List[Int] = xs match {
  case Nil     => Nil
  case y :: ys => y :: primes(sieveAux(y, y, ys))
}
*/