How to construct a list from two lists in prolog

Question

I am a newbie to prolog and I find it hard to think in a recursive manner. Suppose I have two lists: list1[0,0,0,1,1,0,1,1], list2[1,0,1,0,0,0,1,1]. And I want to return a list that has a 1 when either list1 or list 2 has a 1 at a corresponding position.

merge([H1|[]],[H2|[]],[H3|[]]):- H2 = 1, H3 = 1, H1 is 1.
merge([H1|T1],[H2|T2],[H3|T3]):- merge(T1,T2,T3), H2 = 1, H3 = 1, H1 is 1.

I know I can't writhe in the above forms, but this is as close to a prolog form as I can thing of right now. Recursion just seem so hard!

Answer 1

A good way to solve such tasks it to first describe the relation between single elements of each list, and then to use maplist/[2,3,4] to extend the same reasoning to lists.

For example:

either_is_one(0, 1, 1).
either_is_one(1, 0, 1).
either_is_one(1, 1, 1).

But what about the case where neither of the two lists has a "1" at a specific position? For now, I assume you then relate this to "0":

either_is_one(0, 0, 0).

Then, trivially, we use maplist/4 to relate lists of such elements to one another:

?- maplist(either_is_one, [0,0,0,1,1,0,1,1], [1,0,1,0,0,0,1,1], Ls).
Ls = [1, 0, 1, 1, 1, 0, 1, 1] ;
false.

Note that this is completely pure and also works in other directions. For example:

?- length(As, _), maplist(either_is_one, As, Bs, Cs).
As = Bs, Bs = Cs, Cs = [] ;
As = [0],
Bs = Cs, Cs = [1] ;
As = Cs, Cs = [1],
Bs = [0]
As = Bs, Bs = Cs, Cs = [1] ;
etc.

Answer 2

How about using a suitable arithmetic expression with clpfd?

:- use_module(library(clpfd)).

z_z_max(A,B,AB) :-
   [A,B,AB] ins 0..1,
   AB #= max(A,B).

Sample query using meta-predicate maplist/3:

?- maplist(z_z_max, [0,0,0,1,1,0,1,1], [1,0,1,0,0,0,1,1], Ls).
Ls = [1,0,1,1,1,0,1,1].           % succeeds deterministically

clpfd offers a high-level interface to control flow optimizations which can speedup backtracking search by orders of magnitude. Use it!

Answer 3

Use clpb!

Hat-tip to @mat! Twice, in fact: once to the commenter, once to the clpb implementer.

:- use_module(library(clpb)).

bool_bool_or(A,B,AB) :- sat(AB =:= A + B).

Sample queries using maplist/4:

?- maplist(bool_bool_or, [1,1,1], Bs, ABs).
ABs = [1,1,1], Bs = [_X,_Y,_Z], sat(_X=:=_X), sat(_Y=:=_Y), sat(_Z=:=_Z).

?- maplist(bool_bool_or, [1,1,1], _, ABs).
ABs = [1,1,1].

?- maplist(bool_bool_or, [0,0,0,1,1,0,1,1], [1,0,1,0,0,0,1,1], ABs).
ABs = [1,0,1,1,1,0,1,1].