Haskell Language
Składany

Wprowadzenie

Uwagi

Liczenie elementów składanej struktury

length liczy występowanie elementów a w składanej strukturze 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 jest zdefiniowana jako równoważna:

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

Należy zauważyć, że ten typ zwracany Int ogranicza operacje, które można wykonać na wartościach uzyskanych przez wywołania funkcji length . fromIntegral to przydatna funkcja, która pozwala nam poradzić sobie z tym problemem.

Składanie konstrukcji w odwrotnej kolejności

Każde fałdowanie można uruchomić w przeciwnym kierunku za pomocą Dual monoidu , która odwraca istniejącą monoidę, tak że agregacja przechodzi do tyłu.

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)

Gdy podstawowa foldMap wywołania foldMap zostanie odwrócona za pomocą Dual , fold zostanie cofnięty; następujące Reverse typ jest określony w 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

Możemy użyć tej maszyny do napisania zwięzłego reverse dla list:

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

Instancja Foldable dla drzewa binarnego

Aby utworzyć instancję Foldable , musisz podać definicję co najmniej foldMap lub 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

Ta implementacja wykonuje przemierzanie drzewa w kolejności .

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

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

ghci> toList myTree
"abc"

Rozszerzenie DeriveFoldable umożliwia GHC generowanie Foldable instancji na podstawie struktury typu. Możemy zmieniać kolejność przechodzenia maszynowego przez dostosowanie układu konstruktora 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"

Spłaszczanie struktury składanej do listy

toList spłaszcza się Foldable struktura ta w liście 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 jest zdefiniowany jako równoważny z:

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

Wykonywanie efektu ubocznego dla każdego elementu składanej struktury

traverse_ wykonuje akcję Applicative dla każdego elementu w strukturze Foldable . Ignoruje wynik działania, zachowując tylko skutki uboczne. (W przypadku wersji, która nie odrzuca wyników, użyj 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_ jest traverse_ z argumentami odwrócone. Przypomina pętlę foreach w imperatywnym języku.

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_ zwija Foldable pełen akcji Applicative w jedną akcję, ignorując wynik.

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

traverse_ jest zdefiniowany jako równoważny z:

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

sequenceA_ jest zdefiniowana jako:

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

Ponadto, gdy Foldable jest również Functor , traverse_ i sequenceA_ Functor mają następującą zależność:

traverse_ f = sequenceA_ . fmap f

Spłaszczanie składanej struktury w Monoid

foldMap mapuje każdy element struktury Foldable na Monoid , a następnie łączy je w jedną wartość.

foldMap i foldr można zdefiniować względem siebie, co oznacza, że instancje Foldable muszą podać definicję tylko jednego z nich.

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

Przykładowe użycie z monoidem Product :

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

Definicja składania

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

Intuicyjnie (choć nie technicznie), Foldable struktury są pojemniki z elementami , które umożliwiają dostęp do ich elementów w ściśle określonej kolejności. a Operacja foldMap odwzorowuje każdy element kontenera na Monoid i zwija je za pomocą struktury Monoid .

Sprawdzanie, czy struktura składana jest pusta

null zwraca True jeśli nie ma elementów a w składanej strukturze ta , i False jeśli jest jeden lub więcej. Struktury, dla których null ma null True mają length 0.

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

null jest zdefiniowany jako równoważny z:

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