Masking in Prolog

Question

I have recently been trying to figure out Prolog and been messing with lists of lists in Prolog. I am trying to create a sort of mask I suppose in p Prolog. I have a predicate that determines the difference between two lists of lists (L1 and L2 lets say) in Prolog and saves them as a list of a list(Lets say R). I have another predicate that simply states if the difference is equal to zero(noDifference). I would like to have two resulting lists of lists (M1 and M2) based off of L1 and L2 compared to the R. For example I would like to compare all values of L1 and L2 to R, if a negative value is at a location of R then the value in the same location of L1 is saved into M1. And if a positive value is at a location of R then the value in the same location of L2 is saved into M2 if that makes sense. Before all of this I check with my noDifference function to see if the difference is 0 and if so all values of M1 and M2's lists of lists will be 0.

This is what I have so far(I'm not sure if I started it right)

masker(L1,L2,R,M1,M2):- noDifference(R1), M1=R, M2=R1;

and for the rest of it here are what some example values should look like under the hood

L1=[[1,5,3,8],[1,5,3,8]]
L2=[[5,4,7,4],[5,4,7,4]]
R=[[4,-1,4,-4],[4,-1,4,-4]]
M1=[[0,5,0,8],[0,5,0,8]]Neg values of L1 at R are stored rest are 0)
M2=[[5,0,7,0],[5,0,7,0]](Pos values of L2 at R are stored rest are 0)

Any insight if what I am doing so far is right and how to properly formulate the subgoals/where I should go next would be awesome!

edit with ex predicate

?- masker([[1,5,3,8],[1,5,3,8]],
          [[5,4,7,4],[5,4,7,4]],
          [[4,-1,4,-4],[4,-1,4,-4]], M1, M2).
M1=[[0,5,0,8],[0,5,0,8]].
M2=[[5,0,7,0],[5,0,7,0]].

Pretend you have a working predicate and show us how you would use it and what answers you expect. — false, Jul 08 '16 at 19:40
You can't use `is/2` to unify variables. `is/2` is for evaluating an arithmetic expression and unifying the results with it's first argument. So `M1 is R1` and `M2 is R2` don't make sense. These should using unification: `M1 = R1` an `M2 = R2`. What's meant by, for example, `L1-[1,5,3,8]`? And `M1[0,5,0,8]` isn't valid Prolog syntax, so It's unclear what that means. — lurker, Jul 08 '16 at 20:45
Okay that makes sense thank you. Those were just examples of what the values were supposed to be equal to after the procedure I guess I wasnt sure how to make that very clear ! — bgibers, Jul 08 '16 at 21:00
@crosskid: Please do not remove (part of) your question. If you have an entirely new question, ask it separately. And if you just have some tiny additional thing to add, add it clearly at the end. Otherwise future visitors of this page would be confused. — false, Jul 13 '16 at 18:17

score 5 · Accepted Answer · answered Jul 08 '16 at 21:20

Think what your predicate should describe. It is a relation between five lists of lists which, according to the example you provided, are of same length. This suggests the base case with five empty lists. Otherwise the heads of all five lists are lists themselves, that are in a specific relation to each other, let's call it lists_mask_mlists/5. And of course the same should be true for the tails, which can be realized by a recursive goal. So your predicate masker/5 could look something like that:

masker([],[],[],[],[]).
masker([X|Xs],[Y|Ys],[M|Ms],[R1|R1s],[R2|R2s]) :-
   lists_mask_mlists(X,Y,M,R1,R2),
   masker(Xs,Ys,Ms,R1s,R2s).

The actual masking relation also has a base case with five empty lists. Otherwise there are two further cases:

1) The current masking element (head of the third list) is negative: The head of the first list is the head of the fourth list and the head of the fifth list is 0

2) The current masking element is positive: The head of the second list is the head of the fifth list and the head of the fourth list is 0

You can express that like so:

lists_mask_mlists([],[],[],[],[]).
lists_mask_mlists([X|Xs],[_Y|Ys],[M|Ms],[X|R1s],[0|R2s]) :-   % 1)
   M < 0,
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).
lists_mask_mlists([_X|Xs],[Y|Ys],[M|Ms],[0|R1s],[Y|R2s]) :-   % 2)
   M >= 0,
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).

With this predicate your example query yields the desired result:

   ?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[4,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[0,5,0,8],[0,5,0,8]],
M2 = [[5,0,7,0],[5,0,7,0]] ? ;
no

Note however, that due to < and >= this only works, if the third list is variable free. Replacing the first 4 in the third argument by a variable yields an instantiation error:

   ?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[X,-1,4,-4],[4,-1,4,-4]],M1,M2).
     ERROR at  clause 2 of user:masked/5 !!
     INSTANTIATION ERROR- =:=/2: expected bound value

If you intend to use the predicate with a third argument that is not variable free, you might like to consider using clpfd. Include the line

