Classes de types et Functor, en Haskell

Voir aussi : video youtube - video peertube - code source

En plus des types algébriques (ADT), Haskell supporte les classes de types (Type Classes). Celles-ci permettent notamment de spécifier des contraintes sur des types polymorphes. Les classes de types sont un outil très performant en Haskell, qui est utilisé pour définir des structures de haut-niveau comme les Functor et les Monad.

Les classes de types existent également dans d’autres langage, sous des formes généralement moins évoluées. Par exemple, les traits en Rust et les concepts en C++20.

Cet article présente les classes de types en Haskell, à partir de quelques exemples. Il introduit également un exemple de structure évoluée, les Functor.

Les classes de types

Attention, la notion de classe abordée ici ne doit pas être confondue avec celle utilisée en programmation orientée-objet.

Exemple avec un ADT

Pour rappel, un type algébrique permet de définir une somme de types produits. Par exemple, on peut définir un type Figure qui peut prendre des valeurs Rectangle ou des valeurs Disque, de la façon suivante.

data Figure
    = Rectangle Double Double
    | Disque Double

On peut ensuite utiliser ce type et ces valeurs pour définir ou appeler des fonctions.

surface :: Figure -> Double
surface (Rectangle l h) = l * h
surface (Disque r) = pi * r**2

printSurface :: Figure -> IO ()
printSurface = print . surface

main :: IO ()
main = do
    printSurface (Rectangle 2 21)
    printSurface (Disque 3.66)

Les types algébriques sont très pratiques pour représenter un état bien défini à l’avance mais ils peuvent parfois manquer d’extensibilité. Par exemple dans le code précédent, si on veut gérer des figures supplémentaires, il faut modifier le type Figure et potentiellement toutes les fonctions qui l’utilisent.

Exemple avec une Type Class

En simplifiant, une classe de type déclare les fonctions qu’un type doit définir pour instancier cette classe. On peut voir cela un peu comme les interfaces en Java (mais où les instances concrètes sont déterminées à la compilation).

Par exemple, la classe HasSurface suivante déclare la fonction surface (et sa signature).

class HasSurface a where
    surface :: a -> Double

On peut ensuite définir un type Rectangle et lui faire instancier la classe HasSurface en définissant la fonction surface pour le type Rectangle.

data Rectangle = Rectangle Double Double

instance HasSurface Rectangle where
    surface (Rectangle l h) = l * h

De même, on peut définir autant de types que l’on veut et leur faire instancier cette classe.

newtype Disque = Disque Double

instance HasSurface Disque where
    surface (Disque r) = pi * r**2

Enfin, on peut profiter du polymorphisme ad-hoc, pour définir des fonctions utilisables sur tout type de cette classe.

printSurface :: HasSurface a => a -> IO ()
printSurface = print . surface

Ici, printSurface prend en paramètre un type polymorphe a mais qui doit respecter la contrainte d’être de classe HasSurface.

On dit que printSurface prend un a et retourne un IO () où a est un type de classe HasSurface.

La classe Show

La bibliothèque de base de Haskell définit de nombreuses classes de types.

Définition

La classe Show représente les types affichables, c’est-à-dire possèdant une fonction show :: a -> String qui prend un paramètre et retourne un texte.

On peut demander des informations sur Show dans ghci :

