Spiega come funziona il nuovo foldr in Haskell

Question

Il nuovo programmatore Haskell sarà abbastanza presto andare alle fonti per vedere come viene implementato foldr. Bene, il codice era semplice (non aspettatevi che i nuovi arrivati ​​sappiano su OldList o FTP).

Come funziona il nuovo codice?

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

mi limiterò a citare le parti che sono non in the answer @duplode linked.

In primo luogo, le implementazioni elencate sono metodi predefiniti. Ogni Foldable tipo deve fornire la propria versione specifica di almeno uno di loro, e gli elenchi ([]) forniscono foldr, which is implemented più o meno come lo è sempre stato:

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

(Che è, per l'efficienza, un po 'diversa dalla versione rapporto Haskell.)

Inoltre, un leggero cambiamento nel Foldable di default in quanto la risposta di duplode è quella strana #. operatore, utilizzato internamente nel codice di GHC Data.Foldable. È fondamentalmente una versione più efficiente di . che funziona solo quando la funzione sinistra è una funzione wrapper/unwrapper di tipo newtype. E 'definita con il nuovo meccanismo di Newtype la coercizione, e viene ottimizzato in sostanza nulla:

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