2

私はPrologから始めています、そして私は少し混乱しています...

私は簡単なプログラムを持っています：

sum(0, []).
sum(Total, [Head|Tail]) :- sum(Sum, Tail), Total is Head + Sum.

デバッグすると、Prologが最初にリストをHeadとTailで分割するので、結果は0 +空のリストになり、その後、数値の合計が開始され、リストに再度追加されます。

誰かがそれが最初に来ない理由を説明しTotal is Head + Sum. 、次にリストを再び頭と尾に分割することができますか？

編集：ここにトレースがあります：

[trace]  ?- sum(X, [1,2,3]).
Call: (6) sum(_G345, [1, 2, 3]) ? creep
Call: (7) sum(_G424, [2, 3]) ? creep
Call: (8) sum(_G424, [3]) ? creep
Call: (9) sum(_G424, []) ? creep
Exit: (9) sum(0, []) ? creep
Call: (9) _G430 is 3+0 ? creep
Exit: (9) 3 is 3+0 ? creep
Exit: (8) sum(3, [3]) ? creep
Call: (8) _G433 is 2+3 ? creep
xit: (8) 5 is 2+3 ? creep
Exit: (7) sum(5, [2, 3]) ? creep
Call: (7) _G345 is 1+5 ? creep
Exit: (7) 6 is 1+5 ? creep
Exit: (6) sum(6, [1, 2, 3]) ? creep
X = 6.
4

2 に答える 2

5

あなたの定義はスタックに加算を置きます。追加を片付けないようにする最適化は、末尾再帰として知られる一般的な手法の特殊なケースになります。

次の定義では、末尾再帰を使用できます。

sum(X,L):-sum(0,L,X).
sum(X,[],X).
sum(N, [Head|Tail],Y) :- N1 is Head + N, sum(N1,Tail,Y).

部分和の値のアキュムレータを導入し、リストの末尾に追加します。sum(X,[1,2,3])クエリの実行のトレースは次のとおりです。

?- trace, sum(S,[1,2,3]),notrace,nodebug.
   Call: (7) sum(_G584, [1, 2, 3]) ? creep
   Call: (8) sum(0, [1, 2, 3], _G584) ? creep
^  Call: (9) _G792 is 1+0 ? creep
^  Exit: (9) 1 is 1+0 ? creep
   Call: (9) sum(1, [2, 3], _G584) ? creep
^  Call: (10) _G795 is 2+1 ? creep
^  Exit: (10) 3 is 2+1 ? creep
   Call: (10) sum(3, [3], _G584) ? creep
^  Call: (11) _G798 is 3+3 ? creep
^  Exit: (11) 6 is 3+3 ? creep
   Call: (11) sum(6, [], _G584) ? creep
   Exit: (11) sum(6, [], 6) ? creep
   Exit: (10) sum(3, [3], 6) ? creep
   Exit: (9) sum(1, [2, 3], 6) ? creep
   Exit: (8) sum(0, [1, 2, 3], 6) ? creep
   Exit: (7) sum(6, [1, 2, 3]) ? creep
S = 6 .
于 2012-07-09T18:36:52.980 に答える
-2

これを行う別のバージョンがあります。私はコードの設計を支援するためにコンセプトマッピングソフトウェアを使用してきました。頭の中で複雑なことをすることはできません。

sum(A, [], A).
sum(Total, [Head|Tail], AuxNum) :-
    Sum is Head+AuxNum,
    sum(Total, Tail, Sum).


   1 ?- trace,sum(Total,[1,2,3],0).
   Call: (7) sum(_G2090, [1, 2, 3], 0) ? creep
   Call: (8) _G2221 is 1+0 ? creep
   Exit: (8) 1 is 1+0 ? creep
   Call: (8) sum(_G2090, [2, 3], 1) ? creep
   Call: (9) _G2224 is 2+1 ? creep
   Exit: (9) 3 is 2+1 ? creep
   Call: (9) sum(_G2090, [3], 3) ? creep
   Call: (10) _G2227 is 3+3 ? creep
   Exit: (10) 6 is 3+3 ? creep
   Call: (10) sum(_G2090, [], 6) ? creep
   Exit: (10) sum(6, [], 6) ? creep
   Exit: (9) sum(6, [3], 3) ? creep
   Exit: (8) sum(6, [2, 3], 1) ? creep
   Exit: (7) sum(6, [1, 2, 3], 0) ? creep
Total = 6.
于 2013-06-04T16:59:35.167 に答える