Haskell Language
Pliable

Introduction

Remarques

Compter les éléments d'une structure pliable

length compte les occurrences des éléments a dans une structure pliable ta .

ghci> length [7, 2, 9]  -- t ~ []
3
ghci> length (Right 'a')  -- t ~ Either e
1  -- 'Either e a' may contain zero or one 'a'
ghci> length (Left "foo")  -- t ~ Either String
0
ghci> length (3, True)  -- t ~ (,) Int
1  -- '(c, a)' always contains exactly one 'a'

length est définie comme étant équivalente à:

class Foldable t where
    -- ...
    length :: t a -> Int
    length = foldl' (\c _ -> c+1) 0

Notez que ce type de retour Int limite les opérations pouvant être effectuées sur les valeurs obtenues par les appels à la fonction length . fromIntegral est une fonction utile qui nous permet de résoudre ce problème.

Plier une structure en sens inverse

Tout pli peut être exécuté dans la direction opposée à l'aide du monoïde Dual , qui fait basculer un monoïde existant de sorte que l'agrégation retourne en arrière.

newtype Dual a = Dual { getDual :: a }

instance Monoid m => Monoid (Dual m) where
    mempty = Dual mempty
    (Dual x) `mappend` (Dual y) = Dual (y `mappend` x)

Lorsque le monoïde sous-jacent d'un appel foldMap est retourné avec Dual , le pli est en arrière; le type d' Reverse suivant est défini dans Data.Functor.Reverse :

newtype Reverse t a = Reverse { getReverse :: t a }

instance Foldable t => Foldable (Reverse t) where
    foldMap f = getDual . foldMap (Dual . f) . getReverse

Nous pouvons utiliser cette machinerie pour écrire un reverse laconique pour les listes:

reverse :: [a] -> [a]
reverse = toList . Reverse

Une instance de Pliable pour un arbre binaire

Pour instancier Foldable vous devez fournir une définition d'au moins foldMap ou foldr .

data Tree a = Leaf
            | Node (Tree a) a (Tree a)

instance Foldable Tree where
    foldMap f Leaf = mempty
    foldMap f (Node l x r) = foldMap f l `mappend` f x `mappend` foldMap f r
    
    foldr f acc Leaf = acc
    foldr f acc (Node l x r) = foldr f (f x (foldr f acc r)) l

Cette implémentation effectue une traversée dans l'ordre de l'arborescence.

ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)

--    +--'b'--+
--    |       |
-- +-'a'-+ +-'c'-+
-- |     | |     |
-- *     * *     *

ghci> toList myTree
"abc"

La DeriveFoldable extension permet de générer GHC Foldable cas en fonction de la structure du type. Nous pouvons modifier l'ordre du parcours écrit en ajustant la disposition du constructeur de Node .

data Inorder a = ILeaf
               | INode (Inorder a) a (Inorder a)  -- as before
               deriving Foldable

data Preorder a = PrLeaf
                | PrNode a (Preorder a) (Preorder a)
                deriving Foldable

data Postorder a = PoLeaf
                 | PoNode (Postorder a) (Postorder a) a
                 deriving Foldable

-- injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)

preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)

postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x

ghci> toList (inorder myTree)
"abc"
ghci> toList (preorder myTree)
"bac"
ghci> toList (postorder myTree)
"acb"

Aplatir une structure pliable en une liste

toList aplatit une Foldable structure de ta dans une liste d' a s.

ghci> toList [7, 2, 9]  -- t ~ []
[7, 2, 9]
ghci> toList (Right 'a')  -- t ~ Either e
"a"
ghci> toList (Left "foo")  -- t ~ Either String
[]
ghci> toList (3, True)  -- t ~ (,) Int
[True]

toList est défini comme étant équivalent à:

class Foldable t where
    -- ...
    toList :: t a -> [a]
    toList = foldr (:) []

Effectuer un effet secondaire pour chaque élément d'une structure pliable

traverse_ exécute une action Applicative pour chaque élément d'une structure Foldable . Il ignore le résultat de l'action, ne gardant que les effets secondaires. (Pour une version qui ne supprime pas les résultats, utilisez Traversable .)

-- using the Writer applicative functor (and the Sum monoid)
ghci> runWriter $ traverse_ (\x -> tell (Sum x)) [1,2,3]
((),Sum {getSum = 6})
-- using the IO applicative functor
ghci> traverse_ putStrLn (Right "traversing")
traversing
ghci> traverse_ putStrLn (Left False)
-- nothing printed

for_ est traverse_ avec les arguments retournés. Cela ressemble à une boucle foreach dans un langage impératif.

ghci> let greetings = ["Hello", "Bonjour", "Hola"]
ghci> :{
ghci|     for_ greetings $ \greeting -> do
ghci|         print (greeting ++ " Stack Overflow!")
ghci| :}
"Hello Stack Overflow!"
"Bonjour Stack Overflow!"
"Hola Stack Overflow!"

sequenceA_ réduit un Foldable rempli d'actions Applicative en une seule action, en ignorant le résultat.

ghci> let actions = [putStrLn "one", putStLn "two"]
ghci> sequenceA_ actions
one
two

traverse_ est défini comme étant équivalent à:

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ f = foldr (\x action -> f x *> action) (pure ())

sequenceA_ est défini comme suit:

sequenceA_ :: (Foldable t, Applicative f) -> t (f a) -> f ()
sequenceA_ = traverse_ id

En outre, lorsque le Foldable est également un Functor , traverse_ et sequenceA_ ont la relation suivante:

traverse_ f = sequenceA_ . fmap f

Aplatir une structure pliable en un monoïde

foldMap mappe chaque élément de la structure pliable sur un Monoid , puis les combine en une seule valeur.

foldMap et foldr peuvent être définis les uns par rapport aux autres, ce qui signifie que les instances de Foldable ne doivent donner qu'une définition pour l'une d'entre elles.

class Foldable t where
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldMap f = foldr (mappend . f) mempty

Exemple d'utilisation avec le monoïde de Product :

product :: (Num n, Foldable t) => t n -> n
product = getProduct . foldMap Product

Définition de pliable

class Foldable t where
    {-# MINIMAL foldMap | foldr #-}

    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

    -- and a number of optional methods

Intuitivement (mais pas techniquement), Foldable structures sont des conteneurs d'éléments d' a permettant d' accéder à leurs éléments dans un ordre bien défini. L'opération foldMap mappe chaque élément du conteneur sur un Monoid et les réduit en utilisant la structure Monoid .

Vérifier si une structure pliable est vide

null renvoie True s'il n'y a pas d'éléments a dans une structure pliable ta , et False s'il en existe un ou plusieurs. Les structures pour lesquelles null est True ont une length de 0.

ghci> null []
True
ghci> null [14, 29]
False
ghci> null Nothing
True
ghci> null (Right 'a')
False
ghci> null ('x', 3)
False

null est défini comme étant équivalent à:

class Foldable t where
    -- ...
    null :: t a -> Bool
    null = foldr (\_ _ -> False) True