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 :

ghci> foldr (+) 0 [2, 4, 5]
11

La fonction foldr parcourt la liste de droite à gauche, le calcul précédent est donc équivalent à :

ghci> 2 + (4 + (5 + 0))
11

De même, on peut implémenter d’autres calculs avec des réductions :

ghci> foldr (*) 1 [2, 4, 5]
40

ghci> foldr (++) "" ["foo", "bar", "baz"]
"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
  Data.Foldable.fold :: Monoid m => t m -> m
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b
  ...
  Data.Foldable.toList :: t a -> [a]
  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.

ghci> 42 `elem` (Just 42)
True

ghci> 42 `elem` (Just 0)
False

ghci> 42 `elem` Nothing
False

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

ghci> getSum $ foldr (<>) mempty [Sum 2, Sum 4, Sum 5]
11

Avec foldMap, on peut même mapper la construction des Sum sur une liste d’entiers et utiliser automatiquement le monoïde correspondant :

ghci> getSum $ foldMap Sum [2, 4, 5]
11

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 :

ghci> getSum $ fold [2, 4, 5]
11

Tout ceci est aussi valable pour n’importe quel monoïde, par exemple Product ou String :

ghci> getProduct $ fold [2, 4, 5]
40

ghci> fold ["foo", "bar", "baz"]
"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
insert e Leaf = Node Leaf e Leaf
insert e (Node left x right) = 
  if e <= x
  then Node (insert e left) x right
  else Node left x (insert e right)

fromList :: Ord a => [a] -> Tree a
fromList = foldr insert Leaf

On peut également écrire manuellement des fonctions similaires à celles implémentées dans la classe Foldable, par exemple :

toList :: Tree a -> [a]
toList Leaf = []
toList (Node left x right) = toList left ++ [x] ++ toList right

sum' :: Num a => Tree a -> a
sum' Leaf = 0
sum' (Node left x right) = sum' left + x + sum' right

elem' :: Ord a => a -> Tree a -> Bool
elem' _ Leaf = False
elem' e (Node left x right)
  | e < x = elem' e left
  | e > x = elem' e right
  | otherwise = True

Exemple d’utilisation :

ghci> t1 = fromList [3, 2, 5, 4]

ghci> t1
Node (Node Leaf 2 (Node Leaf 3 Leaf)) 4 (Node Leaf 5 Leaf)

ghci> toList t1
[2,3,4,5]

ghci> sum' t1
14

ghci> elem' 1 t1
False

ghci> elem' 2 t1
True

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
        acc2 = f x acc1
        acc3 = foldr f acc2 left
    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
insert e Leaf = Node Leaf e Leaf
insert e (Node left x right) = 
  if e <= x
  then Node (insert e left) x right
  else Node left x (insert e right)

fromList :: Ord a => [a] -> Tree a
fromList = foldr insert Leaf

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 :

• Haskell/Foldable
• What’s That Typeclass: Foldable