Lists of list exercsie in Prolog

Question

I have this exercise:

Write a deterministic Prolog program test( +List, ?Integer ) that succeeds if and only if Integer is the number of ways two different elements in List can be selected such that the first has exactly one element more than the second.

Sample query:

?- test( [ [], [0], [0,0], [0,1], [1,0] ], N ).
N = 5

But i cannot figure out how i would do this. Hope someone can help

Answer 1

Here is an idea, while completely removing any thought about performance:

Subgoal:

1. Select a first element (which is a list) using member/2; AND
2. Select a second element (which is a list) using member/2; AND
3. Compute the length of the first selected element/list using length/2; AND
4. Compute the length of the second selected element/list using length/2; AND
5. Make sure that the two lengths fit your length constraint using </2
   • Which will fail if this is not the case, backtracking back up this list
   • But if it suceeds, this goal succeeds.

Collect all the solutions of the subgoal using bagof/3

Answer 2

Prolog can be... difficult to wrap your head around when you are starting out.

First, try writing a predicate that will, on backtracking, return the entire cartesian join of the list against itself, something like this:

test( List, result( A, B ) ) :-
  member( A, List ),
  member( B, List )
  .

Running that with the test data: test( [ [], [0], [0,0], [0,1], [1,0] ], R ). will successively return 25 results (the sample list has 5 items in it, so 5 × 5 gives us 25 results, right?):

R = result( []    , []     )
R = result( []    , [0]    )
R = result( []    , [0, 0] )
R = result( []    , [0, 1] )
R = result( []    , [1, 0] )
R = result( [0]   , []     )
R = result( [0]   , [0]    )
R = result( [0]   , [0, 0] )
R = result( [0]   , [0, 1] )
R = result( [0]   , [1, 0] )
R = result( [0, 0], []     )
R = result( [0, 0], [0]    )
R = result( [0, 0], [0, 0] )
R = result( [0, 0], [0, 1] )
R = result( [0, 0], [1, 0] )
R = result( [0, 1], []     )
R = result( [0, 1], [0]    )
R = result( [0, 1], [0, 0] )
R = result( [0, 1], [0, 1] )
R = result( [0, 1], [1, 0] )
R = result( [1, 0], []     )
R = result( [1, 0], [0]    )
R = result( [1, 0], [0, 0] )
R = result( [1, 0], [0, 1] )
R = result( [1, 0], [1, 0] )

Once you have that, it's easy to compute the difference in length between the 2 sublists:

test( List, result( A, B ) ) :-
  member( A, List ),
  member( B, List ),
  length( A, L1   ),
  length( B, L2   ),
  Delta is L1 - L2
  .

And even easier to filter on that:

test( List, result( A, B ) ) :-
  member( A, List ),
  member( B, List ),
  length( A, L1   ),
  length( B, L2   ),
  Delta is L1 - L2,
  Delta = 1
  .