object AProExam extends Application {
  
  /* EXERCICE 1 */
  
  val dictionnaire = List("ara", "ado", "kayak", "kanuk")

  def palindromes(xs: List[String]): List[String] =
    for (w <- xs; if (w compareTo w.reverse) == 0) yield w
      
  def plusLong(xs: List[String]): String = {
    var candidat = ""
    for (w <- xs) if (w.length > candidat.length) { candidat = w }
    candidat
  }
  
  def commence(xs: List[String]): List[Pair[String, String]] =
    for (w1 <- xs; w2 <- xs; if (w1(0) == w2(0)) && (w1 != w2)) yield
      Pair(w1, w2)
  
  println("palindromes = " + palindromes(dictionnaire))
  println("plusLong = " + plusLong(dictionnaire))
  println("commence = " + commence(dictionnaire))
  
  
  def palindromes2(xs: List[String]): List[String] = 
    xs filter { w => (w compareTo w.reverse) == 0 }
  
  def plusLong2(xs: List[String]): String =
    ("" /: xs) { (c, w) => if (w.length > c.length) w else c }
  
  def commence2(xs: List[String]): List[Pair[String, String]] =
    xs flatMap { w1 => xs flatMap { w2 =>
      if (w1(0) == w2(0) && w1 != w2) List(Pair(w1, w2)) else Nil
    }}
  
  println("palindromes2 = " + palindromes2(dictionnaire))
  println("plusLong2 = " + plusLong2(dictionnaire))
  println("commence2 = " + commence2(dictionnaire))
  
  
  /* EXERCICE 2 */
  
  val blackTrack: Stream[Double] = Stream(12.8, 13.0, 11.2, 33.5, 9.9, 13.5, 61.8)
  
  def moyenne(trous: Stream[Double]): Stream[Double] = {
    def moyenneImpl(trous: Stream[Double], n: Int, moyenneAvant: Double): Stream[Double] = {
      if (trous.isEmpty)
        Stream.empty
      else {
        val moyenne1: Double = (trous.head + moyenneAvant*n) / (n+1)
        Stream.cons(moyenne1, moyenneImpl(trous.tail, n+1, moyenne1))
      }
    }
    Stream.cons(trous.head, moyenneImpl(trous.tail, 1, trous.head))
  }
  
  def paimentTrou(trous: Stream[Double], moyennes: Stream[Double]): Stream[Double] =
    for ((trou, moyenne) <- trous.tail zip moyennes if trou >= moyenne * 1.73) yield trou
  
  def paimentTrou2(trous: Stream[Double], moyenne: Stream[Double]): Stream[Double] = {
    def paimentImpl(trous: Stream[Double], moyenne: Stream[Double]): Stream[Double] = {
      if (trous.isEmpty)
        Stream.empty
      else if (trous.head >= (1.73 * moyenne.head))
        Stream.cons(trous.head, paimentImpl(trous.tail, moyenne.tail))
      else
        paimentImpl(trous.tail, moyenne.tail)
    }
    paimentImpl(trous.tail, moyenne)
  }
  
  println("moyenne = " + moyenne(blackTrack).force)
  println("paimentTrou = " + paimentTrou(blackTrack, moyenne(blackTrack)).force)
  
  
  /* EXERCICE 3 */
  
  /*
  
  On prouve
    xs filter p filter p == xs filter p
  par induction sur xs
  
  cas xs = Nil
  
          (Nil filter p) filter p == Nil filter p
                     Nil filter p == Nil filter p         --> par E-Nil
                                 vrai                     --> trivialement
  
  
  cas xs = x::xs
  avec hyp. ind.
  (xs filter p) filter p == xs filter p
    
  si p(x)
      ((x::xs) filter p) filter p == (x::xs) filter p
    (x :: (xs filter p)) filter p == (x::xs) filter p     --> par E-Xs1
    x :: ((xs filter p) filter p) == (x::xs) filter p     --> par E-Xs1
               x :: (xs filter p) == (x::xs) filter p     --> par hyp. ind.
               x :: (xs filter p) == x :: (xs filter p)   --> par E-Xs1
                                 vrai                     --> trivialement
  
  si !p(x)
      ((x::xs) filter p) filter p == (x::xs) filter p
           (xs filter p) filter p == (x::xs) filter p     --> par E-Xs2
           (xs filter p) filter p == xs filter p          --> par E-Xs2
                                 vrai                     --> par hyp. ind.
  
  CQFD
  
  */
  
  
  /* EXERCICE 4 */
  
  val liste = List(5, 3, 9, 4, 1, 2, 7, 4, 6, 2, 6)
  
  def partition(lss: List[Int], pivot: Int): Pair[List[Int], List[Int]] = lss match { 
    case Nil => (Nil, Nil) 
    case l :: ls =>
      val Pair(pp, pg) = partition(ls, pivot)
      if (l < pivot)
        Pair(l :: pp, pg)
      else
        Pair(pp, l :: pg)
  }
  
  def quicksort(lss: List[Int]): List[Int] =
  if (lss.length > 1) {
    val Pair(pp, pg) = partition(lss.tail, lss.head)
    quicksort(pp) ::: lss.head :: quicksort(pg)
  }
  else
    lss
  
  println("partition = " + partition(liste.tail, liste.head))
  println("quicksort = " + quicksort(liste))

  /*
  
  partition([], P, [] []). 
  partition([X|Xs], P, [X|Ys], Zs) :- lt(X, P), partition(Xs, P, Ys, Zs).
  partition([X|Xs], P, Ys, [X|Zs]) :- gt(X, P), partition(Xs, P, Ys, Zs).
  
  quicksort([], []). 
  quicksort([X|Xs], Ys) :- partition(Xs, X, Ls, Gs),
                           quicksort(Ls, Lss),
                           quicksort(Gs, Gss),
                           append(Lss, [X|Gss], Ys).
  
  */
  
}