Haskell Language Foldable Folding a structure in reverse
Example
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
