Réductions avec Foldable, en Haskell
Voir aussi : video youtube - code source
Une réduction est un calcul réalisé en considérant tous les éléments d’une collection de données (on “réduit” les données en un résultat final). Par exemple en Haskell, on peut utiliser la fonction foldr
pour calculer une réduction sur une liste. La classe de types Foldable
permet d’implémenter des réductions classiques et d’étendre le principe de la réduction à d’autres types.
Rappel sur la réduction
Concrètement une réduction consiste à prendre successivement chaque élément de la collection pour mettre à jour un accumulateur, grâce à une fonction de mise à jour.
Exemple en JavaScript
La réduction suivante calcule la somme des éléments [2,4,5]
, en appliquant une fonction d’addition à partir de l’accumulateur initial 0
.
> [2,4,5].reduce((a,x) => a+x, 0)
11
Ici le parcours des éléments est fait de gauche à droite, ce qui revient à faire le calcul :
> ((0 + 2) + 4) + 5
11
La réduction permet d’implémenter différents calculs, par exemple le produit de nombres ou la concaténation de textes :
> [2,4,5].reduce((a,x) => a*x, 1)
40
> ["foo", "bar", "baz"].reduce((a,x) => a+x, "")
'foobarbaz'
Exemple en Haskell
Haskell propose plusieurs fonctions pour calculer une réduction, par exemple pour calculer la somme des éléments d’une liste :
> foldr (+) 0 [2, 4, 5]
ghci11
La fonction foldr
parcourt la liste de droite à gauche, le calcul précédent est donc équivalent à :
> 2 + (4 + (5 + 0))
ghci11
De même, on peut implémenter d’autres calculs avec des réductions :
> foldr (*) 1 [2, 4, 5]
ghci40
> foldr (++) "" ["foo", "bar", "baz"]
ghci"foobarbaz"
La classe de types Foldable
Définition
La classe Foldable représente les types sur lesquels on peut calculer des réductions :
class Foldable t where
:: Monoid m => t m -> m
Data.Foldable.fold foldMap :: Monoid m => (a -> m) -> t a -> m
foldr :: (a -> b -> b) -> b -> t a -> b
...
:: t a -> [a]
Data.Foldable.toList null :: t a -> Bool
length :: t a -> Int
elem :: Eq a => a -> t a -> Bool
maximum :: Ord a => t a -> a
minimum :: Ord a => t a -> a
sum :: Num a => t a -> a
product :: Num a => t a -> a
{-# MINIMAL foldMap | foldr #-}
-- Defined in ‘Data.Foldable’
instance Foldable [] -- Defined in ‘Data.Foldable’
instance Foldable Maybe -- Defined in ‘Data.Foldable’
...
Ainsi, pour instancier Foldable
sur un type, il suffit d’écrire son implémentation de foldr
ou de foldMap
et on obtient gratuitement des fonctions comme toList
, sum
, elem
utilisables sur ce type. Haskell fournit déjà des instances de Foldable
sur les listes, sur Maybe
, etc.
> 42 `elem` (Just 42)
ghciTrue
> 42 `elem` (Just 0)
ghciFalse
> 42 `elem` Nothing
ghciFalse
Utilisation avec des monoïdes
La réduction s’applique assez naturellement aux monoïdes : l’accumulateur initial correspond à l’élément neutre et la fonction d’accumulation correspond à la loi de composition interne (voir le tuto 87).
Par exemple, si on utilise le monoïde Sum, on peut calculer la somme d’une liste en utilisant mempty
et (<>)
:
> getSum $ foldr (<>) mempty [Sum 2, Sum 4, Sum 5]
ghci11
Avec foldMap, on peut même mapper la construction des Sum
sur une liste d’entiers et utiliser automatiquement le monoïde correspondant :
> getSum $ foldMap Sum [2, 4, 5]
ghci11
En fait, Haskell est même capable de déterminer le monoïde à utiliser d’après le contexte (ici getSum
); on peut donc simplement utiliser fold :
> getSum $ fold [2, 4, 5]
ghci11
Tout ceci est aussi valable pour n’importe quel monoïde, par exemple Product
ou String
:
> getProduct $ fold [2, 4, 5]
ghci40
> fold ["foo", "bar", "baz"]
ghci"foobarbaz"
Exemple : arbre binaire de recherche
On peut écrire nos propres types et leur faire instancier la classe Foldable
. Prenons l’exemple d’un arbre binaire de recherche, où pour tout noeud, les éléments de son sous-arbre gauche (resp. de son sous-arbre droit), les éléments sont inférieurs (resp. supérieurs) à la valeur du noeud.
Implémentation basique
Pour implémenter un ABR, on peut définir un type Tree a
avec une fonction insérant un élément dans un arbre et une fonction construisant un arbre à partir d’une liste :
data Tree a
= Leaf
| Node (Tree a) a (Tree a)
deriving (Show)
insert :: Ord a => a -> Tree a -> Tree a
Leaf = Node Leaf e Leaf
insert e Node left x right) =
insert e (if e <= x
then Node (insert e left) x right
else Node left x (insert e right)
fromList :: Ord a => [a] -> Tree a
= foldr insert Leaf fromList
On peut également écrire manuellement des fonctions similaires à celles implémentées dans la classe Foldable
, par exemple :
toList :: Tree a -> [a]
Leaf = []
toList Node left x right) = toList left ++ [x] ++ toList right
toList (
sum' :: Num a => Tree a -> a
Leaf = 0
sum' Node left x right) = sum' left + x + sum' right
sum' (
elem' :: Ord a => a -> Tree a -> Bool
Leaf = False
elem' _ Node left x right)
elem' e (| e < x = elem' e left
| e > x = elem' e right
| otherwise = True
Exemple d’utilisation :
> t1 = fromList [3, 2, 5, 4]
ghci
> t1
ghciNode (Node Leaf 2 (Node Leaf 3 Leaf)) 4 (Node Leaf 5 Leaf)
> toList t1
ghci2,3,4,5]
[
> sum' t1
ghci14
> elem' 1 t1
ghciFalse
> elem' 2 t1
ghciTrue
Instance de Foldable
On peut instancier la classe Foldable
pour notre type Tree a
, par exemple en écrivant la fonction foldr
:
instance Foldable Tree where
-- foldr :: (a -> b -> b) -> b -> Tree a -> b
foldr _ acc Leaf = acc
foldr f acc (Node left x right) =
let acc1 = foldr f acc right
= f x acc1
acc2 = foldr f acc2 left
acc3 in acc3
Alternativement, on peut écrire foldMap
au lieu de foldr
et profiter du fait qu’on accumule via un monoïde :
instance Foldable Tree where
-- foldMap :: Monoid m => (a -> m) -> Tree a -> m
foldMap _ Leaf = mempty
foldMap f (Node left x right) = foldMap f left <> f x <> foldMap f right
Dans tous les cas, on obtient alors automatiquement des implémentations de toList
, sum
, elem
.
On notera cependant que certaines implémentations, notamment elem
, feront un parcours complet de l’arbre, donc sans l’optimisation permise par les ABR. On pourrait écrire une implémentation explicite de elem
mais on a besoin de comparer les éléments, ce qui n’est pas autorisé par le type de elem
(on a Eq a
mais il nous faudrait Ord a
) :
elem :: (Foldable t, Eq a) => a -> t a -> Bool
Instance dérivée
L’extension DeriveFoldable
permet de dériver automatiquement Foldable
pour notre type Tree a
:
{-# Language DeriveFoldable #-}
import Data.Foldable
import Data.Monoid
data Tree a
= Leaf
| Node (Tree a) a (Tree a)
deriving (Foldable, Show)
insert :: Ord a => a -> Tree a -> Tree a
Leaf = Node Leaf e Leaf
insert e Node left x right) =
insert e (if e <= x
then Node (insert e left) x right
else Node left x (insert e right)
fromList :: Ord a => [a] -> Tree a
= foldr insert Leaf fromList
On obtient ainsi une instance à Foldable
équivalente, sans avoir à l’écrire nous-même.
Conclusion
Les réductions sont des algorithmes très classiques qui consistent à effectuer un calcul en considérant successivement chaque élément d’une collection de données.
Haskell propose des fonctions qui implémentent l’algorithme général de réduction (foldr
, foldl
, foldMap
…). À partir de cela, il propose également des fonctions plus spécifiques (elem
, sum
, toList
…) et s’intègre bien avec la notion de monoïde (Sum
, Product
, String
…).
Tout ceci est implémenté via la classe de types Foldable
, que l’on peut instancier pour nos propres types, explicitement ou automatiquement (avec l’extension DeriveFoldable
).
Quelques liens :