binary - Prolog - 二进制加法？

Question

我需要编写一个 Prolog 谓词来计算列表中表示的 2 个二进制数的总和。列表已经颠倒过来，例如 ([0,1] base 2) = (2 base 10)。

例如，它应该适用于 binary_plus(+,+,-) 模式

?- binary_plus([1,1],[1],X).
X = [0,0,1].

例如，模式为binary_plus(-,-,+)

?- binary_plus(X,X,[0,1]).
X = [1].

我不允许使用剪切符号、findall、否定或 if-then-else。

这是我的代码:

is_binary([]).
is_binary([X]):- X is 1.
is_binary([X|Xs]):-
    append(_,[1],Xs),
    member(X,[0,1]),    
    is_binary(Xs).

binary_plus([],X,X):-
    is_binary(X).
binary_plus(X,[],X):- 
    is_binary(X).

binary_plus([0|Xs],[Y|Ys],[Y|Zs]):-
    binary_plus(Xs,Ys,Zs).
binary_plus([1|Xs],[0|Ys],[1|Zs]):-
    binary_plus(Xs,Ys,Zs).
binary_plus([1|Xs],[1|Ys],[0|Zs]):-
    binary_plus(Xs,[1],Ws),
    binary_plus(Ws,Ys,Zs).

我不知道我错在哪里，因为有一些奇怪的问题我无法解决，所以如果有人可以帮助我，我将不胜感激。谢谢。

Answer 1

描述列表时，始终考虑使用 DCG 表示法。例如，在您的情况下，请考虑将其写为:

:- use_module(library(clpfd)).

binary_addition(Xs, Ys, As) :-
        phrase(binary_addition_(Xs, Ys, 0), As).

binary_addition_([], [], 0)     --> [].
binary_addition_([], [], 1)     --> [1].
binary_addition_([X|Xs], [], C) --> binary_addition_([X|Xs], [C], 0).
binary_addition_([], [Y|Ys], C) --> binary_addition_([C], [Y|Ys], 0).
binary_addition_([X|Xs], [Y|Ys], C0) -->
        { [X,Y] ins 0..1,
          Sum #= X + Y + C0 },
        sum_carry(Sum, C),
        binary_addition_(Xs, Ys, C).

sum_carry(0, 0) --> [0].
sum_carry(1, 0) --> [1].
sum_carry(2, 1) --> [0].

示例查询及其解决方案:

?- binary_addition([1,0],[0,1,1], Sum).
Sum = [1, 1, 1] .

?- binary_addition([1,1],[1,0,1], Sum).
Sum = [0, 0, 0, 1] .

?- binary_addition([0,1],[1,1], Sum).
Sum = [1, 0, 1] .

请注意，它也适用于另一个方向:

?- binary_addition(Xs, Ys, [1,1]).
Xs = [1, 1],
Ys = [] ;
Xs = [],
Ys = [1, 1] ;
Xs = [_G2510, 1],
Ys = [_G2522],
_G2510 in 0..1,
_G2510+_G2522#=1,
_G2522 in 0..1 ;
etc.

如果您想要反向列表，只需将 reverse/2 目标添加到 binary_addition/3 即可。