1

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!

repeat
  • 18,496
  • 4
  • 54
  • 166
Louis Kuang
  • 727
  • 1
  • 14
  • 30

3 Answers3

2

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.
mat
  • 40,498
  • 3
  • 51
  • 78
  • Thanks, it worked. By the way, if I want to store this Ls for later use, Do I have to call this maplist everytime I want to use Ls, Or can I save it? – Louis Kuang Oct 30 '15 at 15:31
  • 1
    Your can easily introduce a new relation for this `your_relation(As, Bs, Cs) :- maplist(either_is_one, As, Bs, Cs).` – mat Oct 30 '15 at 15:37
2

Use !

Hat-tip to @mat! Twice, in fact: once to the commenter, once to the 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].
Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
1

How about using a suitable arithmetic expression with ?

:- use_module(library(clpfd)).

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

Sample query using 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

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

Community
  • 1
  • 1
repeat
  • 18,496
  • 4
  • 54
  • 166
  • 2
    +1! If one is reasoning over Boolean variables, I also recommend to check out CLP(**B**) constraints. For example: `bool_bool_or(X, Y, Or) :- sat(Or =:= X + Y).`, usable for example with `library(clpb)` in SICStus Prolog. Example query: `?- maplist(bool_bool_or, [1,1,1], _, Cs).`, yielding: `Cs = [1, 1, 1]`. – mat Oct 30 '15 at 17:23
  • 1
    I also did some microbenchmarks. clpfd is within a factor of 2 of `AB is A+B`, impressive... the 4-facts-variant is fastest, though... of course that is turned upside down once we look at the bigger picture! – repeat Oct 30 '15 at 17:27
  • 2
    Regarding speed: I recommend to simply use CLP(FD) constraints throughout, and forget about lower-level integer arithmetic, since not even speed advantages justify using lower-level features these days. Systems will only improve (and catch up) if the newer, more declarative features are being used. In practice, I would use either the CLP(FD) or CLP(B) version, or the spelt out version if the remaining case does not match the expressions. – mat Oct 30 '15 at 17:42
  • 2
    We're on the same page here... no surprise. – repeat Oct 30 '15 at 18:18