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

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.

Les fichiers `.cabal`

Cabal et Stack

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é.

Stack

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

@TODO

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.

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.

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

Fonctions polymorphiques

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

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

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.

TODO exporter un type mais pas ses constructeurs.

Importation de modules

-- 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.

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

Composition

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

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é

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 \cite{Hutton1999}.

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$.

(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:

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 $[-2²⁹ ; 2²⁹-1]$
`Int8` , `Int16`, `Int32`, `Int64`	Entier signé de $n$ bits
`Word8`, `Word16`, `Word32`, `Word64`	Entier non signé de $n$ 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.

Sommes

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

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

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

@TODO (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

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 @TODO

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.

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 \fsee{partial-application-and-currying @FIXME}. 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.

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.

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 \enconcept{backticks}: 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

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

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 \cite[103]{OSullivan2008}) 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) = \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.

Filtrage par motifs

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

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

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

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

«Pattern guards»

Haskell 2010 étend la syntaxe des gardes \todo{Cette section}

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"

@TODO

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

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:

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.)
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.

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

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

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

@TODO 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

À 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

[[http://creativecommons.org/licenses/by-nc-sa/2.0/fr/][]]

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.

Files

haskell.org

Latest commit

History