Chapitre 12 : La Traversée des Types

Jusqu'ici, dans notre cirque des conteneurs, vous nous avez vus dompter le redoutable Foncteur, le pliant à notre volonté pour exécuter toute opération qui nous chante. Vous avez été éblouis par le jonglage simultané d'effets dangereux grâce à l'application fonctionnelle pour collecter les résultats. Vous êtes restés médusés en voyant des conteneurs disparaître en fumée en les joignant ensemble. Dans le chapiteau des effets secondaires, nous les avons composés en un seul. Récemment, nous avons dépassé le naturel pour transformer un type en un autre sous vos yeux ébahis.

Pour notre prochain tour, observons les traversées. Nous verrons les types s'entrelacer comme des acrobates préservant intacte notre valeur. Nous réorganiserons les effets tels les wagons d'un manège tournoyant. Quand nos conteneurs s'emmêlent comme les membres d'un contorsionniste, cette interface les démêlera. Nous observerons différents effets selon leur agencement. Passez-moi mes hauts-de-chausses et mon sifflet à coulisse, c'est parti.

Types n' Types

Entrons dans l'étrange :

// readFile :: FileName -> Task Error String

// firstWords :: String -> String
const firstWords = compose(intercalate(' '), take(3), split(' '));

// tldr :: FileName -> Task Error String
const tldr = compose(map(firstWords), readFile);

map(tldr, ['file1', 'file2']);
// [Task('hail the monarchy'), Task('smash the patriarchy')]

Ici nous lisons plusieurs fichiers pour finir avec un tableau inutile de tâches. Comment les dupliquer ? Idéalement, nous pourrions inverser les types pour obtenir Task Error [String] au lieu de [Task Error String]. Ainsi nous aurions une future valeur contenant tous les résultats, bien plus adaptée à nos besoins asynchrones que plusieurs valeurs arrivant à leur guise.

Voici un dernier cas épineux :

// getAttribute :: String -> Node -> Maybe String
// $ :: Selector -> IO Node

// getControlNode :: Selector -> IO (Maybe (IO Node))
const getControlNode = compose(map(map($)), map(getAttribute('aria-controls')), $);

Voyez ces IO aspirant à s'unir. Nous aimerions les joindre pour qu'ils dansent proches, mais hélas un Maybe les sépare comme chaperon au bal de promo. Notre meilleure option est de réorganiser leurs positions pour simplifier la signature en IO (Maybe Node).

Feng Shui Typologique

L'interface Traversable offre deux fonctions clés : sequence et traverse.

Réorganisons nos types avec sequence :

sequence(List.of, Maybe.of(['the facts'])); // [Just('the facts')]
sequence(Task.of, new Map({ a: Task.of(1), b: Task.of(2) })); // Task(Map({ a: 1, b: 2 }))
sequence(IO.of, Either.of(IO.of('buckle my shoe'))); // IO(Right('buckle my shoe'))
sequence(Either.of, [Either.of('wing')]); // Right(['wing'])
sequence(Task.of, left('wing')); // Task(Left('wing'))

Voyez ceci ? Notre type imbriqué s'inverse comme un pantalon de cuir par temps humide. Le foncteur interne migre à l'extérieur. Notons que sequence exige des arguments spécifiques :

// sequence :: (Traversable t, Applicative f) => (a -> f a) -> t (f a) -> f (t a)
const sequence = curry((of, x) => x.sequence(of));

Le second argument doit être un Traversable contenant un Applicative. Cela transforme t (f a) en f (t a). Le premier argument, optionnel dans les langages typés, aide pour les types récalcitrants comme Left.

Implémentons sequence pour Either :

class Right extends Either {
  // ...
  sequence(of) {
    return this.$value.map(Either.of);
  }
}

Si la valeur est un foncteur applicatif, un simple map suffit pour restructurer le type.

L'argument of est crucial pour les cas comme Left qui nécessitent une assistance pour préserver la structure.

class Left extends Either {
  // ...
  sequence(of) {
    return of(this);
  }
}

Les contraintes du Applicative imposent d'avoir un Foncteur Pointé avec of. Dans les langages typés, le type externe est inféré automatiquement.

Variétés d'Effets

L'ordre des types influence le comportement. [Maybe a] représente des valeurs potentielles, Maybe [a] une collection conditionnelle. De même, l'ordre Either Error (Task Error a)/Task Error (Either Error a) différencie validation client/serveur.

// fromPredicate :: (a -> Bool) -> a -> Either e a

// partition :: (a -> Bool) -> [a] -> [Either e a]
const partition = f => map(fromPredicate(f));

// validate :: (a -> Bool) -> [a] -> Either e [a]
const validate = f => traverse(Either.of, fromPredicate(f));

partition classe les résultats selon un prédicat tandis que validate retourne la première erreur. L'agencement typologique module le comportement.

Examinons traverse pour List :

traverse(of, fn) {
    return this.$value.reduce(
      (f, a) => fn(a).map(b => bs => bs.concat(b)).ap(f),
      of(new List([])),
    );
  }

La fonction utilise un reduce avec un accumulateur applicatif. Décomposons :

