Coding Stories

Singe savant en ingénierie logicielle

Quicksort en Scala

| Comments

Retour aux racines du génie logiciel : le tri. Tout développeur doit savoir écrire un tri en moins de 5 minutes.

Comment faire un quicksort en Scala ?

1
2
3
4
5
6
def sort (list : Seq[Int]) : Seq[Int] = {
  list match {
    case Nil => list
    case x :: xs => sort(xs.filter(_ < x)) ++ List(x) ++ sort(xs.filter(_ >= x))
  }
}

Ça marche pour les int. Mais si je veux trier des float, des String, des Scoubidou ? Il faudrait généraliser la fonction. Pour cela il existe le trait `Ordered qui permet de définir une relation d’ordre total sur les éléments.

1
2
3
4
5
6
def sort [A <% Ordered[A]] (list:Seq[A]): Seq[A] = {
  list match {
    case Nil => list
    case x :: xs => sort(xs.filter(_ < x)) ++ List(x) ++ sort(xs.filter(_ >= x))
  }
}

L’expression `[A <% Ordered[A]] est une view bound. Cela permet de définir une fonction polymorphique mais aussi fournit la conversion implicite du type A en Ordered[A]. En fait cette définition :

1
def sort [A <% Ordered[A]] (list:Seq[A]): Seq[A] = { /* ... */ }

est équivalente à :

1
def sort [A] (list:Seq[A])(implicit conv: A => Ordered[A]): Seq[A] = { /* ... */ }

Avantage : l’objet scala.Predef qui est tourjours chargé par Scala possède déjà plusieurs fonctions implicites de converstion par exemple Int vers Ordered[Int].

Et si maintenant nous compararions nos scoubidous ?

1
2
3
4
5
6
case class Scoubidou(name: String)
val samy = Scoubidou("Samy")
val daphne = Scoubidou("Daphne")
sort(List(samy, daphne))

> error: no implicit argument matching parameter type (Scoubidou) => Ordered[Scoubidou] was found.

Et oui, sort attend un Ordered. Bien sûr nous pourrions nous arranger pour que Scoubidou étende le trait Ordered mais parfois ce n’est simplement pas possible, par exemple parce que le type est fournit par une bibliothèque sur laquelle on n’a pas la main. Mais il est possible de définir une fonction implicite de conversion qui trie les Scoubidou selon l’ordre lexicographique (en clair on va déléguer l’appel à compare au champ name).

1
2
3
4
5
6
7
implicit def scoubidou2ordered (x: Scoubidou): Ordered[Scoubidou] = {
  new Ordered[Scoubidou] {
    def compare(that: Scoubidou): Int = {
      x.name.compare(that.name)
    }
  }
}

et maintenant on peut trier la liste :

1
2
3
sort(List(samy, daphne))

> Seq[Scoubidou] = List(Scoubidou(Daphne), Scoubidou(Samy))

Comments