Prelude> :info Show
class Show a where
  showsPrec :: Int -> a -> ShowS
  show :: a -> String
  showList :: [a] -> ShowS
  {-# MINIMAL showsPrec | show #-}
  	-- Defined in ‘GHC.Show’
instance Show Int -- Defined in ‘GHC.Show’
instance Show a => Show [a] -- Defined in ‘GHC.Show’
...

Ceci nous indique que :

Instanciation pour un ADT

Illustrons comment instancier la classe Show pour le type algébrique List suivant :

data List = Nil | Cons Int List

Il s’agit donc d’un type récursif qui définit une liste d’entiers de façon classique. La valeur Nil représente la liste vide et la valeur Cons représente l’ajout d’un élément à une sous-liste.

On peut ensuite instancier la classe Show pour notre type List.

instance Show List where
    -- show :: List -> String 
    show Nil = "Nil"
    show (Cons x Nil) = "Cons " ++ show x ++ " Nil"
    show (Cons x xs) = "Cons " ++ show x ++ " (" ++ show xs ++ ")"

Il s’agit donc essentiellement de définir les fonctions demandées par la classe, pour notre type. Pour la classe Show, il suffit de définir la fonction show.

Avec cette instance, on peut désormais utiliser, avec notre List, toutes les fonctions définies pour des types de classe Show, comme par exemple la fonction print.

main :: IO ()
main = do
    print Nil
    print (Cons 1 (Cons 2 Nil))

Instanciation pour un ADT polymorphe

Notre type List précédent représentait des listes d’entiers uniquement. On peut le modifier pour représenter des listes génériques.

data List a = Nil | Cons a (List a)

Ceci signifie simplement, qu’on a désormais un type polymorphe List a et qu’une valeur Cons contient désormais un type a et non obligatoirement un Int.

Il faut donc légèrement modifier l’instance de Show.

instance Show a => Show (List a) where
    -- show :: List a -> String 
    show Nil = "Nil"
    show (Cons x Nil) = "Cons " ++ show x ++ " Nil"
    show (Cons x xs) = "Cons " ++ show x ++ " (" ++ show xs ++ ")"

Dans cette instanciation, on a donc remplacé List par List a. De plus, comme notre définition de show affiche les éléments de la liste (avec show x), il faut également ajouter la contrainte de type que a doit être de classe Show.

On a ainsi une liste générique, que l’on peut afficher si ses éléments sont eux-mêmes affichables.

main :: IO ()
main = do
    print (Nil :: List String)
    print (Cons 1 (Cons 2 Nil) :: List Int)

Instanciation automatique

Haskell permet d’implémenter des instances automatiquement, via deriving. Ainsi, le code précédent se résume en fait à :

data List a = Nil | Cons a (List a)
    deriving Show

main :: IO ()
main = do
    print (Nil :: List String)
    print (Cons 1 (Cons 2 Nil) :: List Int)

La classe Functor

Définition

Intuitivement, les foncteurs sont des types “à l’intérieur desquels on peut appliquer une fonction”.

Prelude> :info Functor
class Functor (f :: * -> *) where
  fmap :: (a -> b) -> f a -> f b
  (<$) :: a -> f b -> f a
  {-# MINIMAL fmap #-}
  	-- Defined in ‘GHC.Base’
instance Functor [] -- Defined in ‘GHC.Base’
instance Functor Maybe -- Defined in ‘GHC.Base’
...

On peut voir cela comme une généralisation de la fonction map des listes Haskell à d’autres types. Pour cela, on a donc la classe Functor, qui déclare la fonction fmap (pour “flat map”).

Ainsi, on peut “fmapper” une fonction sur les éléments d’une liste, ce qui produit une nouvelle liste, de même type ou non, selon la fonction utilisée.

Prelude> fmap (*2) [1..4]
[2,4,6,8]

Prelude> fmap show [1..4]
["1","2","3","4"]

De même, on peut fmapper dans n’importe quel foncteur, par exemple Maybe.

Prelude> fmap (*2) (Just 21)
Just 42
Prelude>

Et on peut définir des fonctions qui “fonctionneront” sur tous les foncteurs.

Prelude> fmap2fois f x = fmap f (fmap f x)

Prelude> fmap2fois (*2) [1..4]
[4,8,12,16]

Prelude> fmap2fois (*2) (Just 3)
Just 12

Remarque sur le HKT

On notera le type de la fonction précédente (et également celui de la fonction fmap en fait) :

Prelude> :t fmap2fois 
fmap2fois :: Functor f => (a -> a) -> f a -> f a

Ici le paramètre de classe (f) est utilisé dans la signature de fonction comme un type polymorphe (f a). Il s’agit en fait d’un type de sorte supérieur (Higher Kinded Types).

Ceci est une fonctionnalité très puissante de Haskell (et sera certainement utilisé dans des articles suivants de ce blog). Pour l’instant, on retiendra juste que la classe Show permet de construire une contrainte à partir d’un type alors que la classe Functor construit une contraint à partir d’une fonction sur des types :

Prelude> :kind Show
Show :: * -> Constraint

Prelude> :kind Functor
Functor :: (* -> *) -> Constraint

Instanciation manuelle

Comme pour toute classe de type, on peut instancier Functor pour nos propres types, par exemple pour List a.

data List a = Nil | Cons a (List a)
    deriving Show

instance Functor List where
    -- fmap :: (a -> b) -> List a -> List b
    fmap _ Nil = Nil
    fmap f (Cons x xs) = Cons (f x) (fmap f xs)

main :: IO ()
main = do
    print (Nil :: List String)
    print $ fmap (*2) (Cons 1 (Cons 2 Nil) :: List Int)
    print $ fmap (*2) [1,2::Int]

On remarquera qu’on instancie bien Functor pour List a et non pour List car, comme expliqué précédemment, un foncteur construit une contrainte à partir d’une fonction sur des types :

*Main> :kind List
List :: * -> *

*Main> :kind (List Int)
(List Int) :: *

Instanciation automatique

Haskell est également capable d’instancier Functor automatiquement, avec l’extension DeriveFunctor.

Finalement, on peut implémenter une liste générique, affichable et “fmappable” avec les quelques lignes suivantes !!!

{-# LANGUAGE DeriveFunctor #-}

data List a = Nil | Cons a (List a)
    deriving (Functor, Show)

main :: IO ()
main = do
    print (Nil :: List String)
    print $ fmap (*2) (Cons 1 (Cons 2 Nil) :: List Int)
    print $ fmap (*2) [1,2::Int]

Autre exemple d’instanciation

Le système de types, classes de types et HKT de Haskell est très pratique pour manipuler des structures arborescentes. Par exemple, pour un arbre binaire générique, affichable et fmappable :

{-# LANGUAGE DeriveFunctor #-}

data Tree a
    = Leaf
    | Node a (Tree a) (Tree a)
    deriving (Functor, Show)

main :: IO ()
main = do
    let t1 = Node (1::Int) (Node 2 Leaf Leaf) (Node 3 Leaf Leaf)
    print t1
    print $ fmap (*2) t1

Conclusion

Une classe de types déclare les fonctions qu’un type de cette classe doit définir. Ceci permet de spécifier des contraintes pour affiner le polymorphisme ad-hoc. En Haskell, les classes de types permettent également de définir des types de sortes supérieures et ainsi d’implémenter des structures évoluées comme les foncteurs. Au delà de cette approche un peu abstraite, ceci permet concrètement d’écrire du code plus expressif, plus concis et plus sûr.