Haskell Language
traversable

introduzione

Instantiating Functor e Foldable per una struttura Traversable

import Data.Traversable as Traversable

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

Ogni Traversable struttura può essere fatto un Foldable Functor utilizzando i fmapDefault e foldMapDefault funzioni che si trovano in Data.Traversable .

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault è definito eseguendo traverse nel Identity funtore applicativa.

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 è definito usando il functor applicativo Const , che ignora il suo parametro mentre accumula un valore monoidale.

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)

Un'istanza di Traversable per un albero binario

Le implementazioni della traverse solito assomigliano a un'implementazione di fmap innalzata in un contesto 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

Questa implementazione esegue una traversata in ordine dell'albero.

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

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

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

L'estensione DeriveTraversable consente a GHC di generare istanze Traversable base alla struttura del tipo. Possiamo variare l'ordine di attraversamento scritto da macchina modificando il layout del costruttore 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'

Attraversando una struttura al contrario

Un attraversamento può essere eseguito nella direzione opposta con l'aiuto del Backwards applicativo Backwards , che capovolge un applicativo esistente in modo che gli effetti composti avvengano in ordine inverso.

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 può essere messo in uso in una " traverse rovesciata". Quando l'applicativo sottostante di una chiamata traverse viene capovolto con Backwards , l'effetto risultante avviene in ordine inverso.

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'

Il nuovo tipo Reverse si trova in Data.Functor.Reverse.

Definizione di 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 strutture t sono contenitori finitari di elementi a azionabili mediante un funzionamento effectful "visitatore". La funzione visitatore f :: a -> fb esegue un effetto collaterale su ogni elemento della struttura e traverse gli effetti collaterali utilizzando Applicative . Un altro modo di vedere le cose è che sequenceA dice Traversable strutture permuta con Applicative s.

Trasformare una struttura attraversabile con l'aiuto di un parametro di accumulo

Le due funzioni mapAccum combinano le operazioni di piegatura e mappatura.

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

Queste funzioni generalizzano fmap in quanto consentono ai valori mappati di dipendere da ciò che è accaduto in precedenza nella piega. Generalizzano foldl / foldr , nel senso che mappa la struttura a posto così come la riduzione a un valore.

Ad esempio, tails possono essere implementate utilizzando mapAccumR e la sua sorella inits possono essere implementate utilizzando 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 è implementato attraversando nel mapAccumL applicativo di State .

{-# 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 funziona eseguendo mapAccumL al contrario .

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

Strutture traversabili come forme con contenuti

Se un tipo t è Traversable allora i valori di ta possono essere divisi in due parti: la loro "forma" e il loro "contenuto":

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

dove i "contenuti" sono gli stessi di quelli che "visiteresti" utilizzando un'istanza Foldable .

Andando in una direzione, da ta a Traversed ta non richiede altro che Functor e Foldable

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

ma tornare utilizza la funzione traverse modo cruciale

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

Le leggi Traversable richiedono quell'interruzione break . recombine e recombine . break sono entrambi identità. In particolare, questo significa che ci sono esattamente gli elementi numerici giusti nei contents per riempire completamente la shape senza avanzi.

Traversed t è Traversable stessa. L'implementazione della traverse funziona visitando gli elementi utilizzando l'istanza di Traversable dell'elenco e quindi ricollegando la forma inerte al risultato.

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

Trasposizione di un elenco di elenchi

Notando che la zip traspone una tupla di liste in una lista di tuple,

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

e la somiglianza tra i tipi di transpose e 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)
--                                                |       |
--                                                +--->---+

l'idea è di usare la struttura Traversable e Applicative [] per distribuire la sequenceA come una sorta di zip n-ari , comprimendo insieme tutte le liste interne in senso stretto.

[] Impostazione predefinita "scelta prioritaria" Applicative istanza Applicative non è appropriata per il nostro uso - abbiamo bisogno di un Applicative "zippy". Per questo usiamo il nuovo tipo ZipList , che si trova 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)

Ora otteniamo la transpose gratuitamente, attraversando l' 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]]