S-99: P06, P07

Je continue la résolution des 99 problèmes en Scala. Au fur et à mesure que j'avance dans la résolutions de ces problèmes je me rends compte je fais beaucoup usage du pattern matching. Et cet épisode ne fait pas exception à la règle!

Le problème P06: Vérifier si une liste est un palindrome

C'est par là si vous voulez en savoir davantage sur le palindrome.
Exemple

scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true

La solution à P06

Je suis rapidement arrivé à la solution suivante consistant à comparer la liste avec son inverse. J'ai ensuite cherché d'autres plus "efficace" mais je ne suis pas arrivé à trouver une solution plus "fonctionnelle" à mon goût.

def isPalindrome[T](xs: List[T]) = xs.reverse == xs

Le test de la solution

import org.specs2.mutable._

class P06Spec extends Specification {
  "P06.isPalindrome(xs)" should {    
    "return true" in {
      P06.isPalindrome(List()) must_== true
    }
    
    "return true" in {
      P06.isPalindrome(List(1)) must_== true
    }
    
    "return true" in {
      P06.isPalindrome(List(60, 60)) must_== true
    }
    
    "return true" in {
      P06.isPalindrome(List(3, 2, 1, 2, 3)) must_== true
    }
  }
}

Le problème P07: Mettre à plat une liste de listes

Il s'agit de mettre à plat une liste dont les constituants peuvent être des listes à leur tour. C'est pour le fun que nous écrivons cette fonction mais pas une nécessité car l'API des listes fournit une méthode permettant de mettre à plat une liste.
Exemple:

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

La solution à P07

La solution utilise le pattern matching et la récursivité à fond!

  def flatten(xs: List[Any]): List[Any] = {
    xs match {
      case head :: tail => (head, tail) match {
        case (h: List[Any], t) => flatten(h) ++ flatten(t)
        case (h: Any, t) => h :: flatten(t)
      }
      case x => x
    }
  }

Le test de la solution

import org.specs2.mutable._

object P07Spec extends Specification {
  "P07.flatten(xs)" should {
    "return Nil" in {
      P07.flatten(Nil) must_== Nil
    }
    
    "return List(1)" in {
      P07.flatten(List(1)) must_== List(1)
    }
    
    "return List(1, 2)" in {
      P07.flatten(List(1, List(2))) must_== List(1, 2)
    }
    
    "return List(1, 2, 3, 4)" in {
      P07.flatten(List(1, List(2, 3), 4)) must_== List(1, 2, 3, 4)
    }
    
    "return List(1, 2, 3, 4, 5, 7, 8)" in {
      P07.flatten(List(1, List(2, 3), 4, List(5, List(6, List(7, 8))))) must_== List(1, 2, 3, 4, 5, 6, 7, 8)
    }
  }
}

Fin du voyage mes amis! A bientôt pour un autre épisode ;-)

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!