Haskell Language Traversing a structure in reverse


A traversal can be run in the opposite direction with the help of the Backwards applicative functor, which flips an existing applicative so that composed effects take place in reversed order.

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 can be put to use in a "reversed traverse". When the underlying applicative of a traverse call is flipped with Backwards, the resulting effect happens in reverse order.

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

The Reverse newtype is found under Data.Functor.Reverse.