Haskell Language
pieghevole

introduzione

Osservazioni

Conteggio degli elementi di una struttura pieghevole

length conta le occorrenze degli elementi a in una struttura pieghevole 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 è definita come equivalente a:

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

Si noti che questo tipo di restituzione Int limita le operazioni che possono essere eseguite sui valori ottenuti dalle chiamate alla funzione di length . fromIntegral è una funzione utile che ci consente di affrontare questo problema.

Piegare una struttura al contrario

Qualsiasi piega può essere eseguita nella direzione opposta con l'aiuto del Dual monoid , che ribalta un monoide esistente in modo che l'aggregazione vada all'indietro.

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)

Quando il monoide sottostante di una chiamata foldMap viene capovolto con Dual , la piega viene eseguita all'indietro; il seguente tipo di Reverse è definito in 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

Possiamo usare questo macchinario per scrivere un reverse per le liste:

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

Un'istanza di Pieghevole per un albero binario

Per istanziare Foldable è necessario fornire una definizione di almeno 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

Questa implementazione esegue una traversata in ordine dell'albero.

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

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

ghci> toList myTree
"abc"

L'estensione DeriveFoldable consente a GHC di generare istanze Foldable base alla struttura del tipo. Possiamo variare l'ordine di attraversamento scritto da macchina modificando il layout del costruttore 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"

Appiattimento di una struttura pieghevole in un elenco

toList appiattisce un Foldable struttura ta in un elenco di 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 è definito come equivalente a:

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

Esecuzione di un effetto collaterale per ciascun elemento di una struttura pieghevole

traverse_ esegue un'azione Applicative per ogni elemento in una struttura Foldable . Ignora il risultato dell'azione, mantenendo solo gli effetti collaterali. (Per una versione che non scarta risultati, usa 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_ is traverse_ con gli argomenti capovolti. Assomiglia a un ciclo di foreach in un linguaggio 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_ collassa un Foldable pieno di azioni Applicative in una singola azione, ignorando il risultato.

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

traverse_ è definito come equivalente a:

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

sequenceA_ è definito come:

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

Inoltre, quando il Foldable è anche un Functor , traverse_ e sequenceA_ avere la seguente relazione:

traverse_ f = sequenceA_ . fmap f

Appiattimento di una struttura pieghevole in un mono

foldMap mappa ogni elemento della struttura Pieghevole in un Monoid e quindi li combina in un singolo valore.

foldMap e foldr possono essere definite in termini di uno dall'altro, il che significa che i casi di Foldable bisogno solo dare una definizione di uno di loro.

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

Esempio di utilizzo con il Product monoid :

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

Definizione di pieghevole

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 (anche se non tecnicamente), Foldable strutture sono contenitori di elementi a che permettono l'accesso ai loro elementi in un ordine ben definito. L'operazione foldMap mappa ogni elemento del contenitore su un Monoid e li comprime usando la struttura Monoid .

Verifica se una struttura pieghevole è vuota

null restituisce True se non ci sono elementi a in una struttura pieghevole ta e False se ce n'è uno o più. Le strutture per le quali null è True hanno una length pari a 0.

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

null è definito come equivalente a:

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