Объясните, как новый складной инструмент работает в Haskell

Question

Новый программист Haskell скоро перейдет к источникам, чтобы увидеть, как реализовано foldr. Ну, код был простым (не ожидайте, что новички узнают о OldList или FTP).

Как работает новый код?

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

Я упомяну только те части, которые не в the answer @duplode linked.

Во-первых, эти реализации, которые вы перечисляете, являются по умолчанию методов. Каждый Foldable типа должен предоставить свою собственную конкретную версию, по крайней мере один из них, а также списков ([]) обеспечивают foldr, which is implemented в значительной степени, как это всегда было:

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

(Который, для повышения эффективности, немного отличается от версии отчета Haskell.)

Кроме того, небольшое изменение в Foldable по умолчанию, так как ответ duplode является то, что странно #. оператор, используется внутри Data.Foldable кода GHC,. Это, в основном, более эффективная версия ., которая работает только , когда левая функция - это функция обертки/разворота нового типа. Это определяется с помощью нового механизма Newtype принуждения, и получает оптимизировано в практически ничего:

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