99 Scala problems : les 22 premiers

Après quelques articles et tutoriels, ainsi que quelques tests sur les interactions avec Java, j’ai commencé mon apprentissage du Scala par les 99 Scala problems.

Avant de me lancer dans la résolution des problèmes en question, et en application des bonnes pratiques du TDD, j’ai écrit les signatures des méthodes, et les tests associés à ces 22 problèmes. Si vous voulez vous lancer, je vous épargne cette première étape : vous pouvez télécharger directement ce squelette.

Vous pourrez vérifier que les 22 tests échouent. Ces tests sont cependant rudimentaires, et les faire passer au vert ne garantira pas que vous avez la bonne solution (même si c’est encourageant).

D’autres personnes se sont lancées avant moi dans la résolution de ces problèmes. Comme il est toujours intéressant de comparer les différentes approches, en voici quelques unes (en plus des solutions du site original) :

Voici maintenant mes propositions pour chacun de ces problèmes, que vous pourrez tester, critiquer, optimiser. Par rapport à celles proposées sur le site officiel, elles sont sans doute moins optimisées, et plus complexes. Mais découvrant le langage, je n’ai pas eu le réflexe d’utiliser les méthodes natives de manipulation des listes avancées (flatMap, takeWhile, dropWhile, etc.), qui permettent souvent de s’en sortir d’une jolie manière.
P01 : trouver le dernier élément d’une liste

1
2
3
4
5
6
def last[E](ls: List[E]): E =
    ls match {
        case Nil => throw new NoSuchElementException
        case head :: Nil => head
        case _ :: tail => last(tail)
    }

P02 : trouver l’avant-dernier élément d’une liste

1
2
3
4
5
6
def penultimate[E](ls: List[E]): E =
    ls match {
        case head :: lastElement :: Nil => head
        case _ :: tail => penultimate(tail)
        case Nil => throw new NoSuchElementException
    }

P03 : trouver un élément donné d’une liste

1
2
3
4
5
6
def nth[E](n: Int, ls: List[E]): E =
    (n, ls) match {
        case (_, Nil) => throw new NoSuchElementException
        case (0, head :: _) => head
        case (m, _ :: tail) => nth(m - 1, tail)
    }

P04 : trouver la taille d’une liste

1
2
3
4
5
def length(ls: List[Any]): Int =
    ls match {
        case Nil => 0
        case _ :: tail => 1 + length(tail)
    }

P05 : inverser une liste

1
2
3
4
5
6
7
8
def reverse[E](ls: List[E]): List[E] =
    reverseRec(ls, Nil)
 
private def reverseRec[E](input: List[E], result: List[E]): List[E] =
    (input, result) match {
        case (Nil, res) => res
        case (head :: tail, res) => reverseRec(tail, head :: res)
    }

P06 : la liste est-elle un palindrome ?

1
2
3
def isPalindrome(ls: List[Any]): Boolean =
    // En Scala, '==' correspond à la méthode Java 'equals()'.
    (ls == reverse(ls))

P07 : « aplanir » une liste

1
2
3
4
5
6
def flatten(ls: List[Any]): List[Any] =
    ls match {
        case Nil => Nil
        case (head: List[_]) :: tail => flatten(head) ::: flatten(tail)
        case head :: tail => head :: flatten(tail)
    }

P08 éliminer les doublons successifs d’une liste

1
2
3
4
5
6
def compress[E](ls: List[E]): List[E] =
    ls match {
        case Nil => Nil
        case h1 :: h2 :: tail if (h1 == h2) => compress(h2 :: tail)
        case h1 :: tail => h1 :: compress(tail)
    }

P09 : « compacter » une liste

1
2
3
4
5
6
7
8
9
10
11
def pack[E](ls: List[E]): List[List[E]] =
    packRec(Nil, Nil, ls)
 
private def packRec[E](accu: List[E], result: List[List[E]], ls: List[E]): List[List[E]] =
    (accu, result, ls) match {
        case (Nil, res, Nil) => res
        case (acc, res, Nil) => res ::: List(acc)
        case (Nil, res, head :: tail) => packRec(List(head), res, tail)
        case (accHead :: accTail, res, lsHead :: lsTail) if (accHead == lsHead) => packRec(lsHead :: accHead :: accTail, res, lsTail)
        case (accHead :: accTail, res, lsHead :: lsTail) => packRec(List(lsHead), res ::: List(accHead :: accTail), lsTail)
    }

P10 : « encodage » d’une liste

1
2
3
def encode[E](ls: List[E]): List[(Int, E)] = {
    pack(ls) map ((l: List[E]) => (length(l), l.head))
}

P11 : encodage modifié d’une liste

1
2
3
4
5
6
7
def encodeModified(ls: List[Any]): List[Any] =
    pack(ls) map (
            (l: List[_]) => length(l) match {
                case 1 => l.head
                case n => (n, l.head)
            }
    )

P12 : « décodage » d’une liste

1
2
3
4
5
6
7
8
9
10
11
def decode[E](ls: List[(Int, E)]): List[E] =
    ls match {
        case Nil => Nil
        case (n, elem) :: tail => decodeRec(n, elem, Nil) ::: decode(tail)
    }
 
private def decodeRec[E](n: Int, elem: E, result: List[E]): List[E] =
    n match {
        case 0 => result
        case m => decodeRec(m - 1, elem, elem :: result)
    }

P13 : encodage direct d’une liste

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def encodeDirect[E](ls: List[E]): List[(Int, E)] =
    ls match {
        case Nil => List()
        case head :: tail => encodeDirectRec(1, head, List(), tail)
    }
 
