は、私はPrologでバイナリツリーを実装しようとしていると私は、次のエラーを取得していプロローグ

Question

に/ 2でありますis/2のRHSが正しくインスタンス化されていません。 しかし、私は2番目のtree_eval/3に変数zをインスタンス化する方法を理解することが難しいと思っています。

tree_eval(_,tree(empty,Num,empty),Num). 
tree_eval(Value,tree(empty,z,empty),Value):- 
     z = Value. 
tree_eval(Value,tree(L,Op,R),Eval):- 
     tree_eval(Value,L,LEval), 
     tree_eval(Value,R,REval), 
     eval(LEval,REval,Op,Eval). 

eval(LEval,REval,Op,Result):- 
     Op = '+', 
     Result is LEval + REval. 
eval(LEval,REval,Op,Result):- 
     Op = '-', 
     Result is LEval - REval. 
eval(LEval,REval,Op,Result):- 
     Op ='/', 
     Result is LEval/REval. 

ここで値をzに割り当てるにはどうすればよいですか？

ありがとうございます。

Answer 1

z=Value実際には、変数Valueをアトムzで統一しています。その場合

tree_eval(Value,tree(empty,Z,empty),Value):- 
     Z = Value. 

を、述語を照会するときに何が起こるかを検討することは興味深い：

?- tree_eval(V,tree(empty,3,empty),E). 
E = 3 ? ; 
E = V = 3 ? ; 
no 

あなたは@vmgが指摘したように、大文字 Zとしてそれを記述する必要があり、変数であることがZを意味する場合

最初の解決策は、最初の引数に匿名変数がある最初のルールによって生成されます。 2番目の解は、1番目と3番目の引数が同じであることを要求する2番目のルールによって生成されます。したがって、本質的に、両方の場合で3の値の2つの導出パスがあります。今度は、大きめの木を見てみましょう：

?- tree_eval(V,tree(tree(empty,2,empty),+,tree(empty,3,empty)),E). 
E = 5 ? ; 
E = 5, 
V = 3 ? ; 
E = 5, 
V = 2 ? ; 
no 

ツリーはなく、どのような次の二つのソリューションについて実際に5と評価されたとして、最初の答えはほとんどの思わぬされていませんか？

tree(tree(empty,2,empty),+,tree(empty,3,empty)) 

という用語は、サブツリーが空ではないため、3番目のルールとのみ一致します。だから、3/tree_evalが最初のソリューションとしてサブツリーtree(empty,2,empty)と収率で呼び出されます。(_,tree(empty,2,empty),2)

/3は、第一の溶液とのサブツリーtree(empty,3,empty)のために呼ばれその後tree_eval：

(_,tree(empty,3,empty),3)今eval(2,3,+,Eval)利回りEval=5。しかし、最初の引数はまだValue=_です。したがって、クエリの最初のソリューションはE=5です。

もしも他の答えを求めるなら、3番目の目標のためのさらなる解決策があるならば、プロローグは何もないと判断して、2番目の目標、すなわち正しいサブツリーに逆戻りし、実際には2番目のルールは(3,tree(empty,3,empty),3)です。 eval(2,3,+,Eval)はEval=5に再び寄与します。したがって、クエリの2番目の解決方法はE=5, V=3です。

さらに多くの解決策を依頼する場合、プロローグは第1目標にさらに後退しなければならず、第2のルールが再び配信されます：(2,tree(empty,2,empty),2)。 (_,tree(empty,3,empty),3)は、evalは/ 4が再びEval=5提供し、そのクエリへの第三ソリューションは、次のとおりです：今、あなたの第二の目標は、再び第一ルールが一致したE=5, V=2

は2プロローグが再び第二のルールをしようとするので失敗している目標に1つのより多くの時間をバックトラック最初の引数は同時に2と3になることはできません。したがって、クエリには4番目の解決策はありません。

?- tree_eval(V,tree(tree(empty,2,empty),+,tree(empty,2,empty)),E). 
E = 4 ? ; 
E = 4, 
V = 2 ? ; 
E = 4, 
V = 2 ? ; 
E = 4, 
V = 2 ? ; 
no 

たものを見て：tree_eval/3は同じツリー構造で問い合わせることだろうが、2であることの両方の葉が、それは、上記の理由により、実際の思わぬされていない場合

しかし、4つの解決策があること複数のソリューションでは、3番目の引数が正しい解決策を提供していること、そして最初の引数が本当に必要ないことが明らかです。また、2番目のルールなしで行うこともできます。 @matによって提案されたいくつかの改良を取り入れ、自分の述語は、そのように見えるかもしれません：

tree_evaluation(tree(empty,Num,empty),Num). 
tree_evaluation(tree(L,Op,R),Val) :- 
    tree_evaluation(L,LVal), 
    tree_evaluation(R,RVal), 
    evaluation(LVal,RVal,Op,Val). 

evaluation(L,R,+,V) :- 
    V is L + R. 
evaluation(L,R,-,V) :- 
    V is L - R. 
evaluation(L,R,/,V) :- 
    V is L/R. 

このバージョンでは、ユニークな答えが得られます。

?- tree_evaluation(tree(empty,3,empty),E). 
E = 3 ? ; 
no 

    ?- tree_evaluation(tree(tree(empty,2,empty),+,tree(empty,3,empty)),E). 
E = 5 ? ; 
no