2

这是“使用延迟模态从定点算子计算（无限）树”的变体。

那个设定。我们研究一种二叉树语言，增强了通过从根开始的路径引用树中任意其他节点的能力：

type Path = [Bool]
data STree = SNode STree STree
           | SPath Path
           | SLeaf Int
    deriving (Show)

路径是在某个根的上下文中定义的，当我们在路径中看到 False/True 时，它​​会识别通过连续跟随左/右子节点找到的子树。例如，路径在树中[False, True]标识。SLeaf 2SNode (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)

不使用非结构递归函数调用（因此，您可以在STreeand上进行结构递归Path），编写一个STree -> Tree展开无限树的函数（或类似函数）。

后记。在许多情况下，我们不想计算无限展开：如果存在，我们想要有限展开，否则会出错。具体来说，给定原始数据类型：

data Tree = Node Tree Tree
          | Leaf Int
    deriving (Show)

在不使用非结构递归的情况下，我们可能想要编写一个函数STree -> Maybe Tree（或类似函数），如果它存在则将语法展开为有限树，否则失败。这种结构中没有延迟模态保证了它是有限的。

由于此结构中没有延迟模态的实例，因此似乎无法使用fixD: 我们将得到一个我们永远无法使用的延迟结果。看来我们必须将树转换为图，对其进行拓扑排序，然后直接实现高斯消元算法，而不使用fixD.

是否有替代的打字规则允许我们像在原始（错误）代码中一样优雅地实现展开？如果是这样，您可能刚刚（重新）发现了另一种在图中查找循环的算法。

4

1 回答 1

1

好吧，这里至少是对这个问题的一些部分观察。

我写下的问题的具体表述可能有点太难了；比预想的更困难。这是一个特别讨厌的例子：

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

这不是一个格式良好的图表，但只有在展开SVar []事件后，循环才会变得明显。替换为False，True它变得格式良好。

目的是能够表达不可约图，事实上，有一种更简单的语法letrec可以实现这一目标。我们直接采用 Oliveira-Cook 的“结构化图的函数式编程”（ 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. 无需写下所需节点的路径，只需为其命名即可。此外，这使得这个问题与之前的 StackOverflow 问题更加相似。（使用延迟模态从定点算子计算（无限）树）那么，我们可以用同样的方法解决它吗？

答案是“是的，但是……” 警告出现在这个表达式中：SMu ["x", "y"] [SVar "y", SLeaf 0]. 这种“递归”绑定根本不是递归的——但它仍然会被延迟上下文风格算法拒绝，因为在y我们想要使用它的时候变量不可用（它没有被保护。）事实上，这正是对应于“禁止空循环”中建议的限制：插入的出现f用作保护检查以确保不会发生循环。

显然，意图是所有的绑定SMu都是强连接的；因此，我们的算法只有在我们首先计算绑定的强连通分量，预处理成真正的递归绑定（因此我们不会虚假地拒绝非递归绑定）时才适用。非递归绑定可以在没有fixD. 实际上，这与 Haskell 中的绑定在实践中的处理方式相匹配：我们首先将绑定分离为强连接的组件，然后一次处理一个 SCC，在这些情况下打结（当我们检测到空时出错在 SCC 中循环。）

但这还不是全部。考虑SMu ["x" "y"] [SVar "y", SNode (SVar "x") (SVar "x")]。所有的组件都是强连接的，y没有保护的，但是没有没有保护的循环。所以仅仅 topsort 是不够的：我们还必须删除裸变量。幸运的是，这相当简单（在这种情况下，将所有出现的“x”替换为“y”。）

那么，这对原始问题意味着什么？我不认为它已经完全解决了：有根路径使得很难说出树的“拓扑排序”版本应该是什么！

于 2016-06-17T03:20:20.487 回答