Explain how does new foldr work in Haskell

Question

New Haskell programmer will soon enough go to sources to see how foldr is implemented. Well, the code used to be simple (don't expect newcomers to know about OldList or FTP).

How does the new code work?

-- | Map each element of the structure to a monoid,
-- and combine the results.
foldMap :: Monoid m => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty

-- | Right-associative fold of a structure.
--
-- @'foldr' f z = 'Prelude.foldr' f z . 'toList'@
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z

Answer 1

I'll just mention the parts that are not in the answer @duplode linked.

First, those implementations you list are default methods. Every Foldable type needs to provide its own specific version of at least one of them, and lists ([]) provide foldr, which is implemented pretty much as it always has been:

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

(Which is, for efficiency, a bit different from the Haskell report version.)

Also, a slight change in the Foldable default since duplode's answer is that strange #. operator, used internally in GHC's Data.Foldable code. It's basically a more efficient version of . that works only when the left function is a newtype wrapper/unwrapper function. It's defined using the new newtype coercion mechanism, and gets optimized into essentially nothing:

(#.) :: Coercible b c => (b -> c) -> (a -> b) -> (a -> c)
(#.) _f = coerce
{-# INLINE (#.) #-}