Semigroup et Monoid, en Haskell
Voir aussi : video youtube - code source
Haskell est un langage de programmation qui s’inspire beaucoup de travaux théoriques en mathématiques et en informatique. Ainsi, certaines notions théoriques sont implémentées explicitement dans Haskell, comme par exemple les notions de semi-groupe et de monoïde.
Illustration avec String et Text
En Haskell, le type String est implémenté par une liste de caractères :
Prelude> :info String
type String = [Char]On peut donc concaténer deux String en utilisant l’opérateur de concaténation
de listes (++) :
Prelude> "foo" ++ "bar"
"foobar"Mais on peut aussi concaténer deux String en utilisant l’opérateur, plus
général, (<>) :
Prelude> "foo" <> "bar"
"foobar"En effet, il existe d’autres façons que les listes pour implémenter un type
texte. Par exemple, le type Text utilise des tableaux; on ne peut donc pas
utiliser l’opérateur (++) mais l’opérateur (<>) si :
Prelude> :set -XOverloadedStrings
Prelude> import Data.Text
Prelude Data.Text> "foo" <> "bar" :: Text
"foobar"On peut voir cela comme une vision utilisateur de la notion de texte : on peut
concaténer deux textes (avec (<>)) indépendamment des détails
d’implémentation (liste ou tableau).
En fait, cette abstraction correspond à la notion de monoïde et permet, par
exemple, d’écrire la fonction myIntercalate suivante, qui construit un texte
(ou plus exactement un monoïde) en intercalant un séparateur donné entre les
textes d’une liste donnée :
myIntercalate :: Monoid a => a -> [a] -> a
myIntercalate _sep [] = mempty
myIntercalate _sep [x] = x
myIntercalate sep (x:xs) = x <> sep <> myIntercalate sep xsComme String et Text sont des monoïdes, on peut utiliser la fonction
précédente avec chacun de ces deux types :
main :: IO ()
main = do
print $ myIntercalate " - " ["foo", "bar", "baz" :: Text]
print $ myIntercalate " - " ["foo", "bar", "baz" :: String]Quelques définitions
En mathématiques
Un magma \((E, \star)\) est une structure algébrique composée d’un ensemble \(E\) et d’une loi de composition interne \(\star\) (c’est-à-dire telle que, pour tout \(x\) et \(y\) de \(E\), \(x \star y\) appartient aussi à \(E\)).
Un semi-groupe est un magma associatif, c’est-à-dire que pour tout \(x\), \(y\) et \(z\) de \(E\), on a \((x \star y) \star z = x \star (y \star z)\).
Un monoïde est un semi-groupe unifère, c’est-à-dire qui possède un élément neutre \(e\) tel que pour tout \(x\) de \(E\), on a \(x \star e = x\) et \(e \star x = x\).
En Haskell
En Haskell, la notion de magma n’est pas vraiment utilisée. En revanche, la
notion de semi-groupe est implémentée par la classe de types
Semigroup
(l’opérateur (<>) est la loi de composition interne du semi-groupe).
Prelude> :info Semigroup
class Semigroup a where
(<>) :: a -> a -> a
...
{-# MINIMAL (<>) #-}
instance Semigroup [a] -- Defined in ‘GHC.Base’
...De même, la notion de monoïde est implémentée par la classe de types
Monoid
à partir de la classe de types Semigroup (mappend est une fonction synonyme
de l’opérateur (<>) et mempty est l’élément neutre du monoïde).
Prelude> :info Monoid
class Semigroup a => Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
{-# MINIMAL mempty #-}
instance Monoid [a] -- Defined in ‘GHC.Base’
...On peut remarquer que les listes instancient Monoid (et donc aussi
Semigroup), ce qui explique pourquoi la fonction myIntercalate de la
section précédente est utilisable avec le type String. De même, le type
Text instancie également Monoid (et est donc utilisable par la fonction
myIntercalate).
Prelude Data.Text> :info Text
data Text
= Data.Text.Internal.Text {-# UNPACK #-}Data.Text.Array.Array
{-# UNPACK #-}Int
{-# UNPACK #-}Int
-- Defined in ‘Data.Text.Internal’
instance Monoid Text -- Defined in ‘Data.Text’
instance Semigroup Text -- Defined in ‘Data.Text’
...Ainsi, on peut profiter de la notion de monoïde pour écrire des fonctions
utilisables avec tous les types implémentant cette notion. Par exemple, la
fonction foldMap de la bibliothèque de base de Haskell :
Prelude Data.Monoid> :info foldMap
class Foldable t where
...
foldMap :: Monoid m => (a -> m) -> t a -> mEt réciproquement, on peut définir des nouveaux types qui instancient
Semigroup ou Monoid et utiliser toutes les fonctions existantes pour ces
deux classes de types. Attention, cependant, l’implémentation doit respecter
les lois des semi-groupe/monoïde mais ceci n’est pas vérifié par le
compilateur.
Exemple avec Sum et Product
En Haskell, les types de nombres comme Int n’instancient pas directement
Monoid car il y a plusieurs monoïdes possibles.
Par exemple, les nombres sommables forment un monoïde, dont la loi de
composition interne est l’addition et l’élément neutre le nombre 0. Ce monoïde
est implémenté en Haskell via le type Sum :
Prelude Data.Monoid> :info Sum
newtype Sum a = Sum {getSum :: a}
...
instance Num a => Monoid (Sum a)
instance Foldable Sum
Prelude Data.Monoid> Sum 1 <> mempty <> Sum 2 <> Sum 4
Sum {getSum = 7}
Prelude Data.Monoid> mconcat [Sum 1, Sum 2, Sum 4]
Sum {getSum = 7}
Prelude Data.Monoid> foldMap Sum [1, 2, 4]
Sum {getSum = 7}De même, les nombres multipliables forment un monoïde, dont la loi de
composition interne est la multiplication et l’élément neutre le nombre 1. Ce
monoïde est implémenté en Haskell via le type Product :
Prelude Data.Monoid> Product 1 <> mempty <> Product 2 <> Product 4
Product {getProduct = 8}
Prelude Data.Monoid> mconcat [Product 1, Product 2, Product 4]
Product {getProduct = 8}
Prelude Data.Monoid> foldMap Product [1, 2, 4]
Product {getProduct = 8}Exemple avec un nouveau type
Comme mentionné précédemment, on peut également créer nos propres types de
semi-groupes ou de monoïdes. Par exemple, on peut représenter un système de
rotations basiques par le type Turn suivant (inspiré d’un exemple du livre
Haskell in Depth) :
data Turn = TNone | TLeft | TRight | TAround
deriving (Show)Si on combine plusieurs Turn, on obtient un Turn : par exemple, deux
rotations à gauche (TLeft) donne une rotation d’un demi-tour (TAround). Et
plus généralement, on peut combiner une suite de Turn “dans n’importe quel
ordre” sans changer le résultat. On a donc une loi de composition interne
associative, donc un semi-groupe :
instance Semigroup Turn where
TNone <> y = y
TLeft <> TLeft = TAround
TLeft <> TRight = TNone
TLeft <> TAround = TRight
TRight <> TRight = TAround
TRight <> TAround = TLeft
TAround <> TAround = TNone
x <> y = y <> xComme la valeur TNone est neutre pour la loi de composition, on a également
un monoïde :
instance Monoid Turn where
mempty = TNoneOn peut ensuite utiliser le type Turn comme n’importe quel semi-groupe/monoïde :
*Main> TLeft <> TNone <> TAround
TRight
*Main> mconcat [TLeft, TNone, TAround]
TRightConclusion
Haskell implémente certaines notions théoriques de mathématiques/informatique, comme le semi-groupe (ensemble muni d’une loi de composition interne associative) et le monoïde (semi-groupe possédant un élément neutre).
Si ces notions peuvent être un peu rebutante pour quelqu’un qui découvre le langage, elles apportent quand même quelques avantages : sémantique bien définie et relativement connue, simplification de preuve d’algorithme, exécution parallèle de code, intégration avec les bibliothèques existantes…
Voir aussi :