Chapitre 07 : Hindley-Milner et moi

Quel est votre type ?

Si vous êtes nouveau dans le monde fonctionnel, vous serez rapidement immergé dans les signatures de types. Les types constituent le méta-langage qui permet aux personnes de différents horizons de communiquer de manière concise et efficace. La plupart du temps, elles utilisent le système « Hindley-Milner », que nous allons étudier ensemble dans ce chapitre.

Avec les fonctions pures, les signatures de types possèdent une puissance expressive inégalée par le langage naturel. Ces signatures vous murmurent les secrets intimes d'une fonction. En une ligne compacte, elles révèlent le comportement et l'intention. Nous en dérivons des « théorèmes gratuits ». Les types peuvent être inférés, évitant les annotations explicites. Ils permettent une précision chirurgicale ou restent généraux et abstraits. Utiles pour les vérifications de compilation, ils constituent aussi la meilleure documentation possible. Les signatures de types jouent donc un rôle central en programmation fonctionnelle - bien plus qu'on ne l'imagine.

JavaScript est un langage dynamique, mais cela n'implique pas l'absence de typage. Nous manipulons toujours des chaînes, nombres, booléens, etc. Simplement, l'intégration linguistique manque : cette information reste dans nos têtes. Pas d'inquiétude - nous utiliserons des commentaires pour documenter ces signatures.

Il existe des outils de typage pour JavaScript comme Flow ou le dialecte typé TypeScript. L'objectif de ce livre est de vous équiper pour écrire du code fonctionnel, donc nous nous en tiendrons au système de typage standard utilisé dans les langages FP.

Contes énigmatiques

Des pages poussiéreuses des livres de maths aux white papers, des billets de blog du samedi matin jusqu'au code source lui-même, le système Hindley-Milner est omniprésent. Bien que simple, il mérite une explication approfondie et de la pratique pour maîtriser ce micro-langage.

// capitalize :: String -> String
const capitalize = s => toUpperCase(head(s)) + toLowerCase(tail(s));

capitalize('smurf'); // 'Smurf'

Ici, « capitalize » prend une « String » et retourne une « String ». L'important réside dans la signature, pas l'implémentation.

Dans HM, les fonctions s'écrivent « a -> b » où « a » et « b » sont des variables de type. La signature de « capitalize » se lit donc comme « une fonction de « String » à « String » » : entrée « String », sortie « String ».

Examinons d'autres signatures :

// strLength :: String -> Number
const strLength = s => s.length;

// join :: String -> [String] -> String
const join = curry((what, xs) => xs.join(what));

// match :: Regex -> String -> [String]
const match = curry((reg, s) => s.match(reg));

// replace :: Regex -> String -> String -> String
const replace = curry((reg, sub, s) => s.replace(reg, sub));

« strLength » suit la même logique : « String » en entrée, « Number » en sortie.

D'autres signatures peuvent dérouter. En considérant le dernier type comme valeur de retour : « match » prend « Regex » et « String » pour retourner « [String] ». Mais une subtilité mérite explication.

Regroupons la signature de « match » ainsi :

// match :: Regex -> (String -> [String])
const match = curry((reg, s) => s.match(reg));

Les parenthèses finales révèlent une fonction prenant « Regex » et retournant « String -> [String] ». Le curryfication explique ce comportement : fournir « Regex » donne une fonction attendant « String ». Bien que non obligatoire, cette interprétation éclaire le retour final.

// match :: Regex -> (String -> [String])
// onHoliday :: String -> [String]
const onHoliday = match(/holiday/ig);

Chaque argument consomme un type au début de la signature. « onHoliday » est un « match » déjà lié à « Regex ».

// replace :: Regex -> (String -> (String -> String))
const replace = curry((reg, sub, s) => s.replace(reg, sub));

Comme le montre « replace » avec ses parenthèses complètes, la notation devient redondante. Nous les omettons donc. Traitons « replace » comme une fonction prenant « Regex », « String », « String » et retournant « String ».

Derniers points :

// id :: a -> a
const id = x => x;

// map :: (a -> b) -> [a] -> [b]
const map = curry((f, xs) => xs.map(f));

« id » prend un type quelconque « a » et retourne le même « a ». Les variables « a » et « b » sont arbitraires mais cohérentes : « a -> b » autorise des types différents, alors que « a -> a » impose l'identité typée. Ex : « id » peut être « String -> String », jamais « String -> Bool ».

