Résumé en français : On vous donne une suite de nombres ainsi qu’une fonction booléenne. On cherche à récupérer le plus long préfixe (c’est-à-dire en commençant par le terme à gauche) d’éléments vérifiés par cette fonction. Par exemple, si la fonction booléenne est “être un nombre pair” (isEven en anglais) et que la suite de nombres est [2,4,6,8,1,2,5,4,3,2], le plus long préfixe est [2,4,6,8] puisqu’ensuite 1 n’est pas pair.
Cet exercice est plus abstrait que les précédents dans le sens où l’un des paramètres est une fonction.
A quel endroit faut-il s’arrêter ?
Une idée est de chercher le rang (s’il existe) où la fonction booléenne donnera faux. On devra alors garder les valeurs entre la position 0 et rang – 1. Pour l’exemple donné, la première valeur impaire est à la 4e position (le premier nombre est à la position 0), on garde donc les nombres entre les positions 0 et 4-1=3. En JavaScript c’est assez simple, voici par exemple comment trouver la position du premier nombre impair :
>> [2,4,6,8,1,2,5,4,3,2].findIndex(v => v % 2 != 0)
4Remarquez que v % 2 != 0 peut être remplacé par v % 2 uniquement puisque si un nombre est impair, v % 2 sera égal à 1 qui correspond à VRAI en Python ou JavaScript.
Et lorsqu’aucune valeur ne remplit la condition, JavaScript retourne -1 :
>> [2,4,6,8,1,2,5,4,3,2].findIndex(v => v > 10) // Nb plus grand que 10 ?
-1On peut donc déjà écrire cette version finale en JavaScript à tester ici :
const pair = n => n % 2 == 0 // true si n est pair, false sinon
takeWhile = (a, f) => {
let fin = a.findIndex(v => !f(v)); // On cherche où s'arrêter
return fin == -1 ? a : a.slice(0, fin); // Tableau complet ou découpage
};
>> takeWhile([2,4,6,8,1,2,5,4,3,2], pair)
[2, 4, 6, 8]Le if…else peut être remplacé par l’opérateur ternaire :
condition ? exprSiVrai : exprSiFauxDans notre cas, si fin vaut -1, renvoyer le tableau complet sinon faire le découpage. On peut utiliser notre programme avec des fonctions quelconques, par exemple pour trouver le plus long préfixe de carrés (nombres de la forme n * n) dans un tableau :
const carre = n => n == (Math.sqrt(n) | 0) ** 2
>> takeWhile([4,9,36,48,100,121], carre)
[4, 9, 36]La notation n | 0 est équivalente à un Math.floor(n)
En Python, on peut également rechercher l’index de la première valeur ne vérifiant pas une condition :
>> next(i for i,v in enumerate([2,4,6,8,1,2,5,4,3,2]) if v%2 != 0)
4Et qui renvoie un message d’erreur lorsque la condition n’est jamais vérifiée :
>> next(i for i,v in enumerate([2,4,6,8]) if v%2 != 0)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIterationPour contourner le problème, on peut utiliser try et except :
def cherche(a):
try:
return next(i for i,v in enumerate(a) if v%2 != 0)
except:
return -1
>> cherche([2,4,6,8,1,2,5,4,3,2])
4
>> cherche([2,4,6,8])
-1Ce qui donne ce programme final :
def pair(n): return n % 2 == 0
def takeWhile(a, f):
try:
fin = next(i for i,v in enumerate(a) if not(f(v)))
return a[:fin]
except:
return a
>> takeWhile([2,4,6,8,1,2,5,4,3,2], pair)
[2, 4, 6, 8]
>> takeWhile([2,4,8,6], pair)
[2, 4, 8, 6]Passons à APL en restant dans l’idée de chercher le rang où arrêter la sélection.
a ← 2 4 6 8 1 2 5 4 3 2 ⍝ Vecteur initial
0 = 2 | a ⍝ Le reste par 2 vaut-il 0 ?
1 1 1 1 0 1 0 1 0 1 ⍝ Vrai pour les 4 premiers puis Faux...
∧\ 0 = 2 | a ⍝ On fait un scan avec la fonction ∧ (ET)
1 1 1 1 0 0 0 0 0 0Le test 0 = 2 | a peut aussi être remplacé par ~ 2 | (négation) :
~ 2 | 2 4 6 8 1 2 5 4 3 2
1 1 1 1 0 1 0 1 0 1Ensuite la technique est de scanner (de la gauche vers la droite en APL) en utilisant le ET. Le premier terme (celui à gauche) est toujours récupéré puis un ET est exécuté entre les 2 premiers termes : 1 ∧ 1 = 1, ensuite entre les 3 premiers termes etc. Comme il s’agit de la fonction ET, dès qu’un des nombres est nul, l’ensemble sera faux, d’où la suite de 0 à partir du premier nombre impair.
Ce vecteur booléen va servir à sélectionner (filtrer) les éléments à conserver :
(∧\ 0 = 2 | a) / a
2 4 6 8Voyons comment généraliser l’écriture à une fonction booléenne quelconque. Créons par exemple isEven qui teste si le reste de la division du nombre par 2 est bien 0 :
isEven ← ~ 2 | ⊢
isEven 4 5 2 11
1 0 1 0Pour mettre cette fonction en paramètre dans takeWhile, nous allons écrire son nom en tant que chaine puis utiliser ⍎ pour l’exécuter :
takeWhile_essai ← {(⍎⍺) ⍵}
'isEven' takeWhile_essai 4 5 2 11
1 0 1 0On exécute le terme de gauche (⍎⍺) en l’appliquant au terme de droite ⍵. D’où cette version finale :
takeWhile ← { ( ∧\ (⍎ ⍺) ⍵ ) / ⍵ }
'isEven' takeWhile 2 4 6 8 1 2 5 4 3 2
2 4 6 8Comme me le fait remarquer Conor Hoekstra, expert en APL, on peut aussi utiliser l’écriture :
Lien pour tester directement le code ci-dessous :
takeWhile ← {⍵ /⍨ ∧\ ⍺⍺ ⍵}
isEven takeWhile 2 4 6 8 1 2 5 4 3 2
2 4 6 8Le symbole ⍨ permettant de commuter les arguments et ⍺⍺ pour récupérer la fonction (et donc inutile de la mettre sous forme de chaine)
Modules existants pour Python et JavaScript
On retrouve takeWhile dans certaines bibliothèques Python, comme itertools :
>> from itertools import takewhile
>> list(takewhile(lambda x: x%2 == 0, [2,4,6,8,1,2,5,4,3,2]))
[2,4,6,8]Ce qui permet de définir notre takeWhile (que nous noterons _takeWhile) par :
from itertools import takewhile
def isEven(n):
return 0 == n % 2
def _takeWhile(a, f):
return list(takewhile(f, a))
>> _takeWhile([2,4,6,8,1,2,5,4,3,2], isEven)
[2, 4, 6, 8]De même on retrouve takewhile en JavaScript, par exemple dans la bibliothèque collect.js.
>> a = collect([2,4,6,8,1,2,5,4,3,2]) // Création d'une collection
Object { items: (10) […] }
>> const isEven = n => 0 == n % 2 // notre fonction booléenne
>> a.takeWhile(isEven)
Object { items: (4) […] }
>> a.takeWhile(isEven).all()
Array(4) [ 2, 4, 6, 8 ]Ou en une seule ligne :
>> collect([2,4,6,8,1,2,5,4,3,2]).takeWhile(isEven).all()
Array(4) [ 2, 4, 6, 8 ]Ce qui permet de définir notre fonction _takeWhile :
>> _takeWhile = (a, f) => collect(a).takeWhile(f).all()
>> _takeWhile([2,4,6,8,1,2,5,4,3,2], isEven)
Array(4) [ 2, 4, 6, 8 ]