Haskell Language
Pliable
Recherche…
Introduction
Foldable
est la classe des types t :: * -> *
qui admettent une opération de pliage . Un pli agrège les éléments d'une structure dans un ordre bien défini, en utilisant une fonction de combinaison.
Remarques
Si t
est Foldable
cela signifie que pour toute valeur ta
nous savons comment accéder à tous les éléments d' a
« de l' intérieur » de ta
dans un ordre linéaire fixe. C'est la signification de foldMap :: Monoid m => (a -> m) -> (ta -> m)
: nous "visitons" chaque élément avec une fonction récapitulative et cassons tous les résumés. Ordre de respect du Monoid
(mais invariant pour différents groupes).
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