我试着写在“纯”序言可逆的关系（无is ，切割，或者类似的东西。是的，它的作业），我必须承认我没有线索怎么办。我没有看到任何工艺打造这样的事情。

我们给予“unpure”但可逆的算术关系（加，多重峰等于，小于，...），我们必须用它来创建这些关系。

现在，我想了解如何通过创建关系创建可逆函数tree(List,Tree)如果这是真正的List是二进制树的叶子列表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 **

因此，我们得到的答案是有点分心。它的第一眼看起来一切正常，只有在回溯真正的问题是遇到。这是收获的人习惯于在序言。显然，使用3个查询是更好的选择。但是，这是运气。

有一个简单的方法来确保这一点一般。只需添加额外的目标， false以查询。添加false手段，我们不再感兴趣的任何答案，因为它再也不能得逞。这样所有的分心被删除，我们直接面对的问题：

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

那么，在哪里这个循环是从哪里来的？

在纯粹的，单调的Prolog程序（如这一个），我们可以通过添加一些目标定位于非终止的理由false到我们的节目。如果得到的程序（称为故障片）不会终止，那么原来的程序没有任何终止。这是最小的故障片为我们的查询：

?- 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实际上是长度减去一个。记住失败片，我们首先得到了什么？非常相同的故障片会出现在这里呢！然而通过由一个“移位”的长度，递归规则的头部现在确保终止。

使用`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:

有趣的问题。

这就是我会做。基本上，因为加/ 3是不是你的关系是不可逆的。我基本上没有了，换成数字计数与对应叶片数大小的名单计数-这是可逆的（当然，追加/ 3和长度/ 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).