Cách Foldable.foldl hoạt động trên Num a => a

Question

Trong LYAH, có một đoạn mã trông giống như thế này.

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

instance F.Foldable Tree where 
    foldMap f Empty = mempty 
    foldMap f (Node x l r) = F.foldMap f l `mappend` 
          f x   `mappend` 
          F.foldMap f r 

ghci> F.foldl (+) 0 testTree 
42 
ghci> F.foldl (*) 1 testTree 
64800 

Theo như tôi biết, foldMap là loại foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m, nhưng Num a => a bản thân không phải là loại Monoid, vì vậy tôi tự hỏi làm thế nào để Foldable.foldl thực sự làm việc ở đây? Và kể từ foldMap được gọi nội bộ theo số Foldable.foldl, loại số Monoid là gì?

Answer 1

Sẽ dễ dàng hơn một chút nếu bạn xem xét foldr, có loại (a -> b -> b) -> b -> t a -> b. Hàm 'đại số' có loại a -> b -> b, mà bạn có thể xem là a -> (b -> b) - tức là: một hàm lấy a làm đầu vào và trả về b -> b làm đầu ra.

Bây giờ, b -> b là một tự đồng cấu, đó cũng là một monoid, và Data.Monoid định nghĩa một loại Endo a (hoặc ở đây, nó nên có lẽ là Endo b), đó là, trên thực tế, một Monoid.

foldr chỉ đơn giản là sử dụng Endo trong nội bộ để gọi foldMap:

foldr :: (a -> b -> b) -> b -> t a -> b 
foldr f z t = appEndo (foldMap (Endo #. f) t) z 

foldl về cơ bản chỉ flips các đối số xung quanh để làm các trick cùng:

foldl :: (b -> a -> b) -> b -> t a -> b 
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z 

Để được rõ ràng, tôi theo nghĩa đen sao chép những hai chức năng thực hiện từ nguồn Haskell. Nếu bạn truy cập vào documentation of Data.Foldable, có nhiều liên kết khác nhau để xem nguồn. Đó là những gì tôi đã làm.