8

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
sevo
  • 4,559
  • 1
  • 15
  • 31
  • 1
    Probably not a duplicate, but [I wrote an answer on getting `foldr` from `foldMap` a while ago](http://stackoverflow.com/a/23319967/2751851). The answer presumes basic familiarity with `Monoid`, so please tell us if it takes too many things for granted. – duplode Aug 08 '15 at 16:44

2 Answers2

11

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 (#.) #-}
Community
  • 1
  • 1
Ørjan Johansen
  • 18,119
  • 3
  • 43
  • 53
0

The mental model I have for foldr follows this structure:

Given a list in it's a:(b:(c:[])) form, replace all ":" with the given op (1st parameter), and then replace the "[]" with the given initial value (2nd parameter).

A pseudo-codey example:

foldr (+) 0 [1,2,3,4] = 1 + 2 + 3 + 4 + 0

And remember, [1,2,3,4] is equivalent to 1:(2:(3:(4:[])))

Kos
  • 4,890
  • 9
  • 38
  • 42
John C
  • 37
  • 4