private def encodeDirectRec[E](nb: Int, elem: E, result: List[(Int, E)], ls: List[E]): List[(Int, E)] =
    (nb, elem, result, ls) match {
        case (0, _, res, Nil) => res
        case (n, el, res, Nil) => res ::: List((n, el))
        case (0, _, res, head :: tail) => encodeDirectRec(1, head, res, tail)
        case (n, el, res, head :: tail) if (el == head) => encodeDirectRec(n+1, el, res, tail)
        case (n, el, res, head :: tail) => encodeDirectRec(1, head, res ::: List((n, el)), tail)
    }

P14 : dupliquer chaque élément d’une liste

1
2
3
4
5
def duplicate[E](ls: List[E]): List[E] =
    ls match {
        case Nil => Nil
        case head :: tail => head :: head :: duplicate(tail)
    }

P15 : dupliquer N fois chaque élément d’une liste

1
2
3
4
5
6
7
8
9
10
11
12
def duplicateN[E](n: Int, ls: List[E]): List[E] =
    duplicateNRec(n, n, ls)
 
private def duplicateNRec[E](n: Int, compt: Int, ls:List[E]): List[E] =
    (compt, ls) match {
        case (_, Nil) => Nil
        // Passage à l'élément suivant
        case (0, head :: tail) => duplicateNRec(n, n, tail)
        // Boucle sur l'élément 'head' tant qu'il doit être dupliqué
        case (cpt, head :: tail) => head :: duplicateNRec(n, cpt-1, head :: tail)
 
    }

P16 : supprimer un élément tous les N d’une liste

1
2
3
4
5
6
7
8
9
def drop[E](n: Int, ls: List[E]): List[E] =
    dropRec(n, 1, ls)
 
private def dropRec[E](n: Int, compt: Int, ls: List[E]): List[E] =
    (compt, ls) match {
        case (_, Nil) => Nil
        case (cpt, head :: tail) if (cpt == n) => dropRec(n, 1, tail)
        case (cpt, head :: tail) => head :: dropRec(n, cpt+1, tail)
    }

P17 : diviser une liste en deux sous-listes

1
2
3
4
5
6
7
8
9
def split[E](n: Int, ls: List[E]): (List[E], List[E]) =
    splitRec(n, Nil, ls)
 
private def splitRec[E](n: Int, left: List[E], right: List[E]): (List[E], List[E]) =
    (n, right) match {
        case (0, _) => (left, right)
        case (_, Nil) => throw new NoSuchElementException
        case (nb, head :: tail) => splitRec(nb-1, left ::: List(head), tail)
    }

P18 : extraire les éléments M à N d’une liste

1
2
3
4
5
6
7
def slice[E](start: Int, end: Int, ls: List[E]): List[E] =
    (start, end, ls) match {
        case (0, 0, _) => Nil
        case (_, _, Nil) => throw new NoSuchElementException
        case (0, n, head :: tail) => head :: slice(0, n-1, tail)
        case (m, n, head :: tail) => slice(m-1, n-1, tail)
    }

P19 : permuter les positions des éléments d’une liste à gauche

1
2
3
4
5
6
7
def rotate[E](n: Int, ls: List[E]): List[E] =
    (n, ls) match {
        case (_, Nil) => Nil
        case (0, lst) => lst
        case (_, head :: tail) if (n > 0) => rotate(n-1, tail ::: List(head))
        case (_, _) => rotate(length(ls) + n, ls)
    }

P20 : supprimer un élément d’une liste

1
2
3
4
5
6
7
8
9
def removeAt[E](n: Int, ls: List[E]): (List[E], E) =
    removeAtRec(n, Nil, ls)
 
private def removeAtRec[E](n: Int, start: List[E], end: List[E]): (List[E], E) =
    (n, end) match {
        case (_, Nil) => throw new NoSuchElementException
        case (0, head :: tail) => (start ::: tail, head)
        case (m, head :: tail) => removeAtRec(m-1, start ::: List(head), tail)
    }

P21 : insérer un élément dans une liste

1
2
3
4
5
6
def insertAt[E](elem: E, pos: Int, ls: List[E]): List[E] =
    (pos, ls) match {
        case (0, lst) => elem :: lst
        case (_, Nil) => throw new NoSuchElementException
        case (_, head :: tail) => head :: insertAt(elem, pos-1, tail)
    }

P22 : créer une liste contenant tous les entiers d’un intervalle donné

1
2
3
4
5
6
def range(start: Int, end: Int): List[Int] =
    (start, end) match {
        case (s, e) if (e < s) => Nil
        case (s, e) if (s == e) => List(s)
        case (_, _) => start :: range(start+1, end)
    }

À propos de Benoît Courtine

Open Source enthousiast, and CTO at Alcion Group.
Ce contenu a été publié dans Java, avec comme mot(s)-clé(s) , , . Vous pouvez le mettre en favoris avec ce permalien.

Une réponse à 99 Scala problems : les 22 premiers

  1. Johan Buret dit :

    Mmm… J’ai l’impression de retrouver du Caml. Je vais donc tester voir ce que donne ces problèmes en F#, qui est l’implémentation de OCaml sur son Framework

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

ERREUR : le plugin si-captcha signale que le support de la librairie image GD n'est pas détécté dans le PHP !

Contactez votre hébergeur et demandez pourquoi le support de la librairie image GD n'est pas activé pour PHP.

ERREUR : le plugin si-captcha signale que la fonction imagepng n'est pas détectée dans PHP !

Contactez votre hébergeur et demandez lui pourquoi la fonction imagepng n'est pas activée pour le PHP

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>