Fonction pure et fonction totale, en Haskell

Voir aussi : video youtube - video peertube - code source

Les notions de fonctions pures et de fonctions totales sont assez fondamentales en programmation fonctionnelle mais peu connues dans les autres paradigmes de programmation. Ces propriétés sont pourtant très utiles pour écrire du code correct. Le but de ce genre d’approche est que le langage ne permette pas de représenter des états invalides.

Cet article présente ces notions et leur intérêt, et les illustre avec quelques exemples de code, notamment en Haskell.

Notion de fonction pure

Transparence référentielle

Dans un code, une expression respecte la propriété de transparence référentielle si elle peut être remplacée par sa valeur sans changer le comportement du programme.

Soit, par exemple, le code C++ suivant.

int f1(int x) {
    return x*2;
}

int main() {
    std::cout << f1(21) << std::endl;
    // équivalent à : std::cout << 42 << std::endl;

    return 0;
}

Ici la fonction f1 ne fait que retourner un résultat. Ainsi, dans la fonction main, qu’on utilise l’expression f1(21) ou l’expression 42, on obtient des programmes strictement équivalents. On dit que la fonction f1 respecte la propriété de transparence référentielle.

Soit maintenant l’exemple suivant.

int f2(int x) {
    std::cout << "On est dans f2 !\n";    // effet de bord
    return x*2;
}

int main() {
    std::cout << f2(21) << std::endl;
    // différent de : std::cout << 42 << std::endl;
    // (car f2 fait un affichage supplémentaire)

    return 0;
}

Ici la fonction f2 fait également un affichage, en plus de retourner son résultat. Désormais, utiliser l’expression f2(21) ou l’expression 42 dans la fonction main, ne donne pas des programmes équivalents. La fonction f2 ne respecte donc pas la propriété de transparence référentielle.

Fonction pure

Une fonction pure est une fonction qui respecte la propriété de transparence référentielle. Concrêtement, ceci signifie que la fonction ne fait pas d’effet de bord (entrées/sorties, modification de variables globales, etc).

Haskell est un langage fonctionnel pur, c’est-à-dire qu’il n’autorise que des fonctions pures et que ceci est vérifié par le compilateur.

f1 :: Int -> Int
f1 x = x*2

main :: IO ()
main = do
    let v1 = f1 21    -- appelle une fonction pure
    print v1

Dans cet exemple de code, la signature de fonction f1 :: Int -> Int indique que f1 prend un paramètre de type Int et retourne un résultat de type Int. Cette fonction ne peut donc pas faire d’effet de bord. Par exemple, si on essaie de faire un affichage à l’intérieur cette fonction, le compilateur produira une erreur indiquant que f1 ne peut pas faire d’entrée/sortie.

Fonction “monadique”

En réalité, un langage sans aucun effet de bord ne peut pas communiquer avec l’extérieur et est donc d’aucune utilité. Haskell utilise un concept particulier, les monades, pour réaliser des effets de bord.

Ainsi, si on veut faire un effet de bord dans une fonction, il faut l’indiquer dans sa signature et la fonction ne sera alors utilisable que dans un contexte compatible. On dit que la fonction est monadique (ou impure).

f2 :: Int -> IO Int
f2 x = do
    putStrLn "this is f2"
    return (x*2)

main :: IO ()
main = do
    v2 <- f2 21       -- appelle une fonction "monadique"
    print v2

Ici, la signature f2 :: Int -> IO Int indique que f2 prend un paramètre de type Int et produit un résultat de type Int, dans la monade IO. On peut donc faire des entrées/sorties dans f2 mais on ne peut appeler f2 que dans un contexte compatible, à savoir la monade IO (ce qui est le cas pour la fonction main).

Si les monades peuvent sembler inutilement compliquées au premier abord, elles apportent en fait de nombreux avantages. Tout d’abord, la signature indique explicitement si la fonction peut faire un effet de bord et lequel. Le compilateur vérifie que les fonctions sont bien compatibles et qu’on n’introduit pas d’effet de bord implicitement. Enfin, Haskell fournit des fonctionnalités sur les monades, donc utilisables pour tous les effets.

Notion de fonction totale

Fonction totale, fonction partielle

