algorithm - Prolog程序，这个程序应该做什么？

Question

我完全不懂 Prolog，但我仍然需要了解这个程序的作用。编译器显示有2个语法错误，但是这个程序的主要逻辑应该还是可以理解的。

domains
 value=symbol
 level=integer
 ltype1=s(value,level)
 ltype2=tree(value,ltype2,ltype2); void
 list1=ltype1*

predicates
 append(list1,list1,list1)
 totree(ltype2,integer,list1)

clauses
 append([],X,X).
 append([X|T],Y,[X|Z]):-append(T,Y,Z).

 totree(void,_,[]).
 totree(tree(X,Y,Z),N,[s(X,N)|TA]):-
    K=N+1,
    totree(Y,K,TA1),
    totree(Z,K,TA2),
    append(TA1,TA2,TA).

goal
 totree(
    tree(a,tree(b,tree(c,void,void),tree(e,void,void)),tree(d,void,void)),
    1,C),
 write(C),
 totree(W,1,
          [s(a,1),s(b,2),s(c,3),s(e,3),s(d,2)]).

Answer 1

这是您可以运行的程序:

append([],X,X).
append([X|T],Y,[X|Z]):-
    append(T,Y,Z).

totree(void,_,[]).
totree(tree(X,Y,Z),N,[s(X,N)|TA]):- 
    K is N+1,
    totree(Y,K,TA1),
    totree(Z,K,TA2),
    append(TA1,TA2,TA).

如果你运行查询

?-totree(tree(a,tree(b,tree(c,void,void),tree(e,void,void)),tree(d,void,void)),1,C ).

结果会是

C = [s(a, 1), s(b, 2), s(c, 3), s(e, 3), s(d, 2)]。

谓词 totree/3 接受输入:

• 表示为 tree(RootElement,Left,Right) 的树，其中 Left 和 Right 是左右子树，
• 一个数字，表示你所在的树的级别
• 并返回一个列表，它是树的表示。

让我们分析一下结果。

• s(a,1):元素 a 位于树的第 1 层，正确，因为它是根(第 1 层是因为在查询中指定).
• s(b,2):元素b在树的第2层，正确因为b是左 child 一个。
• s(c,3):元素c在树的第3层，正确因为c是左 child b 和一片叶子。
• 等等...

这是 append/3 的定义:append(List1,List2,List3) List3 是 List1 的串联 和 List2(此谓词在某些库中已作为 list 提供。