Haskell Language
flytt

Introduktion

Instantiating Functor och vikbar för en genomgående struktur

import Data.Traversable as Traversable

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

Varje Traversable struktur kan göras till en Foldable Functor med fmapDefault och foldMapDefault funktionerna som finns i Data.Traversable .

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault definieras genom att köra traverse i applikationsfunktorn Identity .

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 definieras med hjälp av Const applikativ funktor, som ignorerar dess parameter medan man samlar ett monoidvärde.

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)

En förekomst av Traversable för ett binärt träd

Implementeringar av traverse ser vanligtvis ut som en implementering av fmap lyfts till ett Applicative sammanhang.

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

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

DeriveTraversable förlängningen gör att GHC kan generera Traversable 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 (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'

Korsa en struktur i omvänd riktning

En genomgång kan köras i motsatt riktning med hjälp av den Backwards tillämpliga funktorn , som vänder ett befintligt applikativ så att komponerade effekter sker i omvänd ordning.

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 kan användas i en "omvänd traverse ". När den underliggande tillämpningen av ett traverse vänds med Backwards , sker den resulterande effekten i omvänd ordning.

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'

Den Reverse nyheten hittas under Data.Functor.Reverse.

Definition av Traversable

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 strukturer t är finitiska behållare av element a som kan drivas med en effektiv "besökare" -operation. Besöksfunktionen f :: a -> fb utför en bieffekt på varje element i strukturen och traverse komposerar dessa biverkningar med hjälp av Applicative . Ett annat sätt att titta på det är att sequenceA Traversable säger att Traversable strukturer pendlar med Applicative s.

Omvandla en genomgående struktur med hjälp av en ackumuleringsparameter

De två mapAccum funktionerna kombinerar funktionerna för vikning och mappning.

--                                                       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

Dessa funktioner generaliserar fmap att de tillåter att de mappade värdena beror på vad som har hänt tidigare i veckan. De generaliserar foldl / foldr att de kartlägger strukturen på plats och reducerar den till ett värde.

Till exempel kan tails implementeras med mapAccumR och dess inits kan implementeras med 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 implementeras genom att köra i den State tillämpliga funktorn.

{-# 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 fungerar genom att köra mapAccumL i omvänd riktning .

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

Korsbara strukturer som former med innehåll

Om en typ t är Traversable kan värden på ta delas upp i två delar: deras "form" och deras "innehåll":

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

där "innehållet" är detsamma som vad du skulle "besöka" med en Foldable inställning.

Att gå en riktning, från ta till Traversed ta kräver inte annat än Functor och Foldable

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

men att gå tillbaka använder traverse avgörande

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

Traversable lagarna kräver att det går break . recombine och recombine . break är båda identiteten. Det betyder särskilt att det finns exakt rätt nummerelement i contents att fylla shape helt utan rester.

Traversed t är Traversable själv. Implementeringen av traverse genom att besöka elementen med listans instans av Traversable och sedan fästa den inerta formen till resultatet.

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

Transponera en lista med listor

Observera att zip överför en tupel av listor till en lista med tuples,

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

och likheten mellan typerna av transpose och 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)
--                                                |       |
--                                                +--->---+

idén är att använda [] : s Traversable och Applicative struktur för att distribuera sequenceA A som en slags n-ary zip , zippa ihop alla inre listor tillsammans punktvis.

[] : s standard "prioriterade val" Applicative instans är inte lämplig för vårt bruk - vi behöver ett "zippy" Applicative . För detta använder vi den ZipList typen ZipList, som finns i 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)

Nu får vi transpose gratis genom att gå igenom ZipList Applicative .

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]]