Une fonction totale est définie sur tout l’ensemble de ses paramètres. Une fonction partielle est définie sur une partie seulement de l’ensemble de ses paramètres.

Autrement dit, avec une fonction partielle, il y a certains paramètres qui sont invalides et qui rendent donc le programme incorrect. Ce qui n’est pas le cas avec une fonction totale.

Haskell ne vérifie pas la totalité (il existe des langages, comme Idris, qui le font) et permet donc d’écrire des fonctions partielles. Dans la plupart des langages, on utilise classiquement des assertions, des exceptions ou des tests unitaires, pour gérer des paramètres invalides, à l’exécution. En Haskell, il est également classique d’utiliser le système de type pour implémenter une fonction totale, et donc le vérifier grâce au compilateur.

Exemple de fonction partielle

Un exemple classique est la fonction qui retourne le premier élément d’une liste. Cette fonction est définie sur l’ensemble des listes sauf la liste vide.

-- fonction partiel
myhead1 :: [a] -> a
myhead1 (x : _) = x
myhead1 _ = error "empty list"

Ici, la fonction myhead1 est partielle. Sur la liste [1,2], elle retourne bien la valeur 1.

*Main> myhead1 [1,2]
1

Mais sur la liste vide, elle produit une erreur et le programme crashe.

*Main> myhead1 []
*** Exception: empty list
...

Exemple de fonction totale, via Maybe

Pour éviter les valeurs invalides d’une fonction partielle, on peut changer son type de retour en l’intégrant dans un Maybe. Il s’agit donc d’une valeur optionnelle, indiquant la présence ou l’absence d’un résultat valide. Ce type est de plus en plus courant dans les langages de programmation : Result en Rust, optional en C++, etc.

myhead2 :: [a] -> Maybe a
myhead2 (x : _) = Just x
myhead2 _ = Nothing

Ici la fonction myhead2 est totale. Sur une liste non vide, elle retourne le premier élément, encapsulé dans un Just. Sur une liste vide, elle retourne un Nothing.

*Main> myhead2 [1,2]
Just 1

*Main> myhead2 []
Nothing

Cette méthode évite de crasher le programme avec un paramètre invalide mais nécessite de gérer explicitement les cas d’erreur, à l’exécution, typiquement en testant le résultat de la fonction.

main :: IO ()
main = case myhead2 ([1,2] :: [Int]) of
        Nothing -> putStrLn "liste vide"
        Just v -> print v

Exemple de fonction totale, via NonEmpty

Pour assurer la totalité dès la compilation, on peut définir un type de données correspondant exactement à l’ensemble valide.

Par exemple, on peut définir un type spécifique pour représenter les listes non vides. En fait, ceci existe déjà : la bibliothèque Relude fournit le type NonEmpty et l’opérateur :| (construction de liste non vide).

Ainsi, on peut implémenter une fonction totale prennant en paramètre une liste non vide.

myhead3 :: NonEmpty a -> a
myhead3 (x :| _) = x

Si on utilise cette fonction sur une liste non vide, on obtient directement le résultat voulu.

*Main> myhead3 (1 :| [2])
1

Mais si on essaie de l’utiliser sur une liste vide, on obtient une erreur dès la compilation.

*Main> myhead3 []

<interactive>:4:9: error:
    • Couldn't match expected type ‘NonEmpty a’ with actual type ‘[a0]’
    • In the first argument of ‘myhead3’, namely ‘[]’
      In the expression: myhead3 []
      In an equation for ‘it’: it = myhead3 []
    • Relevant bindings include it :: a (bound at <interactive>:4:1)

Autrement dit, on a rendu l’état invalide “liste vide” impossible à représenter, ce qui évite des erreurs potentielles à l’exécution.

Conclusion

Une fonction pure est une fonction qui retourne uniquement une valeur, sans réaliser d’effet de bord. Une fonction totale est une fonction définie sur toutes les valeurs possibles de ses paramètres.

Respecter ses propriétés permet d’éviter de nombreuses erreurs. De façon classique, on peut le vérifier avec des assertions, des exceptions ou des tests unitaires.

Haskell offre quelques fonctionnalités intéressantes à ce niveau (langage fonctionnel pur, monades, système de types), dans l’objectif de rendre les états invalides impossibles à représenter dans le code.