可逆树长度关系

Question

我试图在"纯粹的"Prolog中写出可逆关系(没有is,剪切或类似的东西.是的,它是家庭作业),我必须承认我不知道如何.我没有看到任何创建这样的事情的过程.

我们被赋予"不可知"但可逆的算术关系(add,mult,equal,less,...),我们必须使用它们来创建这些关系.

现在我正在尝试通过创建关系来了解如何创建可逆函数,tree(List,Tree)如果List是二叉树的叶子列表则为true Tree.

为了实现我试图创造这样的事情tree_size(Tree,N)时,这是真正的关系Tree有N叶子.这是我天真的,不可逆转的关系:

tree_len(n(_,leaf,leaf),1).
tree_len(n(op,G,D),N) :-
    tree_len(G,TG),
    tree_len(D,TD),
    add(TG,TD,N).

我可以进行查询tree_len(some tree, N),但不是说tree_len(X,3),所以它不可逆.到目前为止,我已经尝试了一些事情,但我必须承认我感到气馁,因为我不知道在哪里寻找什么.有没有办法做到这一点？

Answer 1

不终止的原因

首先,让我们试着理解为什么你的定义不可逆.我将使用故障片来更好地解释它.所以考虑一下tree_len(X,1).乍一看,一切都很完美,你会得到一个很好的答案!

?- tree_len(T,1).
T = n(_G267, leaf, leaf) 

但是从不要求另一个答案,因为它会循环:

?- tree_len(T,1).
T = n(_G267, leaf, leaf) ;
** LOOPS **

所以我们得到的答案有点分散注意力.乍一看看起来一切都还好,只有在回溯时遇到了真正的问题.这是Prolog习惯的东西.显然,使用3的查询选择得更好.但那是运气.

总的来说,有一种简单的方法可以确保这一点.只需false在查询中添加额外的目标即可.添加false手段,我们不再对任何答案感兴趣,因为它不再能够成功.以这种方式消除了所有分心,我们直接面对问题:

?- tree_len(T,1), false.
** LOOPS **

那么,这个循环来自哪里？

在纯粹的,单调的Prolog程序(例如这个程序)中,我们可以通过false在程序中添加一些目标来本地化不终止的原因.如果生成的程序(称为failure-slice)没有终止,则原始程序也不会终止.这是我们查询的最小失败切片:

?- tree_len(T,1), false.

tree_len(n(_,leaf,leaf),1) :- false.
tree_len(n(op,G,D),N) :-
    tree_len(G,TG), false,
    tree_len(D,TD),
    N is TG+TD.

我们的计划还剩下多少了!正是这个微小的碎片负责非终止.如果我们想解决问题,我们必须在这一小部分做点什么.其他一切都是徒劳的.

所以我们需要做的是以某种方式改变程序,使这个片段不再循环.

实际上,我们有两个选择,我们可以使用后继算术或像clpfd这样的约束.前者可用于任何Prolog系统,后者仅在某些类似SWI,YAP,SICStus,GNU,B中提供.

使用继承算术

现在,3代表s(s(s(0))).

tree_lensx(T, s(N)) :-
   tree_lendiff(T, N,0).

tree_lendiff(n(_,leaf,leaf), N,N).
tree_lendiff(n(op,G,D), s(N0),N) :-
   tree_lendiff(G, N0,N1),
   tree_lendiff(D, N1,N).

我在这里使用了几种常见的编码技术

差异

实际关系tree_lendiff/3代表一个自然数而不是一个参数,而是使用两个.实际数字是两者之间的差异.以这种方式,可以保持定义可逆.

避免左递归

另一种技术是避免左递归.tree_lendiff/3实际描述的长度是长度减去 1.还记得我们先得到的失败片吗？这里也会出现同样的故障切片!然而,通过将长度"移动"一,递归规则的头部现在确保终止.

运用 library(clpfd)

最初,开发了有限域上的约束来解决组合问题.但你也可以使用它们来获得可逆的算术.SWI和YAP的实施甚至可以实现,它可以编译成代码,这些代码通常与传统的非可逆性相当,(is)/2但仍然是可逆的.

:- use_module(library(clpfd)).

tree_fdlen(n(_,leaf,leaf),1).
tree_fdlen(n(op,G,D),N) :-
   N #= TG+TD,
   TG #>= 1,
   TD #>= 1,
   tree_fdlen(G,TG),
   tree_fdlen(D,TD).

此程序更接近您原始定义.尽管如此,请注意这两个目标TG #>= 1,TD #>= 1并添加了冗余信息以确保终止此计划.

我们现在可以枚举某个范围内的所有树,如下所示:

?- Size in 0..4, tree_fdlen(T, Size).
Size = 1, T = n(_A,leaf,leaf) ;
Size = 2, T = n(op,n(_A,leaf,leaf),n(_B,leaf,leaf)) ;
Size = 3, T = n(op,n(_A,leaf,leaf),n(op,n(_B,leaf,leaf),n(_C,leaf,leaf))) ;
Size = 4, ... ;
Size = 4, ... ;
Size = 3, ... ;
Size = 4, ... ;
Size = 4, ... ;
Size = 4, ... ;
false.

请注意答案替换的确切顺序!这不仅仅是1,2,3,4!相反,答案可以按某种顺序找到.只要我们只对找到所有解决方案感兴趣,哪一个都没关系!

Answer 2

有趣的问题。

这就是我要做的。基本上，您的关系是不可逆的，因为 add/3 不是可逆的。我本质上所做的是，用与叶子数量相对应的大小的列表进行计数来代替数字计数 - 这是可逆的（嗯，append/3 和 length/2 是可逆的）。

这是您所需要的吗？发布的代码可以在 YAP 下运行。

PS：这可能不是最简洁的解决方案，但它是我的想法。如果您还有任何其他问题，我会尽力提供帮助。

:-  use_module(library(lists)).

do_tree_len(n(_,leaf,leaf), [X]).
do_tree_len(n(op,G,D), [X1,X2|T]) :-
    append(TG, TD, [X1,X2|T]),
    TG \= [X1,X2|T], % To prevent infinite loops, when TG or TD is []
    TD \= [X1,X2|T],
    do_tree_len(G, TG),
    do_tree_len(D, TD).

tree_len(Tree, N):-
    length(L, N),
    do_tree_len(Tree, L).