Giải thích cách foldr mới hoạt động trong Haskell

Question

Trình lập trình Haskell mới sẽ sớm đủ nguồn để xem cách foldr được triển khai. Vâng, mã được sử dụng đơn giản (không mong đợi những người mới đến biết về OldList hoặc FTP).

Mã mới hoạt động như thế nào?

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

tôi sẽ chỉ đề cập đến những phần mà không trong the answer @duplode linked.

Trước tiên, những triển khai bạn liệt kê là phương thức mặc định. Mỗi Foldable loại cần phải cung cấp phiên bản cụ thể riêng của mình ít nhất một trong số họ, và danh sách ([]) cung cấp foldr, which is implemented khá nhiều vì nó luôn luôn có được:

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

(Đó là, cho hiệu quả, khác với phiên bản báo cáo Haskell.)

Ngoài ra, thay đổi nhỏ trong yêu cầu Foldable vì câu trả lời của hai chiều là toán tử lạ #., được sử dụng nội bộ trong mã Data.Foldable của GHC. Về cơ bản, đây là phiên bản hiệu quả hơn của . chỉ hoạt động chỉ khi hàm bên trái là hàm wrapper/unwrapper newtype. Nó được xác định bằng cách sử dụng cơ chế Newtype ép buộc mới, và được tối ưu hóa thành về cơ bản không có gì:

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