Prolog Binary Addition Issue?

I have this piece of homework that I have to write in Prolog.The requirement is to write a piece of code that does binary addition such as:

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

And so, this is the code that I came up with:

add([],[], _).
add([],Y, Z) :- append([], Y, Z).
add(X,[], Z) :- append(X,[],Z).
add([HX|TX],[HY|TY], Z) :-
    HX = 1,
    HY = 1,
    add(TX,TY, Z1),
    add([1],Z1, Z2),
    append([0],Z2,Z),!.
add([HX|TX],[HY,TY], Z) :-
    HX = 0,
    HY = 1,
    add(TX,TY,Z1),
    append([1],Z1, Z),!.
add([HX|TX],[HY|TY], Z) :-
    HX = 1,
    HY = 0,
    add(TX,TY,Z1),
    append([1],Z1, Z),!.
add([HX|TX],[HY,TY], Z) :-
    HX = 0,
    HY = 0,
    add(TX,TY,Z1),
    append([0],Z1, Z),!.

It seems to do what I needed, however, there are strange issues with it that I can not understand, so if someone could guide me to what I have done wrong, I would be glad.

Results:

?- add([1,1,1,1], [1,1],Z).
Z = [0, 1, 0, 0, 1]. % this is correct

?- add([1], [1],Z).
Z = [0, 1]. % this is correct

?- add([1,1,0,1], [1,1],Z).
Z = [0, 1, 1, 1]. % this is correct

?- add([1],[0],Y).
Y = [1|_G7100]. % there is an error here, but its not the big issue.

?- add([1,0,1], [1,1],Z).   
false. % no results are returned.

    104 ?- add([0], [1],Z).
    false. % no results returned either

Problem: Whenever there seems to be a 0 in the first binary list, under some conditions(still trying to figure them out), no results seems to be returned.but I can't seem to locate my error.Would be glad if someone can tell me what I did wrong.


There are 3 mistakes:

  • Rule #1: Should be add([],[],[]). instead of add([],[], _). . This fails for equal-length lists.
  • Rule #5 and #7: Should be add([HX|TX],[HY|TY], Z) instead of add([HX|TX],[HY,TY], Z) . This fails when the second list ( Y ) contains less than two elements.
  • Fix these and your code should run well: see here.


    I see you use 7 different rules, since you put the binary arithmetic inside the rules. You can do with 6 different rules plus a start rule as follows:

    add2(AL, BL, CL) :-
       add2(AL, BL, 0, CL).
    
    add2([A | AL], [B | BL], Carry, [C | CL]) :-
       X is (A + B + Carry),
       C is X rem 2,
       NewCarry is X // 2,
       add2(AL, BL, NewCarry, CL).
    add2([], BL, 0, BL) :- !.
    add2(AL, [], 0, AL) :- !.
    add2([], [B | BL], Carry, [C | CL]) :-
       X is B + Carry,
       NewCarry is X // 2,
       C is X rem 2,
       add2([], BL, NewCarry, CL).
    add2([A | AL], [], Carry, [C | CL]) :-
       X is A + Carry,
       NewCarry is X // 2,
       C is X rem 2,
       add2([], AL, NewCarry, CL).
    add2([], [], Carry, [Carry]).
    

    Here are some example runs:

    ?- add2([1,1,1,1], [1,1],Z).
    Z = [0,1,0,0,1]
    ?- add2([1], [1],Z).
    Z = [0,1]
    ?- add2([1,1,0,1], [1,1],Z).
    Z = [0,1,1,1]
    ?- add2([1],[0],Y).
    Y = [1]
    ?- add2([1,0,1], [1,1],Z).
    Z = [0,0,0,1]
    ?- add2([0], [1],Z).
    Z = [1]
    

    Main advantage of the above solution, less invocations of add2/4 and you could replace the //2 and rem 2, and do addition in some other number system as well.

    PS: Code taken from here.

    链接地址: http://www.djcxy.com/p/63996.html

    上一篇: 多通用Java通配符

    下一篇: Prolog二进制添加问题?