3.fp.scala

/*
 * Implémenter les fonctions suivantes en suivant les commentaires.
 * Respectez également les consignes suivantes:
 *  - Toutes les fonctions doivent être pures
 *  - Tout doit être immutable (val au lieu de var)
 *  - Utiliser la recursion terminale si possible
 *  - Utiliser le pattern matching si possible
 */
object Serie3 {

  /*
   * Donne la longueur d'une liste. Votre implémentation ne peut
   *  utiliser aucune fonction de List excepté isEmpty()
   */
  def len[A]( as: List[A] ): Int = {

    @scala.annotation.tailrec
    def size(rem: List[A], s: Int): Int = {
      rem match {
        case Nil => s
        case _ :: bs => size(bs, s+1)
      }
    }

    size(as, 0)
  }

  /*
   * Inverse l'ordre des elements d'une liste. Votre implémentation ne peut
   * utiliser aucune fonction de List excepté: -
   *    - isEmpty
   *    - ::
   *    - head
   *    - tail
   */
  def rev[A]( as: List[A] ): List[A] = {
    @scala.annotation.tailrec
    def takeLast(rem: List[A], bs: List[A]): List[A] = {
      rem match {
        case Nil => bs
        case a :: tail => takeLast(tail, a::bs)
      }
    }
    takeLast(as, Nil)
  }

  /*
   * Somme les elements d'une liste. Votre implémentation ne peut
   * utiliser aucune fonction de List excepté: -
   *    - isEmpty
   *    - head
   *    - tail
   */
  def sum( xs: List[Int] ): Int = {
    @scala.annotation.tailrec
    def acc(rem: List[Int], s: Int): Int ={
      rem match{
        case Nil => s
        case a :: bs => acc(bs, s+a)
      }
    }
    acc(xs, 0)
  }

  /*
   *  Retourne vrai si et seulement si la liste xs ne
   *  comprend que des valeures vraies. Votre implémentation 
   *  ne peutcutiliser aucune fonction de List excepté:
   *    - isEmpty
   *    - head
   *    - tail
   */
  @scala.annotation.tailrec
  final def and(xs: List[Boolean] ): Boolean = {
    xs match {
      case Nil => true
      case true :: bs => and(bs)
      case _ => false
    }
  }

  /*
   *  Applatit une liste. Votre implémentation 
   *  ne peut utiliser aucune fonction de List excepté:
   *   - isEmpty
   *   - head
   *   - tail
   *   - ++
   *
   */
  def flat[A]( las: List[List[A]] ): List[A] = {

    @scala.annotation.tailrec
    def through(as: List[List[A]], dst: List[A]): List[A] = {
      as match {
        case Nil => dst
        case Nil::bs => through(bs, dst)
        case (head::tail):: bs => through(tail::bs, head::dst)
      }
    }

    rev(through(las, Nil))
  }

  /*
   *  Retourne vrai si la Liste a une nombre pair d'éléments. Votre
   *  implémentation ne peut utiliser aucune fonction de List !  Vous
   *  devez utiliser le pattern matching.
   */
  final def even[A]( as: List[A] ): Boolean = as match{
    case Nil => true
    case _ :: Nil => false
    case _ :: _ :: rest => even(rest)
  }

}

object Serie3Main extends App {

  import Serie3._

  val is = List( 1, 2, 3, 4, 5 )
  val bs1 = List( true, true, false, true )
  val bs2 = List( true, true, true )
  val las1 = List.empty[List[Int]]
  val las2 = List( List(1,2), List(3), List(4,5) )

  println("1st")
  require( rev(is) == List( 5, 4, 3, 2, 1 ) )

  println("2nd ")
  require( len(is) == 5 )
  require( len( las1 ) == 0 )
  require( len( bs1 ) == 4 )

  println("3rd")
  require( flat(las1) == Nil )
  require( flat(las2) == is )

  println("4th")
  require( sum(is) == 15 )
  require( sum(flat(las2)) == sum(is) )

  println("5th")
  require( rev( bs1 ) == List( true, false, true, true ) )
  require( rev( bs2 ) == bs2 )

  println("6th")
  require( !even( is ) )
  require( even( bs1 ) )
  require( even( las1 ) )

}