История изменений

Ваш пример проходит компиляцию, однако не «заменяет n-арные конструкторы данных на n-арные функции», а именно этим должен заниматься foldr.

Где написано, что он должен делать именно это?

Это определение катаморфизма. Там как раз речь идёт о замене конструкторов на подходящие по типам и арности функции. Все разумные инстансы Foldable должны работать как катаморфизмы. Вот откуда я это и взял, кажется. AndreyKl это вам тоже.

https://traditio.wiki/Катаморфизм

Катаморфизм в функциональном программировании

В функциональном программировании катаморфизм является обобщением свёртки (для списков) на произвольные алгебраические типы данных, что может быть описано при помощи начальных алгебр (понятие из теории категорий). ... Как известно, алгебраический тип данных является размеченным объединением декартовых произведений различных типов, в том числе и сам такой тип может включаться в своё определение рекурсивно. Каждому декартову произведению в языке Haskell соответствует один конструктор данных, после которого перечисляется 0 или более полей некоторых типов.

Однако я пока затрудняюсь показать или опровергнуть, что свёртка дерева «в ширину» (а не «в глубину») тоже является катаморфизмом. Вполне возможно, что является. И также не могу сказать, является ли катаморфизмом свёртка Queue в том виде, в котором её хочет monk.

Ваш пример проходит компиляцию, однако не «заменяет n-арные конструкторы данных на n-арные функции», а именно этим должен заниматься foldr.

Где написано, что он должен делать именно это?

Это определение катаморфизма. Там как раз речь идёт о замене конструкторов на подходящие по типам и арности функции. Все разумные инстансы Foldable должны работать как катаморфизмы. Вот откуда я это и взял, кажется. AndreyKl это вам тоже.

https://traditio.wiki/Катаморфизм

Катаморфизм в функциональном программировании

В функциональном программировании катаморфизм является обобщением свёртки (для списков) на произвольные алгебраические типы данных, что может быть описано при помощи начальных алгебр (понятие из теории категорий). ... Как известно, алгебраический тип данных является размеченным объединением декартовых произведений различных типов, в том числе и сам такой тип может включаться в своё определение рекурсивно. Каждому декартову произведению в языке Haskell соответствует один конструктор данных, после которого перечисляется 0 или более полей некоторых типов.

Однако я пока затрудняюсь показать или опровергнуть, что свёртка дерева «в ширину» (а не «в глубину») тоже является катаморфизмом. Вполне возможно, что является.