:-use_module(library(clpfd)).

in your source file and alter lists_mask_mlists/5 like so:

lists_mask_mlists([],[],[],[],[]).
lists_mask_mlists([X|Xs],[_Y|Ys],[M|Ms],[X|R1s],[0|R2s]) :-
   M #< 0,                                                    % <- here
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).
lists_mask_mlists([_X|Xs],[Y|Ys],[M|Ms],[0|R1s],[Y|R2s]) :-
   M #>= 0,                                                   % <- here
   lists_mask_mlists(Xs,Ys,Ms,R1s,R2s).

Now the second query works too:

   ?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[X,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[1,5,0,8],[0,5,0,8]],
M2 = [[0,0,7,0],[5,0,7,0]],
X in inf.. -1 ? ;
M1 = [[0,5,0,8],[0,5,0,8]],
M2 = [[5,0,7,0],[5,0,7,0]],
X in 0..sup ? ;
no

Would this same method work if the lists of list were longer then just two?? — bgibers, Jul 09 '16 at 02:21
@crosskid: Yes, if all corresponding lists are of the same length. That is, the lists of lists, that you pass as arguments, have to be the same length and the lists in those lists also got to have corresponding lengths. See this query for example: `?- masker([[1,5,3],[1,5,3,8],[1,2]],[[5,4,7],[5,4,7,4],[3,4]],[[4,-1,-4],[4,-1,4,-4],[-1,1]],M1,M2).` The inner lists are of different length to each other but of the same length as the other corresponding inner lists. So the query yields the result: `M1 = [[0,5,3],[0,5,0,8],[1,0]]` and `M2 = [[5,0,0],[5,0,7,0],[0,4]]` — tas, Jul 09 '16 at 08:21
@crosskid: If you just remove `=` in case 2), you can't match the `0`s. That's why the answer is *false*. You have to decide how you want to treat the `0`s. You can **a)** treat them as positive numbers, that corresponds to the answer I posted. **b)** treat them as negative numbers, then you use `M #=< 0` in case 1) and `M #> 0` in case 2). This yields the answer `M1 = [[0,5,3,8],[0,5,3,8]]` and `M2 = [[5,0,0,0],[5,0,0,0]]`. **c)** treat them as a special case, then you use `M #< 0` in case 1) and `M #> 0` in case 2) and add a rule for lists_mask_mlists/5 to handle the 3rd case: `0`. — tas, Jul 09 '16 at 16:28

score 4 · Answer 2 · edited May 23 '17 at 11:54

@tas has presented a good solution and explanation (+1).

Building on this code, I would like to improve the space efficiency of the program. Consider again the example query with the CLP(FD) based solution:

?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[4,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[0, 5, 0, 8], [0, 5, 0, 8]],
M2 = [[5, 0, 7, 0], [5, 0, 7, 0]] ;
false.

We see from the ; false that choice points were accumulated during the execution of this program, because it was not apparent to the Prolog engine that the clauses were in fact mutually exclusive.

Obviously, such programs use more memory than necessary to keep track of remaining choices.

Resist the temptation to impurely cut away branches of the computation, because that will only lead to even more problems.

Instead, consider using if_/3.

All it takes to apply if_/3 in this case is a very easy reification of the CLP(FD) constraint (#<)/2, which is easy to do with zcompare/3:

#<(X, Y, T) :-
        zcompare(C, X, Y),
        less_true(C, T).

less_true(<, true).
less_true(>, false).
less_true(=, false).

With this definition, the whole program becomes:

:- use_module(library(clpfd)).

masker([], [], [], [], []).
masker([X|Xs], [Y|Ys], [M|Ms], [R1|R1s], [R2|R2s]) :-
        lists_mask_mlists(X, Y, M, R1, R2),
        masker(Xs, Ys, Ms, R1s, R2s).

lists_mask_mlists([], [], [], [], []).
lists_mask_mlists([X|Xs], [Y|Ys], [M|Ms], R1s0, R2s0) :-
        if_(M #< 0,
            (R1s0 = [X|R1s], R2s0 = [0|R2s]),
            (R1s0 = [0|R1s], R2s0 = [Y|R2s])),
        lists_mask_mlists(Xs, Ys, Ms, R1s, R2s).

And now the point:

?- masker([[1,5,3,8],[1,5,3,8]],[[5,4,7,4],[5,4,7,4]],[[4,-1,4,-4],[4,-1,4,-4]],M1,M2).
M1 = [[0, 5, 0, 8], [0, 5, 0, 8]],
M2 = [[5, 0, 7, 0], [5, 0, 7, 0]].

This example query is now deterministic!

And the program is still general enough to also handle the second example query!

3

Nice improvement indeed. +s(0) – tas Jul 09 '16 at 10:42

Masking in Prolog

2 Answers2

Linked