История изменений
Исправление
Crocodoom,
(текущая версия)
:
Однако я пока затрудняюсь показать или опровергнуть, что свёртка дерева «в ширину» (а не «в глубину») тоже является катаморфизмом. Вполне возможно, что является.
Теперь разобрался. Свёртка дерева «в ширину» катаморфизмом не является, и посему может называться свёрткой лишь условно. Буду использовать просто слово «обход».
Дело в том, что инстанс foldMap для обхода «в ширину» невозможно написать естественной рекурсией по Tree a, из списка моноидов поддеревьев мы не можем слепить моноид дерева, происходит потеря информции.
То есть, имея дерево Tree a = Tree a [Tree a], и уже обойдя в ширину каждое дерево Tree a в лесе, мы не сможем скомбинировать обход в ширину исходного дерева.
И также не могу сказать, является ли катаморфизмом свёртка Queue в том виде, в котором её хочет monk.
А вот свёртка для обхода очереди как outbox .. reverse inbox (семантический порядок элементов для Queue) катаморфизмом является, так что тут было всё нормально.
Исходная версия
Crocodoom,
:
Однако я пока затрудняюсь показать или опровергнуть, что свёртка дерева «в ширину» (а не «в глубину») тоже является катаморфизмом. Вполне возможно, что является.
Теперь разобрался. Свёртка дерева «в ширину» катаморфизмом не является, и посему может называться свёрткой лишь условно. Буду использовать просто слово «обход».
Дело в том, что инстанс foldMap для обхода «в ширину» невозможно написать естественной рекурсией по Tree a, из списка моноидов поддеревьев мы не можем слепить моноид дерева, происходит потеря информции.
То есть, имея дерево Tree a = Tree a [Tree a], и уже обойдя в ширину каждое дерево Tree a в лесе, мы не сможем скомбинировать обход в ширину исходного дерева.
И также не могу сказать, является ли катаморфизмом свёртка Queue в том виде, в котором её хочет monk.
А вот свёртка для обхода очереди как outbox .. reverse inbox (сементический порядок элементов для Queue) катаморфизмом является, так что тут было всё нормально.