Недавно я просмотрел некоторые руководства по схемам рекурсии в Haskell, однако большинство статей не описывают go намного дальше реализации базовой инфраструктуры c, необходимой для этих концепций.
Учитывая рекурсивный тип данных, такой как двоичное дерево
data Tree a =
Leaf a
| Node a (Tree a) (Tree a)
, мы также реализовали бы аналогичную структуру, которая заменяет рекурсивные части определения параметром типа, чтобы можно было использовать общие c сгибы типа cata и ana и т. Д.
data TreeF a r =
LeafF a
| NodeF a r r
вместе с комбинатором с фиксированной точкой
newtype Fix f = In { out :: f (Fix f) }
, который позволяет нам express произвольно вложенного дерева с нашим новым представлением.
Итак, мой вопрос довольно прост (и, возможно, глуп): какое представление структуры данных мы фактически используем в остальной части нашей программы? Нужны ли нам оба? Теоретически мы могли бы использовать только TreeF, однако из того, что я нашел при игре с деревом грамматики выражений, которое было реализовано таким образом, это немного проблематично c, в основном, поскольку теперь вам нужно обернуть каждый уровень дерево в новом конструкторе данных, и, насколько я заметил, вы больше не можете автоматически наследовать от базовых c классов типов, таких как Show или Eq.