Introduction

Ce document est destiné à devenir, à terme, une série complète de fiches sur le langage Haskell.

Elles n’ont pas la prétention d’être un support d’apprentissage autonome, et présupposent une connaissance, même élémentaire, du langage. Elles ont vocation à présenter, de manière extrêmement synthétique, pour mémoire ou référence, l’essentiel de Haskell, et pas à se substituer à un apprentissage sérieux.

J’ai décidé de préparer ces fiches pour combler un manque dans la documentation sur Haskell. Les livres dont je dispose sur le langage sont soit trop superficiels, soit insuffisamment systématiques. Certains présentent une version superficelle du langage, d’autres, les plus élaborés, souffrent au contraire du syndrome de l’enseignant-passionné-mais-pas-méthodique : ils ne cessent de s’interrompre et de proposer des apartés hors de propos qui mobilisent soudainement des notions qui ne seront explicitées que plusieurs chapitres plus loin. (Ce qui précède est devenu nettement moins vrai avec le livre d’Allen et Moronuki).

Ces fiches tentent donc une présentation plus rigoureusement systématique, mais sans prétention pédagogique. L’ordre d’exposition n’y est absolument pas linéaire, et l’organisation tente d’être plus logique que pédagogique.

Ce travail est à peine entamé. À terme, il devrait offrir un aperçu complet du langage, et de quelques une des extensions de GHC.

L’environnement de développement

GHC

L’implémentation de Haskell la plus répandue est GHC, The Glasgow Haskell Compiler. GHC fournit trois binaires: un compilateur (ghc), un interpréteur (runghc) et un interpréteur ligne à ligne (REPL) (ghci).

GHC

GHC reconnaît les formats d’entrées suivants:

Extension Format
.hs Source Haskell
.lhs Source Literate Haskell

La liaison d’un exécutable avec ghc a tendance à être très longue, d’une part parce que ld est en général assez lent, d’autre part parce que ghc tend à lier plus de symboles qu’il n’est nécessaire. Pour accélérer la liaison (uniquement lors du développement et pas pour produire des binaires destinés à la distribution, évidemment), on peut invoquer ghc avec le drapeau -dynamic.

Outils de construction

Haskell dispose de deux outils de construction (make): Cabal et Stack. Ces deux outils implémentent la même spécification pour automatiser le processus de compilation. Ils tentent chacun d’assurer la reproductibilité de la compilation et de la résolution des dépendances, et de faciliter la cohabitation de plusieurs versions de la même librairie.

Le nom «Cabal» (pour Common Architecture for Building Applications and Libraries) désigne à la fois:

  • Une spécification
  • Une librairie
  • Une implémentation (cabal-install)

Stack est une implémentation alternative de la même spécification. Un projet construit pour n’importe lequel des deux moteurs devrait compiler avec l’autre.

Dans la mesure où les deux outils gèrent les dépendances de façon différente, et d’une façon différente de GHC, ils fournissent chacun une commande pour invoquer le REPL avec les bonnes dépendances: cabal repl et stack repl.

Les fichiers .cabal

Cabal et Stack

  1. Cabal (cabal-install)

    Cabal-le-programme est le programme de construction «historique» de Haskell. Jusqu’à la version 1.24, il reposait sur un mécanisme de «bac à sable» pour isoler les dépendances nécessaires à un projet. Le coût de cette solution était une initialisation relativement longue pour les projets ayant de nombreuses dépendances. À partir de la version 1.24, Cabal fournit new-build, qui utilise un dépôt centralisé.

  2. Stack

    Stack est un moteur de construction alternatif qui suit la spécification Cabal, mais fournit sa propre implémentation.

    (???)

Le langage

Conditionnels

Haskell connaît deux structures conditionnelles: if et case.

if

Une clause if est une expression, pas une structure de contrôle. La syntaxe est if a then b else c, où a est une expression de type Bool, b et c des expressions d’un type quelconque. Si a est vraie, l’expression vaut b, sinon c.

Comme c’est une expression, on peut affecter son résultat directement à une variable:

a = if even x then "pair" else "impair"

Que if soit une primitive du compilateur n’est justifié que par le gain de clarté qu’il apporte. L’implémenter en Haskell directement est trivial:

if' :: Bool -> a -> a
if' True a _ = a
if' _ _ b = b

case

Évaluation paresseuse

let a = [1..] -- a est la liste de l'ensemble des entiers positifs
let b = map ((^^) 2) a

L’évaluation paresseuse a un prix, qui est une plus grande consommation de mémoire : au lieu d’évaluer 2 + 2, Haskell stocke un thunk, c’est à dire en gros un calcul différé. Mais sur les gros traitements récursifs, l’accumulation de thunk peut entrainer rapidement un débordement de mémoire. La commande seq force l’évaluation et permet d’éviter un débordement de mémoire.

L’évaluation paresseuse obéit à des règles strictes.

Il est possible de déterminer avec précision si une expression va être évaluée, et si oui quand. C’est parce qu’il est garanti qu’une expression dont le résultat n’est pas utilisé ne sera pas évaluée qu’on peut, par exemple, programmer des opérateurs logiques court-circuitants directement en Haskell, ou manipuler des suites infinies.

Polymorphisme

Polymorphisme paramétrique

