Haskell Language
Faltbar

Einführung

Bemerkungen

Zählen der Elemente einer faltbaren Struktur

length zählt die Vorkommen von Elementen a in einer faltbaren 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 ist definiert als äquivalent zu:

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

Beachten Sie, dass dieser Rückgabetyp Int die Operationen beschränkt, die für Werte ausgeführt werden können, die durch Aufrufe der length werden. fromIntegral ist eine nützliche Funktion, die es uns ermöglicht, mit diesem Problem umzugehen.

Eine Struktur in umgekehrter Richtung falten

Jede Falte kann mit Hilfe des Dual Monoids in die entgegengesetzte Richtung ausgeführt werden, wodurch ein vorhandenes Monoid umgedreht wird, sodass die Aggregation rückwärts geht.

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)

Wenn das darunter liegende Monoid eines foldMap Aufrufs mit Dual umgedreht wird, läuft die Falte rückwärts; Der folgende Reverse Typ ist in Data.Functor.Reverse definiert:

newtype Reverse t a = Reverse { getReverse :: t a }

instance Foldable t => Foldable (Reverse t) where
    foldMap f = getDual . foldMap (Dual . f) . getReverse

Wir können diese Maschinerie verwenden, um eine kurze reverse für Listen zu schreiben:

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

Eine Instanz von Foldable für einen Binärbaum

Instanziieren Foldable müssen Sie für mindestens eine Definition liefern foldMap oder 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

Diese Implementierung führt eine In-Reihenfolge-Durchquerung des Baums durch.

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

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

ghci> toList myTree
"abc"

Die DeriveFoldable Erweiterung ermöglicht GHC das Generieren von Foldable Instanzen basierend auf der Struktur des Typs. Wir können die Reihenfolge der Maschine geschriebenen Traversal variieren durch das Layout der Einstellung Node - Konstruktor.

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"

Reduzieren einer faltbaren Struktur in eine Liste

toList flacht eine Foldable Struktur ta in eine Liste von 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 ist definiert als äquivalent zu:

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

Durchführen eines Nebeneffekts für jedes Element einer faltbaren Struktur

traverse_ führt für jedes Element in einer Foldable Struktur eine Applicative Aktion aus. Es ignoriert das Ergebnis der Aktion und behält nur die Nebenwirkungen bei. (Für eine Version, die Ergebnisse nicht verwirft, verwenden Sie 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_ ist traverse_ mit umgedrehten Argumenten. Es ähnelt einer foreach Schleife in einer imperativen Sprache.

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_ fasst eine Foldable Applicative Foldable Aktionen zu einer einzigen Aktion zusammen und ignoriert das Ergebnis.

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

traverse_ ist definiert als äquivalent zu:

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

sequenceA_ ist definiert als:

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

Wenn Foldable auch ein Functor , haben traverse_ und sequenceA_ die folgende Beziehung:

traverse_ f = sequenceA_ . fmap f

Eine faltbare Struktur in ein Monoid glätten

foldMap ordnet jedes Element der faltbaren Struktur einem Monoid und kombiniert sie dann zu einem einzigen Wert.

foldMap und foldr können in Bezug aufeinander definiert werden, was bedeutet, dass Instanzen von Foldable nur für eine von ihnen eine Definition Foldable müssen.

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

Anwendungsbeispiel mit dem Product :

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

Definition von faltbar

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

Foldable Strukturen sind intuitiv (wenn auch nicht technisch) Container von Elementen a die den Zugriff auf ihre Elemente in einer definierten Reihenfolge ermöglichen. Die foldMap Operation ordnet jedes Element des Containers einem Monoid und foldMap sie mithilfe der Monoid Struktur.

Prüfen, ob eine faltbare Struktur leer ist

null zurückkehrt True , wenn es keine Elemente a in einer faltbaren Struktur ta und False , wenn ein oder mehrere sind. Strukturen, für die null True haben eine length von 0.

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

null ist definiert als äquivalent zu:

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