Haskell Language
Durchlauffähig

Einführung

Instantiating Functor und Foldable für eine durchlaufbare Struktur

import Data.Traversable as Traversable

data MyType a =  -- ...
instance Traversable MyType where
    traverse = -- ...

Jede Traversable Struktur kann mit den Funktionen fmapDefault und foldMapDefault in Data.Traversable zu einem Foldable Functor werden.

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault wird durch Ausführen von traverse in der applikativen Funktion " Identity definiert.

newtype Identity a = Identity { runIdentity :: a }

instance Applicative Identity where
    pure = Identity
    Identity f <*> Identity x = Identity (f x)

fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f = runIdentity . traverse (Identity . f)

foldMapDefault wird mit der Const Anwendung definiert, die den Parameter ignoriert, während ein monoider Wert angesammelt wird.

newtype Const c a = Const { getConst :: c }

instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)

Eine Instanz von Traversable für einen binären Baum

Implementierungen von traverse normalerweise aus wie eine Implementierung von fmap die in einen Applicative Kontext gehoben wurde.

data Tree a = Leaf
            | Node (Tree a) a (Tree a)

instance Traversable Tree where
    traverse f Leaf = pure Leaf
    traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r

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> traverse print myTree
'a'
'b'
'c'

Die DeriveTraversable Erweiterung ermöglicht GHC erzeugen Traversable Instanzen auf der Struktur des Typs basiert. 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 (Functor, Foldable, Traversable)  -- also using DeriveFunctor and DeriveFoldable

data Preorder a = PrLeaf
                | PrNode a (Preorder a) (Preorder a)
                deriving (Functor, Foldable, Traversable)

data Postorder a = PoLeaf
                 | PoNode (Postorder a) (Postorder a) a
                 deriving (Functor, Foldable, Traversable)

-- 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> traverse print (inorder myTree)
'a'
'b'
'c'
ghci> traverse print (preorder myTree)
'b'
'a'
'c'
ghci> traverse print (postorder myTree)
'a'
'c'
'b'

Eine Struktur rückwärts durchlaufen

Eine Traversierung kann in die entgegengesetzte Richtung mit Hilfe des Anwendungsfunktors Backwards , wodurch ein vorhandener Anwendungsbereich umgedreht wird, sodass zusammengesetzte Effekte in umgekehrter Reihenfolge stattfinden.

newtype Backwards f a = Backwards { forwards :: f a }

instance Applicative f => Applicative (Backwards f) where
    pure = Backwards . pure
    Backwards ff <*> Backwards fx = Backwards ((\x f -> f x) <$> fx <*> ff)

Backwards in verwenden eine „umgekehrt gebracht werden traverse “. Wenn der zugrunde liegende applicative eines traverse Anruf mit gespiegelt wird Backwards , geschieht der resultierende Effekt in umgekehrter Reihenfolge.

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

instance Traversable t => Traversable (Reverse t) where
    traverse f = fmap Reverse . forwards . traverse (Backwards . f) . getReverse

ghci> traverse print (Reverse "abc")
'c'
'b'
'a'

Der neue Typ Reverse wird unter Data.Functor.Reverse gefunden.

Definition von fahrbar

class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}
    
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse f = sequenceA . fmap f
    
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id
    
    mapM :: Monad m => (a -> m b) -> t a -> m (t b)
    mapM = traverse
    
    sequence :: Monad m => t (m a) -> m (t a)
    sequence = sequenceA

Traversable Strukturen t sind finitäre Behälter von Elementen a , die mit einem effekt „Besucher“ Betrieb betrieben werden kann. Die Besucherfunktion f :: a -> fb führt für jedes Element der Struktur einen Nebeneffekt aus, und die traverse setzt diese Nebeneffekte mit Applicative . Eine andere Sichtweise ist, dass sequenceA sagt, dass Traversable Strukturen mit Applicative s pendeln.

Eine verfahrbare Struktur mit Hilfe eines Akkumulationsparameters transformieren

Die beiden mapAccum Funktionen kombinieren die Vorgänge zum Falten und Mapping.

--                                                       A Traversable structure
--                                                                   |
--                                                     A seed value  |
--                                                             |     |
--                                                            |-|  |---|
mapAccumL, mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
--                                      |------------------|              |--------|
--                                               |                            |
--                       A folding function which produces a new mapped       |
--                         element 'c' and a new accumulator value 'a'        |
--                                                                            |
--                                                            Final accumulator value
--                                                             and mapped structure