N’importe quelle fonction ou type peut accepter des paramètres d’un type non défini. Sa signature remplace dans ce cas le nom d’un type par un paramètre de type, qui commence par une minuscule.

  1. Types polymorphiques

    Le type Maybe, qui représente une valeur possible, est un exemple de type polymorphique. Il a deux constructeurs : Nothing et Just a. Nothing ne prend pas de paramètre, et représente l’absence de valeur. Just a prend un paramètre du type quelconque a.

    ghci> :type Just 3
    Just 3 :: Num a => Maybe a
    ghci> :type Just "Une chaîne"
    Just "Une chaîne" :: Maybe [Char]
    ghci> :type Nothing
    Nothing :: Maybe a
  2. Fonctions polymorphiques

    Une fonction peut accepter, ou renvoyer, des types non-définis.

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

    «Théorèmes gratuits»

    Comme une fonction polymorphique n’a pas accès au type réel de son paramètre, on peut déduire (au sens strict) ce qu’elle peut faire à sa seule signature.

    • La fonction head :: [a] -> a n’a pas accès au type a, et par conséquent ne peut ni construire un nouvel a, ni modifier un des a de la liste [a] d’entrée: elle doit en renvoyer un tel quel. On peut donc déduire que head b `elem` b.

    • La fonction fst :: (a, b) -> a ne peut rien faire d’autre que renvoyer le premier élément de la paire qui lui est passée, et ignorer le second.

    (Wadler 1989) explicite le soubassement logico-mathématique de ce principe et montre des applications à des cas beaucoup plus complexes que ces quelque exemples.

Polymorphisme ad hoc

Modules

Écrire un module

Un module a le même nom que le fichier .hs qui le contient, et ce nom commence par une majuscule. La déclaration de module a la syntaxe suivante:

-- MyModule.hs
module Mod ( x, y, z ) where -- code

Cette déclaration exporte les identifiants x, y et z du code qui la suit. On exporterait la totalité des noms en enlevant la parenthèse, et aucun en la laissant vide.

Ce n’est pas une erreur de syntaxe que de ne pas respecter la règle nom du module = nom du fichier. Un tel module ne serait simplement pas importable, puisque le compilateur ne saurait pas où le trouver.

TODO exporter un type mais pas ses constructeurs.

Importation de modules

D’après (Hudak, Peterson, Fasel 2000).
-- Commande                       -- Importé
import Mod                        -- x, y, z, Mod.x, Mod.y, Mod.z
import Mod ()                     -- Uniquement les instances, voir ci-dessous.
import Mod (x,y)                  -- x, y, Mod.x, Mod.y
import qualified Mod              -- Mod.x, Mod.y, Mod.z
import qualified Mod (x,y)        -- Mod.x, Mod.y
import Mod hiding (x,y)           -- z, Mod.z
import qualified Mod hiding (x,y) -- Mod.z
import Mod as Foo                 -- x, y, z, Foo.x, Foo.y, Foo.z
import Mod as Foo (x,y)           -- x, y, Foo.x, Foo.y
import qualified Mod as Foo       -- Foo.x, Foo.y, Foo.z
import qualified Mod as Foo (x,y) -- Foo.x, Foo.y

Même sans importer aucun nom (c’est le cas de import Mod ()), tout import importe les instances de classes de types définies dans le module importé.

Modules et instances

Les instances de classes de types définies dans un module sont toujours exportées et importées, quels que soient les noms explicitement importés ou exportés, et même s’il n’y en a aucun.

Le prélude

Le Prélude (Prelude) est la librairie fondamentale d’Haskell. Contrairement aux autres modules, il est importé implicitement (cette importation peut néanmoins être contrôlée avec une clause import explicite).

L’implémentation de référence est écrite en Haskell.

Il est particulièrement intéressant de noter que parmi les définitions fournies par le Prélude, un certain nombre sont, dans la plupart des langages procéduraux, définies au niveau du compilateur. Parmi celles-ci, on trouve notamment les opérateurs booléens court-circuitants, dont l’implémentation est rendue triviale par le principe d’évaluation paresseuse.

Noms exportés par le Prélude d’Haskell 2010 (Marlow 2010).
module Prelude (
    module PreludeList, module PreludeText, module PreludeIO,
    Bool(False, True),
    Maybe(Nothing, Just),
    Either(Left, Right),
    Ordering(LT, EQ, GT),
    Char, String, Int, Integer, Float, Double, Rational, IO,

    -- These built-in types are defined in the Prelude, but
    -- are denoted by built-in syntax, and cannot legally
    -- appear in an export list.
    -- List type: []((:), [])
    -- Tuple types: (,)((,)), (,,)((,,)), etc.
    -- Trivial type: ()(())
    -- Functions: (->)

    Eq((==), (/=)),
    Ord(compare, (<), (<=), (>=), (>), max, min),
    Enum(succ, pred, toEnum, fromEnum, enumFrom, enumFromThen,
     enumFromTo, enumFromThenTo),
    Bounded(minBound, maxBound),
    Num((+), (-), (*), negate, abs, signum, fromInteger),
    Real(toRational),
    Integral(quot, rem, div, mod, quotRem, divMod, toInteger),
    Fractional((/), recip, fromRational),
    Floating(pi, exp, log, sqrt, (**), logBase, sin, cos, tan,
         asin, acos, atan, sinh, cosh, tanh, asinh, acosh, atanh),
    RealFrac(properFraction, truncate, round, ceiling, floor),
    RealFloat(floatRadix, floatDigits, floatRange, decodeFloat,
          encodeFloat, exponent, significand, scaleFloat, isNaN,
          isInfinite, isDenormalized, isIEEE, isNegativeZero, atan2),
    Monad((>>=), (>>), return, fail),
    Functor(fmap),
    mapM, mapM_, sequence, sequence_, (=<<),
    maybe, either,
    (&&), (||), not, otherwise,
    subtract, even, odd, gcd, lcm, (^), (^^),
    fromIntegral, realToFrac,
    fst, snd, curry, uncurry, id, const, (.), flip, ($), until,
    asTypeOf, error, undefined,
    seq, ($!)
  ) where

