Это вариант на «Compute an (infinite) tree from fixpoint operator using delay modality».Вычислить бесконечное дерево из корневых путей с использованием метода задержки
Установка. Изучается язык бинарных деревьев, дополненной с возможностью ссылаться на произвольные другие узлы в дереве на пути от корня:
type Path = [Bool]
data STree = SNode STree STree
| SPath Path
| SLeaf Int
deriving (Show)
Путь определен в контексте какой-то корень, и определяет поддерева, найденного последовательно следующими слева/справа детьми, когда мы видим False/True в пути. Например, путь [False, True] идентифицирует SLeaf 2 в дереве SNode (SNode (SLeaf 1) (SLeaf 2)) (SLeaf 3).
Такие деревья могут быть использованы, например, для идентификации произвольных графов потоков (в том числе неприводимых графиков, то, что не представляется возможным с помощью Fixpoint операторов.)
Мы можем рассматривать бесконечное дерево, вызванное этим описанием.
data Tree = Node Tree Tree
| Leaf Int
deriving (Show)
Вот функция преобразования от одного к другому, используя вспомогательную функцию follow, которая находит поддерево в какой-то путь дерева:
follow :: Path -> Tree -> Tree
follow [] s = s
follow (False : p) (Node s _) = follow p s
follow (True : p) (Node _ s) = follow p s
follow _ (Leaf _) = error "bad path"
flatten' :: Tree -> STree -> Tree
flatten' root (SPath p) = follow p root
flatten' root (SNode s1 s2) =
Node (flatten' root s1) (flatten' root s2)
flatten' _ (SLeaf i) = Leaf i
flatten :: STree -> Tree
flatten s = fix (\root -> flatten' root s)
К сожалению, эта функция не является продуктивным: оно бесконечные петли на flatten (SPath []).
Проблема. Теперь рассмотрим вариант этой структуры, дополненный модами задержки (как описано в «Compute an (infinite) tree from fixpoint operator using delay modality»), а также конструктор Loop для обозначения самореферентных петель.
data Tree = Node (D Tree) (D Tree)
| Leaf Int
| Loop
deriving (Show)
Без использования без структурно рекурсивных вызовов функций (так, вы можете структурно рекурсию на STree и Path), написать функцию STree -> Tree (или аналогичный), который развертывается бесконечное дерево.
Постскриптум. Во многих случаях мы не хотим вычислять бесконечное разворачивание: мы хотим, чтобы конечное разворачивание, если оно существует, и ошибка в противном случае. В частности, учитывая исходный тип данных:
data Tree = Node Tree Tree
| Leaf Int
deriving (Show)
Без использования без структурно рекурсивным, мы могли бы написать функцию STree -> Maybe Tree (или аналогичные), который разворачивает синтаксис в конечное дерево, если оно существует, и не иначе. Отсутствие механизма задержки в этой структуре гарантирует, что оно конечно.
Поскольку в этой структуре нет экземпляров модальности задержки, представляется невозможным сделать это с помощью fixD: мы получим отложенный результат, который мы никогда не сможем использовать. Казалось бы, мы должны преобразовать дерево в граф, топологически отсортировать его, а затем непосредственно реализовать алгоритм ala Gaussian exc без использования fixD.
Есть ли альтернативная типизирующая дисциплина, которая позволяет нам реализовать развертывания так же элегантно, как и в оригинальном (неправильном) коде? Если это так, вы можете просто (повторно) обнаружить другой алгоритм поиска циклов в графах.
Нет ничего, что он мог бы сделать, кроме бесконечного цикла (или возврата некоторого другого нижнего значения) на 'flatten (SPath [])'. Не существует «Дерева», которое могло бы соответствовать этому. В вашем втором примере это может быть «Loop», но для этого требуется обнаружение цикла. Вы должны быть в состоянии либо явно представлять ссылки в дереве (который имел бы известный конструктор), либо знать, какой конструктор путь будет идти априори. – Cirdec
Ну, не так сложно написать функцию завершения, которая использует 'Loop', но, как вы говорите, для этого требуется обнаружение цикла. Может ли очевидная очевидность очевидная производительность этой функции? Вот в чем вопрос! (Я также укажу, что в предыдущем случае был простой способ обнаружения циклов. Менее очевидно здесь!) –