Haskell Language Folding a structure in reverse


Any fold can be run in the opposite direction with the help of the Dual monoid, which flips an existing monoid so that aggregation goes backwards.

newtype Dual a = Dual { getDual :: a }

instance Monoid m => Monoid (Dual m) where
    mempty = Dual mempty
    (Dual x) `mappend` (Dual y) = Dual (y `mappend` x)

When the underlying monoid of a foldMap call is flipped with Dual, the fold runs backwards; the following Reverse type is defined in Data.Functor.Reverse:

newtype Reverse t a = Reverse { getReverse :: t a }

instance Foldable t => Foldable (Reverse t) where
    foldMap f = getDual . foldMap (Dual . f) . getReverse

We can use this machinery to write a terse reverse for lists:

reverse :: [a] -> [a]
reverse = toList . Reverse