Haskell Language
opvouwbaar

Invoering

Opmerkingen

De elementen van een opvouwbare structuur tellen

length telt het voorkomen van elementen a in een opvouwbare structuur 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 wordt gedefinieerd als gelijk aan:

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

Merk op dat dit retourtype Int de bewerkingen beperkt die kunnen worden uitgevoerd op waarden verkregen door aanroepen van de length . fromIntegral is een nuttige functie waarmee we dit probleem kunnen oplossen.

Een structuur in omgekeerde richting vouwen

Elke vouw kan in de tegenovergestelde richting worden uitgevoerd met behulp van de Dual monoid , die een bestaande monoid omdraait zodat de aggregatie achteruit gaat.

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)

Wanneer de onderliggende monoïde van een foldMap oproep wordt omgedraaid met Dual , loopt de vouw achteruit; het volgende Reverse type is gedefinieerd 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

We kunnen deze machine gebruiken om een korte reverse voor lijsten te schrijven:

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

Een exemplaar van Opvouwbaar voor een binaire boom

Om Foldable , moet u een definitie foldMap voor ten minste foldMap of 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

Deze implementatie voert een in-order doorgang van de boom uit.

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

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

ghci> toList myTree
"abc"

Met de DeriveFoldable extensie kan GHC Foldable instanties genereren op basis van de structuur van het type. We kunnen de volgorde van de machinaal geschreven verplaatsing variëren door de lay-out van de Node constructor aan te passen.

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"

Een opvouwbare structuur afvlakken in een lijst

toList vlakker een Foldable structuur ta in een lijst van 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 wordt gedefinieerd als gelijk aan:

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

Een bijwerking uitvoeren voor elk element van een opvouwbare structuur

traverse_ voert een Applicative voor elk element in een Foldable structuur. Het negeert het resultaat van de actie en behoudt alleen de bijwerkingen. (Gebruik Traversable voor een versie die geen resultaten weggooit.)

-- 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_ met de argumenten omgedraaid. Het lijkt op een foreach lus in een gebiedende taal.

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_ vouwt een Foldable vol met Applicative acties in één actie samen, waarbij het resultaat wordt genegeerd.

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

traverse_ wordt gedefinieerd als gelijkwaardig aan:

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

sequenceA_ is gedefinieerd als:

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

Bovendien, wanneer de Foldable ook een Functor , hebben traverse_ en sequenceA_ de volgende relatie:

traverse_ f = sequenceA_ . fmap f

Een opvouwbare structuur afvlakken tot een monoid

foldMap elk element van de opvouwbare structuur toe aan een Monoid en combineert ze vervolgens tot een enkele waarde.

foldMap en foldr kunnen worden gedefinieerd in termen van elkaar, wat betekent dat instanties van Foldable slechts een definitie voor een van hen hoeven te geven.

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

Voorbeeld gebruik met de Product monoid :

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

Definitie van opvouwbaar

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

Intuïtief (hoewel niet technisch), zijn Foldable structuren containers met elementen a die toegang tot hun elementen in een goed gedefinieerde volgorde mogelijk maken. De bewerking foldMap elk element van de container toe aan een Monoid en vouwt ze samen met behulp van de Monoid structuur.

Controleren of een opvouwbare structuur leeg is

null retourneert True als er geen elementen a in een opvouwbare structuur ta , en False als er een of meer elementen zijn. Structuren waarvoor null True hebben een length van 0.

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

null wordt gedefinieerd als gelijk aan:

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