Foldr для набора двоичного дерева

Question

Как реализовать функцию свёртки для набора с подписью:

(a -> b -> b) -> Set a -> b -> b

вместо

(a -> b -> b) -> b -> Set a -> b

, где

data Set x = Node | Tree x (Set x) (Set x)

Answer 1

Вы можете определить новую функцию в терминах оригинала (обратите внимание, что это не спецификация c до Set; это работает для любого конструктора типов с экземпляром Foldable).

-- or any Foldable t => (a -> b -> b) -> t a -> b -> b
foldr' :: (a -> b -> b) -> Set a -> b -> b
foldr' f = flip (foldr f)
-- foldr' = flip . foldr

Другими словами, новая функция - это просто foldr, составленная из flip.