Prologのリストの合計
-
14-12-2019 - |
質問
私は「prologの芸術」の本を読んでいて、「補助述語を使用せずに、SumがListOfIntegersの合計であるかどうかを保持する関係sum(ListOfIntegers、Sum)を定義する」という演習を見つけました。私はこの解決策を思いついた:
sum([],Sum).
sum([0|Xs], Sum):-sum(Xs, Sum).
sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).
これは私が望むように正確には機能しません。
?- sum([s(s(0)),s(0),s(s(s(0)))],X).
true ;
false.
私はXがあることを期待していた
s(s(s(s(s(s(0))))))
問題は、最初の「反復」で合計を0に「初期化」する必要があることだと思いましたが、それは非常に手続き的であり、残念ながらprologではその作業を行うのが何かアイデアや提案はありますか?
解決
問題をローカライズする最良の方法は、最初にクエリを単純化することです:
?- sum([0],S).
true
?- sum([],S).
true
それらのために、あなたは答えとしてそれを得る 任意の S
そうします。のように
?- sum([],s(s(0))).
yes
以来 []
あなたの事実によってのみ処理することができます、エラーはその事実にある必要があります。あなたは述べた:
sum([], Sum).
これは、の合計を意味します []
ちょうど何でもあります。あなたはおそらく0を意味しました。
最後のルールに別のエラーが隠れています。..最初のエラーを修正した後、次のようになります
?- sum([0],Sum).
Sum = 0
?- sum([s(0)],Sum).
no
ここでは、最後の句が責任があります。それは読みます:
sum([s(X)|Xs], Sum):-sum([X|Xs],s(Sum)).
再帰的なルールは、Prologで読むのが比較的難しいです。それらを理解する最も簡単な方法は、次のものを見ることです。 :-
そして、これは矢印←(したがって右から左への矢印)の意味であるべきであることを認識してください:
ただし、右側の目標が真であることを条件とします
私たちは左側にあるものを結論づけます
だから、非公式の書き込みと比較して、矢印は反対方向を指しています!
私たちのクエリでは、次のインスタンス化を代入することを考えることができます Xs
と []
と X
と0.
sum([s(0)| [] ], Sum) :- sum([0| []],s(Sum)).
したがって、このルールは右から左に読み込まれます:提供される, sum([0],s(Sum))
が真である。..しかし、私たちはそれだけを知っていますか sum([0],0)
保持していますが、その目標ではありません。したがって、このルールは決して適用されません!あなたが意図したことはむしろ反対でした:
sum([s(X)|Xs], s(Sum)):-sum([X|Xs],Sum).
他のヒント
あなたの最初の句は
を読むべきですsum([], 0).
.
その変更付きでは、Navuous true
Returnが消え、1つの問題が残ります.3番目の句は合計の論理を反転します。それは
sum([s(X)|Xs], s(Sum)) :- sum([X|Xs], Sum).
.
s/1
への左の引数のsum/2
の数は、正しい引数の数と同じであるべきです。
私はあなたの論理を本当に続かせていません。
このようなことをするのが簡単で簡単なことはありませんか?
最初に、解決策を平野の英語で定義しているため、
- 空リストの合計は0です。
- 非空のリストの合計は、リストの先頭の末尾にリストの先頭を追加することによって得られます。
その定義から、プロローグは直接次のようになります:
sum( [] , 0 ) . % the sum of an empty list is 0.
sum( [X|Xs] , T ) :- % the sum of an non-empty list is obtained by:
sum( Xs , T1 ) , % - first computing the sum of the tail
T is X + T1 % - and then, adding that the to head of the list
. % Easy!
.