Haskell Language
verplaatsbare

Invoering

Instantiërende functor en opvouwbaar voor een verplaatsbare structuur

import Data.Traversable as Traversable

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

Elke Traversable structuur kan worden gemaakt van een Foldable Functor met de fmapDefault en foldMapDefault functies in Data.Traversable .

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefault wordt gedefinieerd door in de Identity applicative functor traverse .

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 wordt gedefinieerd met behulp van de Const applicatieve functor, die zijn parameter negeert terwijl een monoidale waarde wordt geaccumuleerd.

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)

Een exemplaar van Traversable voor een binaire boom

Implementaties van traverse meestal uit als een implementatie van fmap opgetild in een Applicative context.

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

Deze implementatie voert een in-order doorgang van de boom uit.

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

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

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

Met de extensie DeriveTraversable kan GHC Traversable instanties genereren op basis van de structuur van het type. We kunnen de volgorde van de machinaal geschreven verplaatsing variëren door de lay-out van de Node constructor aan te passen.

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'

Een structuur omgekeerd doorlopen

Een verplaatsing kan in de tegenovergestelde richting worden uitgevoerd met behulp van de Backwards applicative functor , die een bestaande applicative omdraait zodat samengestelde effecten in omgekeerde volgorde plaatsvinden.

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 in een "omgekeerde traverse " worden gebruikt. Wanneer de onderliggende toepassing van een traverse oproep wordt omgedraaid met Backwards , gebeurt het resulterende effect in omgekeerde volgorde.

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'

Het Reverse type is te vinden onder Data.Functor.Reverse.

Definitie van 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 constructies t zijn finitary containers elementen a bedienbare op een effectful "bezoekers" operatie. De bezoekersfunctie f :: a -> fb voert een neveneffect uit op elk element van de structuur en traverse stelt deze bijwerkingen samen met Applicative . Een andere manier om ernaar te kijken is dat sequenceA zegt dat Traversable structuren pendelen met Applicative s.

Het transformeren van een verplaatsbare structuur met behulp van een accumulerende parameter

De twee mapAccum functies combineren de bewerkingen van vouwen en toewijzen.

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

Deze functies generaliseren fmap in die fmap dat de toegewezen waarden afhankelijk zijn van wat er eerder in de vouw is gebeurd. Ze generaliseren foldl / foldr in die foldr dat ze de structuur op hun plaats brengen en deze tot een waarde reduceren.

Bijvoorbeeld, tails kunnen worden geïmplementeerd met behulp mapAccumR en haar zus inits kan worden geïmplementeerd met behulp van 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 wordt geïmplementeerd door de State applicatief functor te doorlopen.

{-# 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 werkt door mapAccumL in omgekeerde volgorde uit te voeren .

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

Verplaatsbare structuren als vormen met inhoud

Als een type t Traversable is, kunnen waarden van ta worden opgesplitst in twee stukken: hun "vorm" en hun "inhoud":

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

waarbij de 'inhoud' hetzelfde is als wat u zou 'bezoeken' met een Foldable instantie.

Eén richting ta , van ta tot Traversed ta vereist niets anders dan Functor en Foldable

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

maar teruggaan gebruikt de traverse functie cruciaal

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

De Traversable wetten vereisen die break . recombine en opnieuw recombine . break zijn beide identiteit. Dit betekent met name dat er precies de juiste nummerelementen in de contents zijn om de shape volledig te vullen zonder restjes.

Traversed t is Traversable zelf. De implementatie van traverse werken door de elementen te bezoeken met behulp van het exemplaar van de lijst van Traversable en vervolgens de inerte vorm opnieuw aan het resultaat te bevestigen.

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

Een lijst met lijsten transponeren

Opmerkend dat zip een tuple lijsten omzet in een lijst met tupels,

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

en de gelijkenis tussen de soorten transpose en 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)
--                                                |       |
--                                                +--->---+

het idee is om de Traversable en Applicative structuur van [] te gebruiken om sequenceA in te zetten als een soort n-ary zip , waarbij alle binnenlijsten puntsgewijs aan elkaar worden geritst.

[] 's standaard "geprioriteerde keuze" Applicative instantie is niet geschikt voor ons gebruik - we hebben een "zippy" Applicative . Hiervoor gebruiken we het nieuwe ZipList ZipList, te vinden 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)

Nu kunnen we gratis transpose , door de 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]]