Monoid Endo

newtype Endo a = Endo { unwrap :: a -> a }

instance Semigroup (Endo a) where
  Endo f <> Endo g = Endo (f . g)

instance Monoid (Endo a) where
  mempty = Endo id

Kiểu Endo a bao bọc một hàm có cùng kiểu đầu vào và đầu ra (a → a). Phép kết hợp của Endo chính là phép hợp thành hàm. Vì hợp thành hàm luôn thỏa tính kết hợp và tồn tại hàm đồng nhất (id), nên Endo tạo thành một monoid.

Monoid Dual

newtype Dual a = Dual { extract :: a }

instance Semigroup a => Semigroup (Dual a) where
  Dual x <> Dual y = Dual (y <> x)

instance Monoid a => Monoid (Dual a) where
  mempty = Dual mempty

Dual a đảo ngược thứ tự kết hợp: khi hai giá trị được kết hợp, chúng hoán đổi vị trí trước khi áp dụng phép <> gốc. Điều này tương đương với việc đảo chiều phép toán ban đầu — hữu ích khi cần duyệt ngược hoặc đảo ngữ cảnh kết hợp.

Luật của Foldable

class Foldable f where
  fold    :: Monoid m => f m -> m
  foldMap :: Monoid m => (a -> m) -> f a -> m
  foldr   :: (a -> b -> b) -> b -> f a -> b
  foldl   :: (b -> a -> b) -> b -> f a -> b

  fold    = foldMap id
  foldMap g = foldr (mappend . g) mempty
  foldr f z t = unwrap (foldMap (Endo . f) t) z
  foldl f z t = unwrap (extract (foldMap (Dual . Endo . flip f) t)) z

Mọi instance của Foldable phải tuân thủ các đẳng thức trên. Chúng đảm bảo rằng cách triển khai foldr, foldl, và foldMap là tương đương nhau về mặt ngữ nghĩa.

Ví dụ: Danh sách là Foldable

instance Foldable [] where
  foldr = Prelude.foldr
  foldl = Prelude.foldl

Dễ dàng kiểm tra rằng với danh sách, các luật foldr và foldl đều thỏa mãn nhờ định nghĩa qua Endo và Dual.

Xây dựng danh sách với build và (++)

build :: forall a. (forall b. (a -> b -> b) -> b -> b) -> [a]
build k = k (:) []

infixr 5 ++
(++) :: [a] -> [a] -> [a]
xs ++ ys = foldr (:) ys xs

Hàm build cho phép xây dựng danh sách theo cách tối ưu hóa thông qua kỹ thuật "fusion" — đặc biệt hữu ích trong thư viện chuẩn.

Mối liên hệ giữa foldMap và concatMap

concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap f = foldMap f  -- vì [b] là monoid với (++)

Khi monoid là danh sách, foldMap trở thành concatMap. Đây là một ứng dụng trực tiếp của định nghĩa foldMap với phép nối danh sách.

Tương tự: fold và concat

concat :: Foldable t => t [a] -> [a]
concat = fold  -- vì fold = foldMap id, và id trên [a] giữ nguyên danh sách

Hàm concat chỉ là trường hợp đặc biệt của fold khi phần tử là danh sách.

Triển khai reverse bằng foldr

reverseViaFold :: [a] -> [a]
reverseViaFold = flip (foldr step id) []
  where step x acc = acc . (x :)

Bằng cách sử dụng Endo và phép hợp thành hàm, ta có thể biểu diễn reverse dưới dạng foldr. Tổng quát hơn:

foldlAsFoldr :: (b -> a -> b) -> b -> [a] -> b
foldlAsFoldr f z xs = foldr (\x g a -> g (f a x)) id xs z

Điều này chứng minh rằng mọi phép foldl đều có thể biểu diễn lại bằng foldr — một kỹ thuật quan trọng trong tối ưu hóa và biến đổi chương trình.