S-99 : P02, P03, P04, P05

Avant d’aller plus loin laissez-moi vous dire que d’intéressantes discussions sont en cours sur la mailing liste du PSUG (Paris Scala User group). Je vous encourage à vous inscrire afin de prendre part aux échanges. Nos oignons maintenant!

Le problème P02

Il s’agit en fait d’écrire une fonction qui retourne l’avant dernier élément d’une liste. Voici l’exemple donné sur le site du S-99.

scala> penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5

La solution au P02

Voici une des solutions auxquelles je suis arrivé:

def penultimate[T](xs: List[T]) = {
      xs.reverse match {
        case _ :: x :: _ => Some(x)
        case _ => None
      }
    }

Le test de la solution à P02

import org.specs2.mutable._

class P02Spec extends Specification {
  "P02.penultimate(List())" should {

    "return None" in {
      P02.penultimate(List()) must_== None
    }

    "return None" in {
      P02.penultimate(List(1)) must_== None
    }

    "return Some(2.5)" in {
      P02.penultimate(List(3.23, 2.4)) must_== Some(3.23)
    }

    "return Some(2)" in {
      P02.penultimate(List(1, 2, 3)) must_== Some(2)
    }

    "return Some(3)" in {
      P02.penultimate(List(1, 2, 3, 4)) must_== Some(3)
    }
  }
}

Le problème P03

Il s’agit d’écrire une fonction qui renvoie l’élément correspondant à un index donné. Exemple:

scala> nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2

La solution à P03

Avant d’aller plus loin permettez moi de vous dire que cet exercice n’a rien de nécessaire car l’API des listes permet de récupérer l’élément à un index donné de la façon suivante:

val element = xs(index)

Maintenant l’une des solutions que j’ai pu avoir:

def nth[T](index: Int, xs: List[T]):Option[T] = {
    (index, xs) match {
      case (_, Nil) => None
      case (0, head :: tail) => Some(head)
      case (_, head :: tail) if(index == -1 || index > (xs.length + 1)) => None
      case (_, head :: tail) => nth(index - 1, tail)
    }
  }

Remarquez l’usage du pattern matching sur le tuple formé de l’index et de la liste.

Le test de la solution à P03

Enfin le test:

import org.specs2.mutable._

class P03Spec extends Specification {
  "P03.nth(index, xs)" should {

    "return None" in {
      P03.nth(-1, List(1, 3)) must_== None
    }

    "return Some(1)" in {
      P03.nth2(0, List(1, 3)) must_== Some(1)
    }

    "return Some(4)" in {
      P03.nth(2, List(2, 3, 4)) must_== Some(4)
    }

    "return None" in {
      P03.nth2(10, List(2, 3, 4, 5)) must_== None
    }

    "return None" in {
      P03.nth(0, List()) must_== None
    }
  }
}

Le problème P04

Il s’agit encore une fois d’implémenter une fonctionnalité déjà présente dans l’API des listes mais c’est pour le fun: trouver le nombre d’éléments dans une liste Exemple:

scala> length(List(1, 1, 2, 3, 5, 8))
res0: Int = 6

La solution au P04

Voici deux solutions à ce problème: l’une utilise la recursivité et l’autre la méthode foldLeft() de l’API des listes.

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

def length[T](xs: List[T]) = {
  xs.foldLeft(0)((x, _) => x + 1)
}

Le test à la solution au P04

import org.specs2.mutable._

class P04Spec extends Specification {
  "P04.length(xs)" should {

    "return 0" in {
      P04.length(List()) must_== 0
    }

    "return 4" in {
      P04.length(List(1, 2, 3, 4)) must_== 4
    }

    "return 5" in {
      P04.length(List(1, 2, 3, 4, 5)) must_== 5
    }

    "return 7" in {
      P04.length(List(1, 2, 3, 4, 5, 6, 7)) must_== 7
    }
  }
}

Le problème P05

Il s’agit d’écrire une liste qui inverse une liste (pour info cette méthode existe déjà dans l’API des listes). Exemple:

scala> reverse(List(1, 1, 2, 3, 5, 8))
res0: List[Int] = List(8, 5, 3, 2, 1, 1)

La solution au P05

def reverse[T](xs: List[T]):List[T] = xs match {
    case Nil => Nil
    case head :: tail => reverse(tail) :+ head
  }

Le problème P05

Enfin un petit test pour s’assurer que tout se passe bien!

import org.specs2.mutable._

class P05Spec extends Specification {
  "P05.reverse(xs)" should {

    "return Nil" in {
      P05.reverse(List()) must_== Nil
    }

    "return List(4, 3, 2, 1)" in {
      P05.reverse(List(1, 2, 3, 4)) must_== List(4, 3, 2, 1)
    }

    "return List(5, 4, 3, 2, 1)" in {
      P05.reverse(List(1, 2, 3, 4, 5)) must_== List(5, 4, 3, 2, 1)
    }

    "return List(7, 6, 5, 4, 3, 2, 1)" in {
      P05.reverse(List(1, 2, 3, 4, 5, 6, 7)) must_== List(7, 6, 5, 4, 3, 2, 1)
    }
  }
}

Conclusion

J’espère que les quelques solutions vous ont donné envie de suivre les prochains épisodes du S-99. Ne décrochez pas là les problèmes deviennent de plus en plus intéressants! A bientôt!