Programmation lettrée

Haskell fait partie des rares langages à gérer nativement la programmation lettrée. Les fichiers sources ont l’extension .lhs (au lieu de .hs) et les blocs de code peuvent être délimités de deux façons

  • Soit par des chevrons, à la façon de Markdown. Les lignes de code commencent par un >. Chaque bloc de code doit être précédé d’au moins une ligne vide.
  • Soit par des délimiteurs d’environnement La$\TeX$: Le code est entouré de \begin{code} et \end{code}.

Idiomes

Composition et point-free style

  1. Composition

    La fonction de composition est (.) :: (b -> c) -> (a -> b) -> a -> c.

  2. Point-free

    Le point-free style est un style de programmation dans lequel une fonction n’identifie pas les arguments sur lesquels elle s’opère, mais compose simplement d’autres fonctions.

    Par exemple:

    reverseTail, reverseTailPointFree :: [a] -> [a]
    reverseTail x = reverse . tail $ x
    reverseTailPointFree = reverse . tail

Récursivité

  1. Récursivité en queue

Folds

Les différents folds sont des catamorphismes.

Associatif à droite:

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Associatif à gauche:

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

Associatif à gauche, évaluation stricte:

Data.List.foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b

Cette version

Voir le tutorial de (Hutton 1999).

Extensions GHC

