Proche de sa sortie, j'ai lu l'article de Gautier Di Folco sur sa résolution du FizzBuzz kata: branchless version.
Outre l'utilisation du pattern matching pour ne pas créer de branche, sa résolution utilise des structures de listes infinies.
On va retrouver :
numbers :: [String]
numbers = show <$> [1..]
Qui représente ici tous les entiers positifs (de 1 à +infini) sous forme de
String: c'est unRange
Mais aussi :
fizzs :: [Maybe String]
fizzs = cycle [Nothing, Nothing, Just "Fizz"]
Qui représente ici un cycle pouvant s'apparenter à
[Nothing, Nothing, Nothing, Nothing, Just "Buzz", Nothing, Nothing, Nothing, Nothing, Just "Buzz", ..]jusqu'à l'infini.
Et pour de l'agrégation :
zipWith (<>) fizzs buzzs
Qui va permettre de fusionner deux listes élément par élément en une seule en fonction d'une opération : n'hésitez pas à lire le reste de l'article de Gautier pour mieux comprendre.
Cependant, en TypeScript, le langage ne nous propose ni de Range, ni de Cycle, ni de Zip, c'est pourquoi je vous propose de créer ces structures dans ce premier épisode.
Range
Imaginons une structure de List en point d'entrée dans laquelle on va utiliser la méthode range(…) pour fabriquer notre Range :
List.range(0, 2) // 0, 2, 4, 6, 8, 10, ….
export abstract class List<T> {
abstract at(index: number): T | undefined;
get values(): T[] {
// …
}
abstract get length();
static range(start: number, step: number): List<number> {
return new Range(start, step);
}
// …
}
Notre Range ressemble alors à :
class Range extends List<number> {
constructor(
private readonly start: number,
private readonly step: number
) {
super();
}
get length(): number {
return +Infinity;
}
at(index: number): number | undefined {
return this.start + index * this.step;
}
}
Le range est une liste dont la length est infinie et dont on peut retrouver à son index la somme de start avec le produit de la valeur de l'index avec le step :
Pour un Range avec un start de 2 et 4 en step, on a alors :
- Pour l'
index1 : 2 + 1 × 4 = 6 - Pour l'
index3 : 2 + 3 × 4 = 14
Mapper
Pour transformer notre liste de number en liste de string, nous avons besoin de .map :
List.of(1, 2, 3).map(number => number.toString()) // '1', '2', '3'.
export abstract class List<T> {
// …
map<U>(transform: (value: T) => U): List<U> {
return new Mapper(this, transform);
}
// …
}
Ici, on choisit de retourner un
Mapperafin de ne pas évaluer tout de suite la transformation tout en conservant l'opération précédente via lethis.
class Mapper<T, U> extends List<U> {
constructor(
private readonly list: List<T>,
private readonly transform: (value: T) => U
) {
super();
}
get length(): number {
return this.list.length;
}
at(index: number): U | undefined {
const toTransform = this.list.at(index);
if (toTransform === undefined) {
return undefined;
}
return this.transform(toTransform);
}
}
Lorsque la méthode at(…) sera évaluée, la transformation se fera, mais comme il n'est pas possible de savoir s'il y aura une valeur ou non à un index précis, le transform(…) sera lancé seulement en présence de la valeur (lorsqu'elle n'est pas undefined).
Cycle
Le Cycle permet de répéter un ensemble de valeurs :
List.cycle(1, 2, 3); // 1, 2, 3, 1, 2, 3, 1, 2, 3, …
export abstract class List<T> {
// …
static cycle<T>(...values: T[]): List<T> {
return new Cycle(values);
}
// …
}
Avec une classe Cycle :
class Cycle<T> extends List<T> {
readonly #values: T[];
constructor(values: T[]) {
super();
this.#values = values;
}
get length(): number {
if (this.#values.length === 0) {
return 0;
}
return +Infinity;
}
at(index: number) {
return this.#values[index % this.#values.length];
}
}
Pour correspondre à une répétition d'un même ensemble de valeurs, on utilise donc un modulo % pour retrouver une valeur par rapport à la taille des valeurs à répéter #values.length.
La taille peut être à 0 s'il n'y a rien à répéter.
Zip
Un Zip permet de regrouper deux listes ensembles avec une opération de transformation basée sur les éléments de chaque List :
Exemple :
const sum = (first: number, second: number): number => first + second;
List.of(1, 2, 3).zipWith(sum, List.of(4, 5, 6));
// 5, 7, 9
Avec :
export abstract class List<T> {
// …
zipWith<S, R>(concat: Concat<T, S, R>, other: List<S>): List<R> {
return new Zip(concat, this, other);
}
// …
}
Et la classe Zip :
class Zip<F, S, R> extends List<R> {
constructor(
private readonly concat: Concat<F, S, R>,
private readonly firstList: List<F>,
private readonly secondList: List<S>
) {
super();
}
get length(): number {
return Math.min(this.firstList.length, this.secondList.length);
}
at(index: number): R | undefined {
const first = this.firstList.at(index);
const second = this.secondList.at(index);
if (first === undefined || second === undefined) {
return undefined;
}
return this.concat(first!, second!);
}
}
La taille d'un
Zipcorrespond ici à la sous liste la plus petite.
L'important c'est les valeurs
Pour récupérer des valeurs de ces listes, on utilisera at qui lance l'évaluation au moment de son appel.
On parle alors d'évaluation paresseuse ou lazy evaluation.
C'est utile dans notre cas parce que ça nous permet de représenter des listes infinies puisqu'on n'a pas à calculer toutes les valeurs.
Pour partitionner nos valeurs et récupérer une liste finie, on peut maintenant utiliser between :
export abstract class List<T> {
// …
between(from: number, to: number): List<T> {
return List.of(...iterate(to - from + 1, from).map((index) => this.at(index)!));
}
// ...
}
Ici le
toest inclus.
Et pour avoir ce sous ensemble de valeur :
const iterate = (times: number, from = 0): number[] =>
Array(times)
.fill(from)
.map((base, index) => base + index);
export abstract class List<T> {
// …
get values(): T[] {
if (this.length === +Infinity) {
throw new Error(`${this.name} list is infinite`);
}
return iterate(this.length).map((index) => this.at(index)!);
}
// ...
}
List.range(10, 1).between(3, 5).values // 13, 14, 15.
Fin du premier épisode
Nous venons de voir les notions suivantes :
- Quelques concepts derrières des listes infinies ;
- Les notions de
Range,CycleetZip; - La
lazy evaluationsur les valeurs.
À bientôt pour l'épisode 2…
