Вычислить бесконечное дерево из корневых путей, используя модальность задержки

Question

Это вариант " Вычислить (бесконечное) дерево из оператора с фиксированной точкой, используя модальность задержки ".

Настройки. Мы изучаем язык бинарных деревьев, дополненный возможностью ссылаться на произвольные другие узлы в дереве путем от корня:

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),

Такие деревья могут использоваться, например, для идентификации произвольных потоковых графов (включая неприводимые графы, что невозможно при использовании операторов с фиксированной точкой).

Мы можем рассмотреть бесконечное дерево, индуцированное этим описанием.

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 []),

Эта проблема. Теперь рассмотрим вариант этой структуры, дополненный модальностью задержки (как описано в разделе " Вычисление (бесконечного) дерева из оператора фиксированной точки с использованием модальности задержки "), а также 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: мы получим задержанный результат, который мы никогда не сможем использовать. Казалось бы, мы должны преобразовать дерево в граф, топологически отсортировать его, а затем напрямую реализовать алгоритм аля исключения Гаусса без использования fixD,

Есть ли альтернативная дисциплина типизации, которая позволяет нам реализовывать развёртывания так же элегантно, как и в оригинальном (неправильном) коде? Если это так, возможно, вы только что (заново) обнаружили другой алгоритм поиска циклов в графах.

Answer 1

Ну, вот хотя бы некоторые частичные наблюдения по проблеме.

Конкретная формулировка проблемы, которую я записал, возможно, слишком сложна; сложнее, чем предполагалось. Вот один особенно неприятный пример:

SNode (SVar [True, False]) (SVar [])

Это не правильно сформированный график, но цикл становится очевидным только после разворачивания SVar [] вхождение. Заменить False с True и это становится хорошо сформированным.

Намерение состояло в том, чтобы иметь возможность выражать неприводимые графы, и на самом деле, существует более простой синтаксис, основанный на letrec который может достичь этой цели. Мы непосредственно перенимаем представление бесконечного двоичного дерева из статьи Оливейры-Кука "Функциональное программирование со структурированными графами" ( https://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf) (без PHOAS, и конструкторы переименованы для согласованности):

data STree
  = SVar Var
  | SMu [Var] [STree] -- first tree gets "returned"
  | SLeaf Int
  | SNode STree STree

SMu это операция привязки в стиле letrec: SMu ["x", "y"] [t1, t2] по существу letrec x = t1; y = t2 in x, Вместо того, чтобы записывать путь к нужному узлу, вы просто даете ему имя. Кроме того, это делает эту проблему намного более похожей на предыдущий вопрос Stackru. ( Вычислить (бесконечное) дерево из оператора фиксированной точки, используя модальность задержки). Итак, можем ли мы решить его таким же образом?

Ответ "Да, однако..." Предостережение происходит в этом выражении: SMu ["x", "y"] [SVar "y", SLeaf 0], Это "рекурсивное" связывание вообще не является рекурсивным, но оно все равно будет отклонено алгоритмом стиля отложенного контекста, как переменная y недоступен в то время, когда мы хотим его использовать (он не защищен). Фактически, это точно соответствует ограничению, предложенному в "Запрещении пустых циклов": вставленные вхождения f служит проверкой безопасности, чтобы гарантировать, что циклы не могут произойти.

Ясно, что цель состоит в том, чтобы все SMu быть сильно связанным; таким образом, наш алгоритм подходит только в том случае, если мы сначала вычислим сильно связанные компоненты привязок, предварительно обработав их до действительно рекурсивных привязок (поэтому мы не отвергаем нерекурсивные привязки случайным образом). Нерекурсивные привязки можно обрабатывать по порядку без fixD, Действительно, это соответствует тому, как привязки в, например, в Haskell, обрабатываются на практике: сначала мы разделяем привязки на сильно связанные компоненты, а затем обрабатываем SCC по одному, связывая узел в этих случаях (и совершая ошибки, когда обнаруживаем пустой цикл в ГТК.)

Но это не все. Рассматривать SMu ["x" "y"] [SVar "y", SNode (SVar "x") (SVar "x")], Все компоненты сильно связаны, y неохраняемый, и все же нет неохраняемых петель. Так что недостаточно просто сортировать: мы должны также удалить пустые переменные. К счастью, это довольно тривиально (в этом случае замените все вхождения "x" на "y".)

Итак, что это значит в исходной проблеме? Я не думаю, что это полностью решено: укоренившиеся пути затрудняют сказать, какой должна быть "топологически отсортированная" версия дерева!