Introduction à Haskell

(Assez courte)

(Jerzy Karczmarczuk, 2018)

Haskell est un langage fonctionnel pur. Pas de constructions impératives (commandes, instructions). Le programme est composé de définitions de fonctions et de structures de données, de directives (importation, options), et d'une seule expression qui est évaluée, et donne le résultat final.
Une variable affectée, par ex. x=2*17 devient synonymique avec sa valeur, on ne peut plus la changer! Pas d'effets de bord. Pas de boucles for, or while, seulement la récursion. (Et même ça est redondant...)

Exceptions :

  • L'interface interactive maintient un dialogue, on peut faire plusieurs choses, mais chaque nouvelle requête "créé un nouveau monde" superposé sur l'ancien. La communication extérieure est délicate à expliquer aux "profanes"... Les entrées et sorties dans le programme restent fonctionnelles pures, mais le "monde extérieur" peut changer. ("Effet de bord outre tombe")

Une expression est l'application d'une fonction à une donnée, peut-être en cascade (style "curryfié", sans parenthèses):
fun x y z     est équivalent à     ((fun x) y) z.

Les applications partielles sont légitimes et populaires, par ex. la définition :
ad3 = (3 +), équivalente à
ad3 y = 3 + y , ou :    ad3 = \y -> 3+y . -- (\ est "lambda" de Church.)

Le 3 a été "caché" à l'intérieur de la fonction, en constituant une fermeture. Ainsi on peut faire en Haskell les structures de données sans structures de données (même si les listes et d'autres composites existent). Définition d'une paire de 2 objets: secret = pair "Schtroumpf" 42, où on définit : 

pair x y sel = sel x y
La variable secret est opaque, aucun moyen d'accéder à l'intérieur. On peut récupérer le contenu (mais jamais le modifier !) grâce au paramètre sel – la fonction de sélection, par exemple 
first a b = a
second a b = b  
-- et l'expression suivante donne "Schtroumpf"

secret first

mais il faut appliquer la fermeture, elle est ainsi "détruite" dans cette expression.

Haskell est un langage paresseux, une fonction n'évalue pas les arguments dont elle n'a pas (ou pas encore !) besoin. L'expression second (1/0) 7 ne déclenche aucune erreur.
Ce, qui est une structure de données, par ex. une liste, en Haskell est un processus, dont les items sont évalués / exécutés séquentiellement, pendant leur consommation.

Les listes en Haskell : [a,b,c,...] peuvent être construites par l'op. (:),
(x : [a,b]) vaut [x,a,b].

Grâce à la "paresse", les listes peuvent être "infinies", voici deux constructeurs de listes sans fin: 
uns = 1 : uns    -- [1,1,1,...]
suite n = n : suite (n+1)   -- [n, n+1, n+2,...]
mais récupérer quelques éléments est facile, par ex. take 10 (suite 66), où: 
take 0 _ = []    -- prédéfinie
take m (x:reste) = x:(take (m-1) reste)
Les définition paresseuses sont des équations, et le système est capable de les résoudre itérativement (pas toujours). Voici une autre définition de suite: 
zipWith f (x:xs) (y:ys) =f x y : zipWith f xs ys 
-- zipWith est prédéfini 
suite n = ls where ls = n : zipWith (+) uns ls
On peut faire des choses intéressantes...
Qu'est-ce que 
add = zipWith (+)
fs = 0 : 1 : add fs (tail fs)
où tail (a:as) = as? Ce genre de programmes sert à construire les programmes qui bouclent: le serveurs, les systèmes d'exploitation, ou autres applications communicantes. Mais on peut faire des choses plus étonnantes. On n'a pas besoin de récursivité pour écrire les programmes récursifs. On peut construire des points fixes fonctionnels. 
fun g n = if n==0 then 1 else n*g (n-1)
fun n'est qu'un "applicateur" de g, non pas la factorielle. Mais ajoutons la définition d'un point fixe d'une fonction: 
fix f = x where x = f x
ou, en substituant fix f pour x – fix f = f (fix f). Un langage strict (non-paresseux) bombera immédiatement si on lance fix f. Mais ici, si f n'a pas besoin de son argument... Oui, fix fun est la factorielle.
Pour l'instant, c'est presque tout dont nous avons besoin; encore il faut savoir que Haskell est un langage statiquement typé, mais polymorphe, capable de raisonner sur les types quelconques, abstraits.

On peut définir quand même des structures de données concrètes, simples ou composites, contenant des abstractions de la perspective du programmeur, qui doit leur accorder une interprétation. Par exemple : 
data Sexe = Homme | Femme
type Age = Integer    -- Synonyme
data FichePers = Fiche Sexe Age String  
    -- la chaîne : par ex. le nom
Pour Haskell une abstraction est un type arbitraire. Le compilateur peut déduire les dépendances entre eux. Le type de first est : p1 -> p2 -> p1. Haskell peut déduire aussi le type des combinateurs: 
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
Les types peuvent être récursifs, voici une structure équivalente à une liste : 
data Liste a = Vide | Seq a (Liste a)
...
addEl x l = Seq x l  -- ajout d'un élément
-- Pour affichage, Haskell ne peut le deviner...
instance (Show a) => Show (Liste a) where
  show Vide = "Vide"
  show (Seq x y) = show x ++ " ->> " ++ show y

On peut spécifier des structures infinies, par ex. 

data Arbre a = Noeud (Arbre a) a (Arbre a)

On peut les construire sans problèmes, grâce à la paresse, mais la procédure d'affichage sera délicate. Devinez comment le faire. C'était un de mes exercices en L3 Info préférés...

Leçon 2 : Classes

Haskell est un langage pour les calculs sur les abstractions, et il est capable de déduire les types génériques de ces expressions. Mais comment peut-il compiler 
cube x = x*x*x

bonne pour x quelconque? Qu'est ce que c'est "*"? La réponse est un peu "O-O", au sens : les données (en fait : leurs types) soumises aux opérations, spécifient elles-mêmes où chercher le sens de ces opérations. Le type de x doit – justement – être compatible avec la multiplication, il (le type !) doit appartenir à la "classe de nombres" (généralisés).
Si on demande le type de cube, la réponse est : cube :: Num a => a -> a .

C'est comme ça que l'on définit des concepts comme "objets imprimables" (disposant de la fonction show qui construit une chaîne représentant l'objet pour l'oeil humain), ou "objets comparables" (égalité (==); ordre (<)). Et c'est comme ça que nous pouvons définir le concept de, disons, l'"espace vectoriel" – la classe de types admettant l'addition, multiplication par nombre, etc.

Puisque la définition d'une classe, c'est la spécification des opérations qui peuvent être nombreuses, les programmes Haskell ne se réduisent pas à une ligne... Mais – pas de mots-clés structurants (begin - end, etc.).

Il y a des parenthèses, accolades et indentation. Voici le crible d'Eratosthène, calculant tous les premiers : 

primes :: [Int]               -- pour mémoire. 
primes = filterPrime [2..]    -- abrév. : 2, 3, 4, 5, ...
  where filterPrime (p:xs) =  -- param. auto-destructuré
          p : filterPrime [x | x <- xs, x `mod` p /= 0]

La dernière ligne contient une compréhension, une liste engendrée dynamiquement depuis une autre, avec (peut-être) un dispositif de filtrage.

Les formes A where B=..., et aussi let A=... in B, permettent d'inclure des variables locales, temporaires.