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)
    }