« map » utilise aussi des variables de type : fonction « a -> b » (identique ou non), tableau de « a », résultat tableau de « b ».

La beauté expressive de cette signature est frappante : elle décrit littéralement le comportement de « map ». Avec une fonction « a -> b » et un tableau de « a », le résultat ne peut être qu'un tableau de « b » obtenu par application élémentaire.

Maîtriser le raisonnement sur les types est crucial en programmation fonctionnelle. Cette compétence rend les articles et documentations plus accessibles, les signatures devenant auto-explicatives. La pratique mène à la fluidité, libérant l'accès à l'information sans documentation superflue.

Quelques exemples supplémentaires pour tester votre décryptage :

// head :: [a] -> a
const head = xs => xs[0];

// filter :: (a -> Bool) -> [a] -> [a]
const filter = curry((f, xs) => xs.filter(f));

// reduce :: ((b, a) -> b) -> b -> [a] -> b
const reduce = curry((f, x, xs) => xs.reduce(f, x));

« reduce » est sans doute la plus expressive. Difficile à appréhender, une explication complémentaire peut aider, mais l'étude autonome reste formatrice.

Examinons la signature : premier argument « (b -> a -> b) » consomme « b » et « a » pour produire « b ». Les arguments suivants (« b » et « [a] ») alimentent cette fonction. Le résultat final « b » correspond à la dernière invocation. L'analyse concorde avec le comportement connu de « reduce ».

Restreindre les possibilités

Les variables de type introduisent la paramétricité : une fonction agit uniformément sur tous les types. Étudions « head » :

// head :: [a] -> a

« head: [a] -> a » ne peut manipuler « a » qu'à travers la structure tableau. Sans connaissance spécifique sur « a », son action se limite à extraire un élément (premier, dernier ou aléatoire). Le nom « head » oriente vers le premier élément.

Autre exemple :

// reverse :: [a] -> [a]

Que fait « reverse » selon sa signature ? Impossible de modifier « a » (sinon « b » apparaîtrait) ou de trier (manque d'information). Seule possibilité : réarranger les éléments de manière uniforme, sans altération. Le polymorphisme restreint fortement les comportements possibles.

Cette restriction permet d'utiliser des moteurs de recherche comme Hoogle pour trouver des fonctions par signature. La densité d'information des signatures est remarquable.

Théorèmes gratuits

Au-delà de l'implémentation, ce raisonnement génère des théorèmes gratuits. Voici des exemples tirés de l'article de Wadler.

// head :: [a] -> a
compose(f, head) === compose(head, map(f));

// filter :: (a -> Bool) -> [a] -> [a]
compose(map(f), filter(compose(p, f))) === compose(filter(p), map(f));

Ces théorèmes émergent directement des types. Le premier stipule qu'appliquer « f » sur le « head » d'un tableau équivaut (et surpasse en performance) à mapper « f » puis prendre le « head ».

Cette évidence intuitive devient formellement vérifiable. L'informatique requiert cette formalisation mathématique pour l'optimisation automatisée.

Le théorème sur « filter » : composer « f » et « p » puis mapper équivaut à mapper « f » avant de filtrer avec « p ». La signature de « filter » garantit la non-altération des éléments (« a » inchangé).

Ces exemples illustrent la généralité du principe. En JavaScript, des outils permettent de déclarer ces règles de réécriture. Les possibilités sont vastes.

Contraintes

Dernier point : les contraintes sur les interfaces.

// sort :: Ord a => [a] -> [a]

La contrainte « Ord a => » indique que « a » doit implémenter l'interface « Ord » (types ordonnables). Cela précise le domaine valide et le comportement de « sort ». On parle de contraintes de types.

// assertEqual :: (Eq a, Show a) => a -> a -> Assertion

Avec « Eq » et « Show », on vérifie l'égalité et la capacité d'affichage des différences.

Les chapitres suivants approfondiront ces concepts.

En résumé

Les signatures Hindley-Milner sont omniprésentes en programmation fonctionnelle. Bien que simples à lire, leur maîtrise demande du temps. Désormais, nous ajouterons des signatures à chaque ligne de code.

Chapitre 08 : Tupperware