A+B=Cの具体値の列挙

Question

###質問内容
???? + ???? = ???? であるような自然数????, ????, ???? の組を具体値ですべて列挙する述語addall(????, ????, ????)を作りたいと思い，以下のように書いたのですが，AとCにしかs()を使えていないので，A=C, B=0でずっと続いてしまい，思うような結果を得ることが出来ません．
この再帰は無限回，深く見てしまうので，この下に何かを書いてBを操作することもできません．
どのようにすれば，Bの値も網羅的に見ていくことが出来ますでしょうか．

###書いたコード

addall(0,0,0).
addall(s(A),B,s(C)):- addall(A,B,C).

###注意事項
ここでの自然数は0を含むこととします．
また，s()は加算を表し，1はs(0)，2はs(s(0))のように表します．

###求める実行結果

addall(A,B,C).
A = B, B = C, C = 0 ;
A = 0,
B = C, C = s(0) ;
A = C, C = s(0),
B = 0 ;
A = 0,
B = C, C = s(s(0)) ;
A = B, B = s(0),
C = s(s(0)) ;
A = C, C = s(s(0)),
B = 0 ;
A = 0,
B = C, C = s(s(s(0))) ;
A = s(0),
B = s(s(0)),
C = s(s(s(0))) ;
A = s(s(0)),
B = s(0),
C = s(s(s(0))) ;
A = C, C = s(s(s(0))),
B = 0 ;
...

Answer 1

Cの値を構成するA,Bの組み合わせを求める

以下のadd_combのZが自然数の時、Zを構成するXとYの組み合わせを列挙します。

?- [user].
|: add_comb(s(X),Y,s(Z)):-add_comb(X,Y,Z).
|: add_comb(0,Z,Z).
|: ^D% user://1 compiled 0.03 sec, 2 clauses
true.

?- add_comb(X,Y,0).
X = Y, Y = 0.

?- add_comb(X,Y,s(0)).
X = s(0),
Y = 0 ;
X = 0,
Y = s(0).

?- add_comb(X,Y,s(s(0))).
X = s(s(0)),
Y = 0 ;
X = Y, Y = s(0) ;
X = 0,
Y = s(s(0)).

prologのappendをヒントにしました。まだ未完成です。Zが連続的の増加するようにすれば完成。

Comments

[xebme]

ペアノ算術とリスト操作の同型性
s(X)とX
[H|T]とT
同型とみなせば、リスト操作をペアノ算術に置き換えることができます。