Haskell Language
Plegable

Introducción

Observaciones

Contando los elementos de una estructura plegable.

length cuenta las ocurrencias de los elementos a en una estructura plegable 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 se define como equivalente a:

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

Tenga en cuenta que este tipo de retorno Int restringe las operaciones que pueden realizarse en valores obtenidos por llamadas a la función de length . fromIntegral es una función útil que nos permite lidiar con este problema.

Doblando una estructura al revés

Cualquier pliegue se puede ejecutar en la dirección opuesta con la ayuda del Dual monoide , que voltea un monoide existente para que la agregación se desplace hacia atrás.

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)

Cuando el monoide subyacente de una llamada foldMap se invierte con Dual , el pliegue se ejecuta hacia atrás; el siguiente tipo Reverse se define en 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

Podemos usar esta maquinaria para escribir un reverse terso para las listas:

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

Una instancia de Plegable para un árbol binario

Para crear una instancia de Foldable , debe proporcionar una definición de al menos foldMap o 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

Esta implementación realiza un recorrido en orden del árbol.

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

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

ghci> toList myTree
"abc"

La extensión DeriveFoldable permite a GHC generar instancias Foldable basadas en la estructura del tipo. Podemos variar el orden del recorrido escrito por la máquina ajustando el diseño del constructor 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"

Aplanando una estructura plegable en una lista

toList aplana una estructura Foldable ta en una lista de 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 se define como equivalente a:

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

Realización de un efecto secundario para cada elemento de una estructura plegable

traverse_ ejecuta una acción Applicative para cada elemento en una estructura Foldable . Ignora el resultado de la acción, manteniendo solo los efectos secundarios. (Para una versión que no descarta resultados, use 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_ es traverse_ con los argumentos volteados. Se asemeja a un bucle foreach en un lenguaje imperativo.

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_ colapsa un Foldable lleno de acciones de Applicative en una sola acción, ignorando el resultado.

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

traverse_ se define como equivalente a:

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

sequenceA_ se define como:

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

Además, cuando el Foldable también es un Functor , traverse_ y sequenceA_ tienen la siguiente relación:

traverse_ f = sequenceA_ . fmap f

Aplanando una estructura plegable en un monoide

foldMap asigna cada elemento de la estructura plegable a un Monoid , y luego los combina en un solo valor.

foldMap y foldr se pueden definir en términos de otros, lo que significa que las instancias de Foldable solo necesitan dar una definición para uno de ellos.

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

Ejemplo de uso con el Product monoide :

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

Definición de plegable

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

Intuitivamente (aunque no técnicamente), Foldable estructuras son contenedores de elementos de a que permiten el acceso a sus elementos en un orden bien definido. La operación foldMap asigna cada elemento del contenedor a un Monoid y los colapsa utilizando la estructura Monoid .

Comprobando si una estructura plegable está vacía

null devuelve True si no hay elementos a en una estructura plegable ta , y False si hay uno o más. Las estructuras para las cuales null es True tienen una 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 se define como equivalente a:

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