Diese Funktionen verallgemeinern fmap , als sie es den zugeordneten Werten ermöglichen, von den fmap in der Falte abzuhängen. Sie verallgemeinern foldl / foldr indem sie die vorhandene Struktur abbilden und sie auf einen Wert reduzieren.

Zum Beispiel tails kann implementiert werden mapAccumR und seine Schwester inits umgesetzt werden kann unter Verwendung von mapAccumL .

tails, inits :: [a] -> [[a]]
tails = uncurry (:) . mapAccumR (\xs x -> (x:xs, xs)) []
inits = uncurry snoc . mapAccumL (\xs x -> (x `snoc` xs, xs)) []
    where snoc x xs = xs ++ [x]

ghci> tails "abc"
["abc", "bc", "c", ""]
ghci> inits "abc"
["", "a", "ab", "abc"]

mapAccumL wird implementiert, indem der State durchlaufen wird.

{-# LANGUAGE DeriveFunctor #-}

newtype State s a = State { runState :: s -> (s, a) } deriving Functor
instance Applicative (State s) where
    pure x = State $ \s -> (s, x)
    State ff <*> State fx = State $ \s -> let (t, f) = ff s
                                              (u, x) = fx t
                                          in (u, f x)

mapAccumL f z t = runState (traverse (State . flip f) t) z

mapAccumR führt mapAccumL in umgekehrter Reihenfolge aus .

mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse

Durchlaufbare Strukturen als Formen mit Inhalt

Wenn ein Typ t Traversable ist, können die Werte von ta in zwei Teile aufgeteilt werden: ihre "Form" und ihre "Inhalte":

data Traversed t a = Traversed { shape :: t (), contents :: [a] }

wo der "Inhalt" derselbe ist, was Sie mit einer Foldable Instanz "besuchen".

Um in eine Richtung zu gehen, von ta zu Traversed ta ist nichts anderes als Functor und Foldable erforderlich

break :: (Functor t, Foldable t) => t a -> Traversed t a 
break ta = Traversed (fmap (const ()) ta) (toList ta)

Beim Zurückfahren wird jedoch die traverse entscheidend verwendet

import Control.Monad.State

-- invariant: state is non-empty
pop :: State [a] a
pop = state $ \(a:as) -> (a, as)

recombine :: Traversable t => Traversed t a -> t a
recombine (Traversed s c) = evalState (traverse (const pop) s) c

Die Traversable Gesetze verlangen , dass die break . recombine und recombine . break sind beide Identität. Dies bedeutet insbesondere, dass im contents genau die richtigen Zahlenelemente vorhanden sind, um die shape vollständig und ohne Überreste auszufüllen.

Traversed t ist selbst Traversable . Die Implementierung von traverse funktioniert, indem die Elemente mit der Instanz von Traversable der Liste Traversable und anschließend die inerte Form dem Ergebnis hinzugefügt wird.

instance Traversable (Traversed t) where
    traverse f (Traversed s c) = fmap (Traversed s) (traverse f c)

Transponieren einer Liste von Listen

Hinweis, dass zip ein Tupel von Listen in eine Liste von Tupeln umwandelt,

ghci> uncurry zip ([1,2],[3,4])
[(1,3), (2,4)]

und die Ähnlichkeit zwischen den Arten der transpose und sequenceA ,

-- transpose exchanges the inner list with the outer list
--           +---+-->--+-+
--           |   |     | |
transpose :: [[a]] -> [[a]]
--            | |     |   |
--            +-+-->--+---+

-- sequenceA exchanges the inner Applicative with the outer Traversable
--                                             +------>------+
--                                             |             |
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
--                                                |       |
--                                                +--->---+

die Idee ist , verwenden [] ‚s Traversable und Applicative Struktur bereitstellen sequenceA als eine Art von n-ary zip , die alle zusammen die inneren Zipping Listen zusammen punktweise.

[] ‚S default‚priorisiert Wahl‘ Applicative Instanz ist für unseren Gebrauch nicht geeignet - wir eine‚flotte‘brauchen Applicative . Dazu verwenden wir den ZipList ZipList-Typ in Control.Applicative .

newtype ZipList a = ZipList { getZipList :: [a] }

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

Jetzt können wir kostenlos transpose , indem wir in der ZipList Applicative ZipList .

transpose :: [[a]] -> [[a]]
transpose = getZipList . traverse ZipList

ghci> let myMatrix = [[1,2,3],[4,5,6],[7,8,9]]
ghci> transpose myMatrix
[[1,4,7],[2,5,8],[3,6,9]]