1. Signature : reduce :: [a] -> (f -> a -> f) -> f -> f. L'accumulateur initial est Either e [a].

2. La valeur initiale Right([]) fixe le type de sortie.

3. fromPredicate(f) génère Either e a pour chaque élément.

4. Le map accumule les succès via une fermeture, conservant l'état dans Either.

5. L'application (ap) propage les erreurs ou agrège les résultats valides.

Cette transformation magistrale s'obtient en 6 lignes grâce aux abstractions applicatives, démontrant la puissance du code générique.

La Valse des Types

Revisitons nos exemples initiaux :

// readFile :: FileName -> Task Error String

// firstWords :: String -> String
const firstWords = compose(intercalate(' '), take(3), split(' '));

// tldr :: FileName -> Task Error String
const tldr = compose(map(firstWords), readFile);

traverse(Task.of, tldr, ['file1', 'file2']);
// Task(['hail the monarchy', 'smash the patriarchy']);

En utilisant traverse, nous synchronisons les Task comme avec Promise.all(), mais de manière générique pour tout type traversable.

Simplifions le dernier exemple :

// getAttribute :: String -> Node -> Maybe String
// $ :: Selector -> IO Node

// getControlNode :: Selector -> IO (Maybe Node)
const getControlNode = compose(chain(traverse(IO.of, $)), map(getAttribute('aria-controls')), $);

chain(traverse(IO.of, $)) remplace map(map($)) en inversant et aplatissant les IO via chain.

Ordre et Désordre

Ces lois constituent des garanties vitales. L'architecture logicielle vise à imposer des contraintes utiles pour guider les solutions.

Une interface sans lois n'est qu'indirection. Les propriétés exposées assurent la cohérence, permettant le remplacement d'implémentations.

Passons aux lois :

Identité

const identity1 = compose(sequence(Identity.of), map(Identity.of));
const identity2 = Identity.of;

// test it out with Right
identity1(Either.of('stuff'));
// Identity(Right('stuff'))

identity2(Either.of('stuff'));
// Identity(Right('stuff'))

Utiliser Identity avec sequence préserve la structure. Cette loi utilise Identity comme foncteur neutre dans la catégorie des foncteurs.

Composition

const comp1 = compose(sequence(Compose.of), map(Compose.of));
const comp2 = (Fof, Gof) => compose(Compose.of, map(sequence(Gof)), sequence(Fof));


// Test it out with some types we have lying around
comp1(Identity(Right([true])));
// Compose(Right([Identity(true)]))

comp2(Either.of, Array)(Identity(Right([true])));
// Compose(Right([Identity(true)]))

La composition de foncteurs reste stable après permutation. Des librairies comme QuickCheck permettent de vérifier cette loi via tests aléatoires.

Cette loi permet la fusion des traversées, optimisant les performances.

Naturalité

const natLaw1 = (of, nt) => compose(nt, sequence(of));
const natLaw2 = (of, nt) => compose(sequence(of), map(nt));

// test with a random natural transformation and our friendly Identity/Right functors.

// maybeToEither :: Maybe a -> Either () a
const maybeToEither = x => (x.$value ? new Right(x.$value) : new Left());

natLaw1(Maybe.of, maybeToEither)(Identity.of(Maybe.of('barlow one')));
// Right(Identity('barlow one'))

natLaw2(Either.of, maybeToEither)(Identity.of(Maybe.of('barlow one')));
// Right(Identity('barlow one'))

Transformation naturelle et permutation sont interchangeables, un principe clé en théorie des catégories.

Corollaire pratique :

traverse(A.of, A.of) === A.of;

Cette propriété offre également des avantages d'optimisation.

En Résumé

Traversable est une interface puissante qui permet de réorganiser les types avec une dextérité intuitive. Elle offre un contrôle précis des effets et prépare le terrain pour les Monoides qui unifient le tout, pilier de la programmation fonctionnelle.

Exercices

Considérez les éléments suivants :

// httpGet :: Route -> Task Error JSON

// routes :: Map Route Route
const routes = new Map({ '/': '/', '/about': '/about' });

Pratiquons !

Utilisez l'interface Traversable pour modifier la signature de getJsons en Map Route Route → Task Error (Map Route JSON) // getJsons :: Map Route Route -> Map Route (Task Error JSON) const getJsons = map(httpGet);

---

Définissons cette fonction de validation :

// validate :: Player -> Either String Player
const validate = player => (player.name ? Either.of(player) : left('must have name'));

Pratiquons !

En utilisant Traversable et validate, modifiez startGame pour ne démarrer que si tous les joueurs sont valides // startGame :: [Player] -> [Either Error String] const startGame = compose(map(map(always('game started!'))), map(validate));

---

Enfin, ces utilitaires système :

// readfile :: String -> String -> Task Error String
// readdir :: String -> Task Error [String]

Pratiquons !

Utilisez Traversable pour réorganiser et aplatir les Tasks & Maybe imbriqués // readFirst :: String -> Task Error (Maybe (Task Error String)) const readFirst = compose(map(map(readfile('utf-8'))), map(safeHead), readdir);