Les extensions s’activent fichier par fichier avec le pragma {-# LANGUAGE NameOfExtension #-}

EmptyDataDecls

Déclarations de type sans constructeurs: data S, data S a. La seule valeur possible est alors \bot.

FlexibleContexts
FlexibleInstances
GeneralizedNewtypeDeriving
MagicHash

Autorise # comme suffixe pour les identifiants. Généralement utilisé pour les types et les valeurs natives (unboxed): par exemple, GHC.Prim déclare Int#.

MultiParamTypeClasses

Classes de type avec plusieurs arguments: class Monad m => VarMonad m v where…

NegativeLiterals
OverlappingInstances
UnicodeSyntax

Autorise à remplacer certaines séquences ASCII par des caractères Unicode: pour ->, pour *, etc.

TypeSynonymInstances

qsd

Types

Généralités

Haskell connaît deux espèces essentielles de type: les types de données et les types de fonctions. Cette section traite uniquement des premiers, les seconds ont leur propre section.

Nommage des identifiants

En Haskell, la casse du premier caractère d’un identifiant a une importance. Un nom de type ou un constructeur de type commencent toujours par une majuscule, un nom de fonction ou de variable par une minuscule.

Types produits, types sommes, types exponentielles

Si on comprend qu’un type est un ensemble (de valeurs possibles), on voit aisément pourquoi on parle de types produit ou somme:

  • Une alternative entre type (data OuBien = Chaine String | Entier Int) a pour cardinal la somme des cardinaux des types qui le constituent.

  • Une combinaison de types (data ChaineEtEntier = ChaineEtEntier String Int) a pour cardinal le produit des cardinaux des types qui le constituent.

  • Une application de types (TypeA -> TypeB) a pour cardinal le cardinal du type du résultat élevé à la puissance du cardinal du type du paramètre. Le cardinal de a -> b est donc #b#a\#b^{\#a}.

(Le cardinal d’un type défini avec data est simplement une somme de produits.)

Types élémentaires

Haskell fournit un grand nombre de types élémentaires, dont les plus importants sont résumés dans ce tableau:

Types numériques essentiels, d’après (O’Sullivan, Stewart, Goerzen 2008).
Type Description
Double Virgule flottante, double précision
Float Virgule flottante, simple précision
Integer Entier signé en précision arbitraire
Int Entier signé à précision fixe, intervalle minimum [229;2291][-2^{29} ; 2^{29}-1]
Int8 , Int16, Int32, Int64 Entier signé de nn bits
Word8, Word16, Word32, Word64 Entier non signé de nn bits
Rational, ~Ratio a Nombre rationnel de précision arbitraire

Définition de types

Produits

data Book = NewBook String [String] Int
--                  ^               ^__ Année de publication
--                  |      ^___________ Auteurs
--                  |__________________ Titre

Cette ligne définit un type nommé Book qui fournit un unique constructeur NewBook. Le constructeur NewBook se comporte comme une fonction qui prend trois paramètres et qrenvoie un Book: NewBook :: String -> [String] -> Int -> Book. Pour construire un nouveau Book, on écrit donc book = NewBook "Critique of Pure Reason" ["Immanuel Kant"] 1781. Dans cette syntaxe, les arguments du constructeur sont positionnels et doivent être fournis dans l’ordre de la déclaration.

Il est légal et très courant, quand un type ne fournit qu’un seul constructeur, de donner à ce constructeur le nom du type. On aurait alors data Book = Book String [String] Int. L’exemple précédent les distingue par souci de clarté, mais n’est pas vraiment idiomatique.

Sommes

Un type somme présente une alternative en offrant plusieurs constructeurs.

data Bool = True | False
data Maybe a = Nothing | Just a

Les types produits et sommes ne sont pas mutuellement exclusifs: data Something = This String Int | That String Bool.

Syntaxe d’enregistrement

La syntaxe d’enregistrement permet de nommer les champs.

data Book = Book {
  bookTitle :: String, -- bookTitle :: Book -> String
  bookAuthors :: [String], -- bookAuthors :: Book -> [String]
  bookYear :: Int -- bookYear :: Book -> Int
  }

Un type qui utilise cette syntaxe peut être instantié avec des arguments positionnels ou des arguments nommés. Ces derniers peuvent être fournis dans n’importe quel ordre:

crp = Book "Critique de la Raison Pure" ["Immanuel Kant"] 1781
tlp = Book {
  bookYear = 1921,
  bookAuthors = ["Ludwig Wittgenstein"],
  bookTitle = "Tractatus Logico-Philosophicus"
  }

Il définit automatiquement une fonction accesseur pour chacun de ses champs. Le type Book ci-dessus fournit ainsi trois fonctions bookYear :: Book -> Int, bookAuthors :: Book -> [String] et bookTitle :: Book -> String:

ghci>  bookYear tlp 1921

Enfin, il permet de construire une nouvelle valeur à partir des champs d’une valeur existante:

rp = tlp {bookTitle = "Recherches philosophiques", bookYear=1953}

Les types comme contextes

(???) (On peut considérer un type algébrique comme un contexte sémantique pour un type natif.)

Types récursifs

Un type peut faire référence à lui-même. On peut construire un type liste identique au type natif de la façon suivante:

data List a = Empty | Cons a (List a) list = (Cons 1 (Cons 2 (Cons 3
Empty)))

Un arbre binaire:

data BTree a = Node a (BTree a) (BTree a) | Empty deriving Show

Synonymes de types

Haskell permet de définir des synonymes pour des types existants. Les synonymes de type permettent d’augmenter la lisibilité du code ou de masquer des détails d’implémentation. Contrairement aux types définis avec data, les informations des synonymes ne sont pas conservées à la compilation.

type

type crée un synonyme d’un type existant. Le synonyme et le type auquel ils renvoient sont interchangeables.

type ObjectId = Int16

Les synonymes créés avec type peuvent servir:

  • À clarifier le sens des champs dans les types personnalisés sans accesseurs (type ISBN = Int pour un type Book, par exemple):
type Authors = [String]
type Title = String
type ISBN = Int
type Year = Int
data Book2 = Authors Title Year ISBN
  • Comme notation abrégée pour des types complexes fréquemment utilisés.
type Weird = (Int -> String) -> (Int -> Int) -> [Int] -> [(Int, String, Int)]

newtype

Le mot-clé newtype permet de dupliquer un type, et crée un type distinct de l’original. Les synonymes créés avec newtype ne sont pas substituables avec le type dont ils sont synonymes. De plus, il n’appartiennent pas automatiquement aux types de classe de ce dernier. Leur syntaxe est très proche de celle de data:

newtype MyType = MyType Int
  • Contrairement à data, newtype:

    • n’autorise qu’un seul constructeur et un seul champ.

    • ne conserve pas les informations du type après la compilation. Dans le programme compilé, MyType ci-dessus est traité comme un

    simple Int:

  • Contrairement à type,

    • il ne maintient pas la substituabilité du nouveau type et du type dont il est un synonyme. Alors que type sert à faciliter la lecture, newtype est plutôt utilisé pour masquer l’implémentation. Il permet notamment de masquer un type sous-jacent sans la perte de performances liée à l’usage de data, par exemple: newtype ResourceHandle = ResourceHandle Int16. Comme il est possible à un module de n’exporter que le type mais pas le constructeur, un programme peut recevoir et transmettre des données de type ResourceHandle sans connaître leur type réel.

    • Il permet aussi, sans perte de performances, de fournir des instances différentes d’une unique classe de type pour un type donné:

      -- Data.Monoid
      
      -- Booléen selon la conjonction
      newtype All = All { getAll :: Bool }
        deriving (Eq, Ord, Read, Show, Bounded)
      instance Monoid All where
        mempty = All True
        mappend (All x) (All y) = All (x && y)
      
      -- Booléen selon la disjonction
      newtype Any = Any { getAny :: Bool }
        deriving (Eq, Ord, Read, Show, Bounded)
      instance Monoid Any where
        mempty = Any False
        mappend (Any x) (Any y) = Any (x || y)
  • Enfin, newtype est strict.

Classes de type

Les classes de type ne sont pas des classes au sens que ce terme possède en POO. Elles sont plus proches de ce qu’on nomme des interfaces : elles décrivent des fonctions pour lesquelles un type qui appartient à la classe fournit une implémentation.

Créer une classe de type

class Parsable a where
  parse :: String -> a

Une implémentation par défaut peut être fournie. La classe de type Eq par exemple est définie comme:

class Eq a where
  (==), (/=) :: a -> a -> Bool
  x /= y     =  not (x == y)
  x == y     =  not (x /= y)

Dériver une classe de type

Version triviale:

data CanardLapin = { canard :: Bool, lapin :: Bool }
instance Show CanardLapin where
  show (CanardLapin True False) = "Seulement un canard"
  show (CanardLapin False True) = "Seulement un lapin"
  show _ = "Un canard lapin!"

Plus marrant: dériver un type higher-kinded en fonction de son paramètre:

{-# LANGUAGE FlexibleInstances #-}

class Magique a where
  magie :: a -> a

data CanardLapin' = Canard | Lapin

instance Functor f, Magique m => Magique (f m) where
  magie = fmap magie

instance Magique CanardLapin' where
  magie Canard = Lapin
  magie Lapin = Canard

À certaines classes de type sont associées des lois (lois des foncteurs, des monades, etc.) que le compilateur ne peut pas nécessairement contrôler. Il est donc possible de construire des instances pathologiques de classes de type sans recevoir d’avertissement du compilateur. Autrement dit, le système des classes de types est en partie formel, en partie contractuel. Il convient de vérifier les dimensions contractuelles dans la documentation de la classe de type. Il est aussi possible, dans une certaine mesure, d’automatiser la vérification de conformité.

Dérivation automatique

Les types crées avec data et newtype peuvent dériver automatiquement certaines classes avec le mot clé deriving:

data Something = Something Integer Integer
  deriving (Show)

La dérivation automatique est implémentée au niveau du compilateur, et ne concerne que quelques classes de type du Prélude.

Sortes

Les Kinds sont aux types ce que les types sont aux valeurs. Autrement dit, c’est le type d’un constructeur de type. Un type ordinaire a (???)

Fonctions

Fonctions et variables

Haskell n’a pas de notion de variable au sens qu’a ce terme en programmation procédurale. Il est possible d’assigner une expression ou une valeur à un nom, avec la syntaxe nom = expression, mais nom est immuable, et est donc plus proche d’une constante (c’est une variable au sens mathématique du terme).

En combinant ceci avec les principes de transparence référentielle, d’évaluation paresseuse et d’application partielle, on voit facilement qu’il n’existe aucune différence stricte entre une fonction et une ariable, donc qu’il n’existe pas de variables. Par exemple:

a = 3 * 2
times3 x = 3 * x
b = times3 2
c = 6

Ici, times3 est une fonction, a, b et c des variables. Dans la mesure où la valeur d’aucune n’est évaluée tant qu’elle n’est pas utilisée, la variable a a strictement la même valeur que b, qui n’est pas 6, mais le thunk 3 * 2.

Cette identité n’est vraie que des fonctions pures. Les fonctions impures, comme par exemple getLine, peuvent évidemment renvoyer un résultat différent à chaque invocation. Voir la section portant sur les entrées-sorties.

La suite de cette fiche ne s’intéresse donc qu’aux fonctions, puisque les «variables» n’en sont qu’un cas particulier.

Signature de type

La signature a la forme f :: TypeA -> TypeRet, ce qui signifie que la fonction prend un paramètre de type TypeA et renvoie une valeur de type TypeRet.

Une fonction définie avec plusieurs paramètres a pour signature f :: TypeA -> TypeB -> TypeC -> TypeRet. Cette syntaxe est explicitée fiche . Les fonctions d’ordre supérieur utilisent les parenthèses pour indiquer qu’elles prennent une autre fonction en paramètre. Par exemple, le type map :: (a -> b) -> [a] -> [b] se lit : map prend comme premier paramètre une fonction quelconque x :: a -> b. Une variable ou une fonction sans paramètres a pour type nom :: Type.

Définition de fonctions

Une fonction se définit de la façon suivante:

add :: Int -> Int -> Int -- Signature de type, généralement optionnel.
add a b = a + b

Une fonction infixe se définit en entourant son nom de parenthèses, comme pour l’utiliser en préfixe:

(+/) a b = a + b + a / b

Fonctions préfixes et infixes

Une fonction est dite préfixe si son nom est placé avant ses arguments, et infixe si son nom est placé entre ses arguments. map est une fonction préfixe, + est infixe. La distinction est syntaxique, et se fait au niveau des caractères qui constituent le nom de la fonction.

  1. Fonctions infixes

    Une fonction infixe a un nom composé uniquement de symboles non alphanumériques: +, * ou >>= sont infixes. On peut utiliser une fonction infixe comme préfixe en entourant son nom de parenthèses : (+) 1 1.

  2. Fonctions préfixes

    Une fonction préfixe a un nom composé de caractères alphanumériques. map, elem ou foldr sont préfixes. On peut utiliser une fonction préfixe comme infixe en entourant son nom de : 1 `elem` [1..10].

Fonctions locales

On peut définir des fonctions dont la visibilité est limitée à une fonction. C’est utile pour définir des constantes, ou fournir des fonctions utilitaires qui n’ont pas besoin d’être disponibles au niveau du module. Haskell propose deux syntaxes: let, qui place les variables locales avant le code de la fonction, et where, qui les positionne après.

circLet :: Fractional a => a -> a
circLet radius = let pi = 3.14
             diam = 2 * radius
         in pi * diam
circWhere :: Fractional a => a -> a
circWhere radius = pi * diam
  where pi   = 3.141592653589793
    diam = 2 * radius
  • Le choix de l’une ou de l’autre syntaxe est une question de goût et de lisibilité.

  • On peut les imbriquer: une fonction locale peut à son tour définir des fonctions locales, etc.

  • La visiblité des fonctions locales est limitée à la définition englobante.

Fixité (précédence et associativité)

L’associativité et la précédence sont collectivement nommées «fixité». La fixité d’une fonction infixe (et de n’importe quelle fonction préfixe dans sa forme infixe, comme `elem`) est fixée par une déclaration infixl (associatif à gauche), infixr (associatif à droite) ou infix (non-associatif), suivie de l’ordre de précédence compris entre 0 et 9 et du nom de la fonction:

(+/) :: Num a => a -> a -> a
infixl 9 +/
(+/) a b = a + b + a / b

Il est possible de définir la fixité d’une fonction locale, directement dans la clause let ou where où elle est définie.

Paramètres, motifs et gardes

Paramètres

  1. Déconstruction de types composites

    «Déconstruire» un argument d’une fonction permet d’obtenir directement les arguments du constructeur. Par exemple, la fonction suivante déconstruit un constructeur de paire (tuple de deux éléments) pour en intervertir les termes:

    toggle :: (a, b) -> a
    toggle (x, y) = (y, x)

    Un paramètre non utilisé peut être remplacé par un _:

    duplFirst :: (a, b) -> (a, a)
    duplFirst (x, \_) = (x, x)

    On n’a pas besoin du second membre de la paire: on la décompose donc en évitant de nommer cet élément.

    De la même façon, si le paramètre est un Maybe, on peut récupérer directement sa valeur en déconstruisant Just:

    double :: Maybe Int -> Int
    double (Just x) = x * 2
  2. Motifs nommés.

    On peut avoir besoin de déconstruire un paramètre selon un motif en conservant le paramètre entier. Les motifs nommés permettent d’éviter des suites déconstruction-reconstruction redondantes. La fonction suffixes (d’après (O’Sullivan, Stewart, Goerzen 2008, p. 103)) renvoie tous les suffixes d’une liste. Elle peut s’écrire:

    suffixes :: [a] -> [[a]] suffixes xs(/:xs') = xs : suffixes xs'
    suffixes / = []

Filtrage par motif et gardes

Le filtrage par motifs et l’emploi de gardes permettent de proposer différentes implémentations d’une même fonction selon les paramètres qui y sont passés, de façon similaire à l’emploi de cas en notation mathématique :

f(x)={f(x1)+xsi x>01sinon f(x) = \begin{cases} f(x-1) + x & \text{si } x > 0 \\ 1 & \text{sinon} \end{cases}

Le filtrage par motifs permet de choisir une implémentation selon le type et dans une certaine mesure la valeur des paramètres, les gardes selon une expression arbitraire.

Le filtrage par motif et les gardes permettent de définir plusieurs cas qui se recouvrent. Par exemple, une fonction peut fournir une implémentation pour n’importe quelle liste, et une autre pour n’importe quelle liste non vide. Haskell utilise toujours la première implémentation qui s’applique aux paramètres, dans l’ordre de déclaration : il faut donc déclarer les moins générales en premier.

Filtrage par motifs

Le filtrage par motifs permet de filtrer selon un constructeur ou selon une valeur arbitraire.

  1. Par constructeur.

    Le filtrage par constructeurs permet de sélectionner quel constructeur d’un type algébrique correspond à quelle implémentation.

    maybeIntToStr :: Maybe Int -> String
    maybeIntToStr (Just a) = show a
    maybeIntToStr Nothing = "NaN"
    mySum :: (Num a) => [a] -> a
    mySum (x:xs) = x + mySum xs
    mySum [] = 0
  2. Par valeur littérale.

    Le filtrage par valeur littérale est le plus simple. Il choisit une implémentation si un paramètre a une valeur déterminée.

    compte :: String -> String -> Int -> String
    compte singulier pluriel 0 = "Aucun(e) " ++ singulier
    compte singulier pluriel 1 = "Un(e) " ++ singulier
    compte singulier pluriel quantite = show quantite ++ " " ++ pluriel

    Une valeur littérale doit être littérale et ne peut pas, pour des raisons syntaxiques, être une variable. Un nom de variable dans une définition de fonction est toujours un paramètre de la fonction, jamais un filtre par valeur.

  3. Paramètres ignorés.

    Certaines implémentations d’une fonction peuvent ne pas faire usage de tous les paramètres. On ignore un paramètre dans la définition avec le symbole _: La fonction compte ci-dessus pourrait s’écrire:

    compte :: String -> String -> Int -> String
    compte singulier _ 0 = "Aucun(e) " ++ singulier
    compte singulier _ 1 = "Un(e) " ++ singulier
    compte _ pluriel quantite = show quantite ++ " " ++ pluriel

    _ n’est pas un nom de variable mais la mention explicite que le paramètre ne sera pas utilisé.

Gardes

Un garde est une expression de type Bool. Si l’expression s’évalue à True, l’implémentation qui suit est utilisée.

Leur syntaxe est:

func args | garde = impl

Par exemple, une fonction qui détermine si un nombre est pair, qui s’implémenterait naïvement sous la forme isEven x = if x `mod` 2 == 0 then True else False peut s’écrire plus lisiblement:

isEven x | x mod 2 == 0 = True
isEven _ = False

La partie à gauche du garde peut être omise si elle est identique à celle qui précède (c’est-à-dire si l’éventuel motif est le même):

isEven x | x mod 2 == 0 = True
         | otherwise = False

otherwise est une variable définie dans le Prélude. Sa valeur est simplement True.

  1. «Pattern guards»

    Haskell 2010 étend la syntaxe des gardes

    gardes :: Int -> String gardes a | odd a, a =mod= 5 == 0 = "Impair et/ou
    multiple de 5" | even a = "Pair mais pas multiple de 5"

    (???)

Application partielle et currying

Une fonction, quel que soit le nombre de paramètres avec lequel elle a été déclarée, ne prend qu’un seul paramètre et renvoie une autre fonction. Le type de +, par exemple, est : Num a => Num a -> Num a -> Num a, ce qui signifie que + prend un premier paramètre d’un type de type Num

Lambdas

Les fonctions anonymes se notent:

\a b c -> a + b + c

Le Prélude fournit quelques fonctions qui peuvent remplacer des formes de lambdas très courantes: const :: a -> b -> a et id :: a -> a.

Données et contrôle

Listes

Cette fiche résume quelques unes des fonctions essentielles applicables à des listes. La plupart sont dans le Prélude, les autres dans Data.List.

Fonctions spécifiques aux listes

(++), (<>) [a] -> [a] -> [a]
head, last [a] -> a
tail [a] -> [a] s
drop, take Int -> [a] -> [a]
dropWhile, takeWhile (a -> Bool) -> [a] -> [a]
span :: (a -> Bool) -> [a] -> ([a], [a]) Regroupe les éléments qui vérifient la fonction dans une liste séparée
group :: Eq a => [a] -> [[a]] Regroupe les éléments identiques
map (a -> b) -> [a] -> [b]~ Applique une fonction sur chaque élément
zip [a] -> [b] -> [(a, b)]
zip3 [a] -> [b] -> [c] -> [(a, b, c)]
zipWith (a -> b -> c) -> [a] -> [b] -> [c]
zipWith3 (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d] Généralisé à n: zipWith4, zipWith5

Généralisées aux foncteurs

concatMap (a -> [b]) -> [a] -> [b]
fmap Functor f => (a -> b) -> f a -> f b

Traits

Foldable

Un Foldable est un conteneur dont les éléments peuvent être «repliés» en une valeur unique. Informellement, c’est un type qui implémente foldr, mais la définition est beaucoup plus dense:

class Foldable t where
    {-# MINIMAL foldMap | foldr #-} -- Ce pragma signifie que foldMap ou
                                    -- foldr suffisent à définir une instance.
    fold :: Monoid m => t m -> m
    fold = foldMap id

    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

    foldr :: (a -> b -> b) -> b -> t a -> b
    foldr f z t = appEndo (foldMap (Endo #. f) t) z

    foldr' :: (a -> b -> b) -> b -> t a -> b
    foldr' f z0 xs = foldl f' id xs z0
      where f' k x z = k $! f x z

    foldl :: (b -> a -> b) -> b -> t a -> b
    foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

    foldl' :: (b -> a -> b) -> b -> t a -> b
    foldl' f z0 xs = foldr f' id xs z0

    foldr1 :: (a -> a -> a) -> t a -> a
    foldr1 f xs = fromMaybe (errorWithoutStackTrace "foldr1: empty structure")
                    (foldr mf Nothing xs)
      where
        mf x m = Just (case m of
                         Nothing -> x
                         Just y  -> f x y)
    foldl1 :: (a -> a -> a) -> t a -> a
    foldl1 f xs = fromMaybe (errorWithoutStackTrace "foldl1: empty structure")
                    (foldl mf Nothing xs)
      where
        mf m y = Just (case m of
                          Nothing -> y
                         Just x  -> f x y)

    toList :: t a -> [a]
    {-# INLINE toList #-}
    toList t = build (\ c n -> foldr c n t)

    null :: t a -> Bool
    null = foldr (\_ _ -> False) True

    length :: t a -> Int
    length = foldl' (\c _ -> c+1) 0

    elem :: Eq a => a -> t a -> Bool
    elem = any . (==)

    maximum :: forall a . Ord a => t a -> a
    maximum = fromMaybe (errorWithoutStackTrace "maximum: empty structure") .
       getMax . foldMap (Max #. (Just :: a -> Maybe a))

    minimum :: forall a . Ord a => t a -> a
    minimum = fromMaybe (errorWithoutStackTrace "minimum: empty structure") .
       getMin . foldMap (Min #. (Just :: a -> Maybe a))

    sum :: Num a => t a -> a
    sum = getSum #. foldMap Sum

    product :: Num a => t a -> a
    product = getProduct #. foldMap Product

Monoïdes

Mathématiquement, un monoïde est une structure algébrique (un ensemble et une ou plusieurs lois de composition) pourvue d’une opération binaire associative (c’est-à-dire telle que a `op` (b `op` c) = (a `op` b) `op` c) et d’un élément neutre (ici, `x` tel que `op a x = op x a = a`).

En Haskell, Monoid est une classe de type définie de la façon suivante:

class Monoid a where
  mempty  :: a           -- Élément neutre
  mappend :: a -> a -> a -- Opération associative
  mconcat :: [a] -> a    -- Plie une liste selon le monoïde
  mconcat = foldr mappend mempty

-- Data.Monoid
x <> y = mappend x y -- Synonyme infixe

Lois des monoïdes

Les monoïdes ont deux lois:

  1. Loi d’identité:

    x <> mempty = x
    mempty <> x = x

    L’application de mappend sur mempty et une valeur quelconque x retourne toujours x, quel que soit l’ordre des paramètres.

    (Attention, ça n’implique pas qu’un monoïde est nécessairement commutatif! Beaucoup le sont, mais String est un monoïde avec mempty = ""~ et ~mappend = (++), et ++ n’est évidemment pas commutatif.)

  2. Loi d’associativité:

    (x <> y) <> z = x <> (y <> z)

    Informellement: une série d’applications de `mappend` renvoie le même résultat quel que soit l’ordre d’application.

Certains types ont plus d’un monoïde «naturel»: Int (addition et multiplication) et Bool (disjonction et conjonction ) par exemple. Dans ce cas, on crée généralement un synonyme newtype pour chaque monoïde. Data.Monoid définit ainsi deux synonymes de Int, Sum et Product, et deux synonymes de Bool, Any et All.

Foncteurs

Il s’agit d’une classe de type, définie comme suit:

class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  1. fmap id === id: Mapper id sur un foncteur renvoie le même foncteur. Autrement dit, fmap ne peut pas introduire d’autres modifications dans le foncteur que l’application de la fonction.

  2. fmap (f . g) == fmap f . fmap g

La métaphore la plus répandue pour décrire un foncteur consiste à le comparer à une boîte qui contient une valeur. La métaphore est un peu courte. Plus abstraitement, un foncteur est un type de sorte * -> * qui permet l’application d’une fonction sur les données du type encapsulée dans le foncteur. Ainsi -> (la définition de fonction) a un foncteur. Par exemple:

a = (*) 2        -- Application partielle
b = fmap (*2) a  -- fmap
b 2              -- == 8

fmap est une généralisation de map, et peut donc toujours le remplacer.

Traversable

Un Traversable est un foncteur foldable qui peut être traversé «de gauche à droite».

class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}

    -- | Map each element of a structure to an action, evaluate these actions
    -- from left to right, and collect the results. For a version that ignores
    -- the results see 'Data.Foldable.traverse_'.
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse f = sequenceA . fmap f

    -- | Evaluate each action in the structure from left to right, and
    -- and collect the results. For a version that ignores the results
    -- see 'Data.Foldable.sequenceA_'.
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

    -- | Map each element of a structure to a monadic action, evaluate
    -- these actions from left to right, and collect the results. For
    -- a version that ignores the results see 'Data.Foldable.mapM_'.
    mapM :: Monad m => (a -> m b) -> t a -> m (t b)
    mapM = traverse

    -- | Evaluate each monadic action in the structure from left to
    -- right, and collect the results. For a version that ignores the
    -- results see 'Data.Foldable.sequence_'.
    sequence :: Monad m => t (m a) -> m (t a)
    sequence = sequenceA

Lois des Traversable

Foncteurs applicatifs

Un foncteur applicatif est une structure intermédiaire entre un foncteur et une monade.

La classe de type est définie comme suit:

class Functor f => Applicative f where
  -- | Lift a value.
  pure :: a -> f a

  -- | Sequential application.
  (<*>) :: f (a -> b) -> f a -> f b

  -- | Sequence actions, discarding the value of the first argument.
  (*>) :: f a -> f b -> f b
  a1 *> a2 = (id <$ a1) <*> a2
  -- This is essentially the same as liftA2 (const id), but if the
  -- Functor instance has an optimized (<$), we want to use that instead.
  -- | Sequence actions, discarding the value of the second argument.
  (<*) :: f a -> f b -> f a
  (<*) = liftA2 const

Monades

class Applicative m => Monad m where
  -- | Sequentially compose two actions, passing any value produced
  -- by the first as an argument tothe second.
  (>>=) :: forall a b. m a -> (a -> m b) -> m b

  -- | Sequentially compose two actions, discarding any value produced
  -- by the first, like sequencing operators (such as the semicolon)
  -- in imperative languages.
  (>>)        :: forall a b. m a -> m b -> m b
  m >> k = m >>= \_ -> k -- See Note [Recursive bindings for Applicative/Monad]
  {-# INLINE (>>) #-}
  -- | Inject a value into the monadic type.
  return      :: a -> m a
  return      = pure
  -- | Fail with a message.  This operation is not part of the
  -- mathematical definition of a monad, but is invoked on pattern-match
  -- failure in a do expression.
  fail        :: String -> m a
  fail s      = error s

(???) Déf propre, exemples, >>, >>=

Test

Quickcheck

TODO

Entrées et sorties

La gestion des entrées/sorties requiert un traitement spécifique dans un langage fonctionnel. Contrairement aux fonctions pures du langage, les fonctions d’E/S produisent des effets de bord, et violent le principe de transparence référentielle.

Le mécanisme d’E/S d’Haskell est implémenté sous la forme d’une monade nommée IO.

Contrairement à ce qui se fait en général dans les bouquins sur Haskell, il vaut mieux avoir vraiment compris les types, les classes de types et les monades avant de se lancer dans l’exploration du mécanisme d’entrée/sortie.

Fonctions d’entrée sortie de base

Fonctions d’entrée

Prelude h* Fonctions Description
getChar :: IO Char Lit un caractère.
getLine :: IO String Lit une ligne.
getContents :: IO String Lit le contenu d’un fichier.

Fonctions de sortie

Manipulation de fichiers ou de répertoires

Gestion des erreurs

Les types Maybe et Either

Exceptions

Contenu à organiser

TODOs

À intégrer, en vrac:

  • Idiome : Point-free style (RWH 120)
  • Lexique : Liste de paires = association list (RWH 121)
  • Extensions :
    • TypeSynonymInstances
    • OverlappingInstances
  • monomorphisme (RWH 163, Haskell 98 4.5.5)
  • IO
  • Qu’est ce qu’une action (RWH 167, 184)
  • Buffering (RWH 189)
  • Data.ByteString, Data.ByteString.Lazy

Conventions

Une information, pour préciser un point ou renvoyer vers d’autres sources.

Un avertissement généralement important.

Ces boîtes précisent un point concernant le soubassement mathématico-logique de Haskell.

Les lois sont des propriétés attendues des instances de classes de type que le compilateur ne peut pas contrôler.

À propos de ce document

Auteur et mainteneur

Thibault Polge (thibault@thb.lt)

Outils

Ce site est généré avec Hakyll, une librairie de génération de sites statiques écrite en Haskell.

Le thème est compilé avec Sass et utilise Gridle.

Le corps du texte est composé en Open Sans, les titres en Open Sans Condensed.

Les icônes des différentes boîtes proviennent de différentes séries compilées sur IcoMoon

Licence

[[https://i.creativecommons.org/l/by-nc-sa/2.0/fr/80x15.png]]

Pour l’instant, ce travail est mis à disposition sous la (relativement restrictive) Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 2.0 France.

Bibliographie

HUDAK, Paul, PETERSON, John et FASEL, Joseph, 2000. A gentle introduction to haskell: Version 98. [en ligne]. 2000. Disponible à l'adresse : https://www.haskell.org/tutorial/

HUTTON, Graham, 1999. A Tutorial on the Universality and Expressiveness of Fold. Journal of Functional Programming. 1999. Vol. 9, n° 04, pp. 355‑372.

MARLOW, Simon (éd.), 2010. Haskell 2010 Language Report [en ligne]. Disponible à l'adresse : https://wiki.haskell.org/Language_and_library_specification#The_Haskell_2010_report

O’SULLIVAN, Bryan, STEWART, Don et GOERZEN, John, 2008. Real world haskell [en ligne]. O’Reilly. Disponible à l'adresse : http://book.realworldhaskell.org/

WADLER, Philip, 1989. Theorems for free! [en ligne]. 1989. Disponible à l'adresse : http://www.cs.sfu.ca/CourseCentral/831/burton/Notes/July14/free.pdf

Fork me on GitHub