Haskell Language
Przejezdny

Wprowadzenie

Instancja Functor i składana dla struktury przejezdnej

import Data.Traversable as Traversable

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

Każdy Traversable struktura może być wykonana z Foldable Functor używając fmapDefault i foldMapDefault funkcje znalezione w Data.Traversable .

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault jest definiowany poprzez bieg traverse w fmapDefault aplikacyjnym 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 jest definiowany za pomocą funktora aplikacyjnego Const , który ignoruje jego parametr podczas kumulacji wartości monoidalnej.

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)

Instancja Traversable dla drzewa binarnego

Implementacje traverse zwykle wyglądają jak implementacja fmap uniesiona do kontekstu Applicative .

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

Ta implementacja wykonuje przemierzanie drzewa w kolejności .

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

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

ghci> traverse print myTree
'a'
'b'
'c'

DeriveTraversable rozszerzenie pozwala GHC wygenerować Traversable instancji oparty na strukturze typu. Możemy zmieniać kolejność przechodzenia maszynowego przez dostosowanie układu konstruktora Node .

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'

Przemierzanie struktury w odwrotnej kolejności

Przejście można uruchomić w przeciwnym kierunku za pomocą funktora aplikacyjnego Backwards , który odwraca istniejącą aplikację, dzięki czemu złożone efekty zachodzą w odwrotnej kolejności.

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 może być oddany do użytku w „odwróconym traverse ”. Gdy podstawowa aplikacja wywołania traverse zostanie odwrócona za pomocą opcji Backwards , powstały efekt zachodzi w odwrotnej kolejności.

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'

Reverse nowy typ znajduje się w Data.Functor.Reverse.

Definicja przejezdnego

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 struktury t są finitary pojemniki elementów , które mogą być zasilane z effectful „gościem” działania. a Funkcja odwiedzająca f :: a -> fb wywołuje efekt uboczny na każdym elemencie konstrukcji, a traverse tworzy te efekty uboczne za pomocą Applicative . Innym sposobem patrzenia na to jest sequenceA Traversable mówi sequenceA że struktury Traversable komunikują się z Applicative .

Przekształcanie struktury przejezdnej za pomocą parametru akumulującego

Dwie funkcje mapAccum łączą operacje składania i mapowania.

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

Funkcje te uogólniają fmap , ponieważ pozwalają na odwzorowanie wartości w zależności od tego, co wydarzyło się wcześniej w fmap . Generalizują foldl / foldr , ponieważ odwzorowują strukturę na miejscu, a także redukują ją do wartości.

Na przykład, tails mogą być zaimplementowane za pomocą mapAccumR a jego siostrzane inits mogą być zaimplementowane za pomocą 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 jest implementowany poprzez przechodzenie przez State funktor aplikacyjny.

{-# 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 działa poprzez uruchomienie mapAccumL w odwrotnej kolejności .

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

Przenośne struktury jako kształty z zawartością

Jeśli typ t jest Traversable wówczas wartości ta można podzielić na dwie części: ich „kształt” i „zawartość”:

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

gdzie „treść” jest taka sama jak „odwiedzona” za pomocą instancji Foldable .

Przejście w jednym kierunku, od ta do Traversed ta , nie wymaga niczego oprócz Functor i Foldable

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

ale cofanie się traverse funkcja traverse zasadnicze znaczenie

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

Przepisy Traversable wymagają tego break . recombine i recombine . break to tożsamość. W szczególności oznacza to, że w contents znajduje się dokładnie odpowiednia liczba elementów, aby całkowicie wypełnić shape bez żadnych pozostałości.

Traversed t jest Traversable siebie. Implementacja traverse polega na odwiedzeniu elementów za pomocą instancji listy Traversable a następnie ponownym podłączeniu obojętnego kształtu do wyniku.

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

Transponowanie listy list

Zwracając uwagę, że zip zamienia krotkę list na listę krotek,

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

oraz podobieństwo między rodzajami transpose i 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)
--                                                |       |
--                                                +--->---+

Chodzi o to, aby użyć struktury [] Traversable i Applicative [] celu rozmieszczenia sequenceA jako swego rodzaju n-ary- zip , łącząc wszystkie wewnętrzne listy razem punktowo.

[] „S default«priorytet wybór» Applicative instancja nie jest odpowiednia dla naszego użytku - potrzebujemy«zippy» Applicative . W tym celu używamy ZipList ZipList, znalezionego w 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)

Teraz transpose za darmo, przechodząc przez 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]]