Haskell Language
Vikbar

Introduktion

Anmärkningar

Räkna elementen i en hopfällbar struktur

length räknar förekomsten av element a i en hopfällbar struktur 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 definieras som motsvarande:

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

Observera att detta returtyp Int begränsar de operationer som kan utföras på värden som erhållits genom anrop till length -funktionen. fromIntegral är en användbar funktion som gör att vi kan hantera detta problem.

Vik en struktur i omvänd riktning

Varje vikning kan köras i motsatt riktning med hjälp av Dual monoiden , som vänder en befintlig monoid så att aggregeringen går bakåt.

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)

När den underliggande monoiden i ett foldMap samtal vänds med Dual , körs vecket bakåt; följande Reverse typ definieras i 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

Vi kan använda den här maskinen för att skriva en reverse lista för listor:

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

En instans av vikbar för ett binärt träd

För att omedelbar Foldable måste du ange en definition för åtminstone foldMap eller 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

Denna implementering utför en beställning av trädet.

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

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

ghci> toList myTree
"abc"

DeriveFoldable förlängningen gör att GHC kan generera Foldable instanser baserade på typen av struktur. Vi kan variera ordningen på den maskinskrivna traversalen genom att justera layouten för Node konstruktören.

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"

Att platta en hopfällbar struktur i en lista

toList plattar en Foldable struktur ta i en lista över 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 definieras som motsvarande:

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

Utföra en bieffekt för varje element i en hopfällbar struktur

traverse_ utför en Applicative åtgärd för varje element i en Foldable struktur. Den ignorerar åtgärdens resultat och behåller bara biverkningarna. (För en version som inte kasserar resultat, använd 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_ är traverse_ med argumenten vänt. Det liknar en foreach på ett nödvändigt språk.

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_ kollapsar en Foldable full av Applicative till en enda åtgärd och ignorerar resultatet.

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

traverse_ definieras som likvärdigt med:

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

sequenceA_ definieras som:

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

Dessutom, när den Foldable är också en Functor , traverse_ och sequenceA_ har följande samband:

traverse_ f = sequenceA_ . fmap f

Att platta en hopfällbar struktur till en monoid

foldMap kartlägger varje element i den hopfällbara strukturen till en Monoid och kombinerar dem sedan till ett enda värde.

foldMap och foldr kan definieras i termer av varandra, vilket innebär att instanser av Foldable bara behöver ge en definition för en av dem.

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

Exempel på användning med Product :

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

Definition av vikbar

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

Intuitivt (men inte tekniskt) är Foldable strukturer behållare med element a som tillåter åtkomst till deras element i en väl definierad ordning. foldMap operationen kartlägger varje element i behållaren till en Monoid och kollapsar dem med Monoid strukturen.

Kontrollera om en hopfällbar struktur är tom

null returnerar True om det inte finns några element a i en hopfällbar struktur ta , och False om det finns ett eller flera. Strukturer för vilka null är True har en length på 0.

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

null definieras som likvärdigt med:

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