Prolog - solving problems with lists

Question

Hello I have to solve some prolog problems with lists but i can't figure it out how these work. I have to add "1" after every even element in a list, and to make the difference of 2 lists. I know this seems easy, in other language like java or c# i would make it very easy, but prolog it's giving me headaches. Please help me :|

For the first problem: do you have to add 1 to a number or do you have to append "1" to a string. What is the type of your list elements? And for the second: how do you define "difference" between two lists? Do you mean that A - B = C (A, B, C are lists) where C[i] = A[i] - B[i]? — sve
For me, when writing Prolog, it helps to think of rules that define what I want in natural language form initially. Usually, there are more than one. For example, "The result of inserting 1 after every even element in an EMPTY list is..." (and here you'd indicate if you want [1] or []. Then you might have another rule that gives a recursive definition of what you want based upon the list's head and tail ([H|T]) or possibly two elements from the head and the tail ([H1, H2|T]). Then you translate the natural language into Prolog statements. — lurker
For the first one example: [4,3,5,7,2,6,3] -->[4,3,1,5,1,7,1,2,6,3,1] And the diferrence: A=[3,4,5,6,7], B=[4,7] --> C=[3,5,6] — jojuk
Your example inserts a 1 after every odd element. Is that what you intended? — lurker
That seems to be a class assignment. Sorry to look like an old boring man but, before doing the homework, I would recommend you to first read your course notes and try to understand the easier examples your professor already gave you. — Aurélien

Nicholas Carey Nicholas Carey · Accepted Answer · 2013-10-22T22:59:19

Edited to note the clarified problem statement ("even item" meaning the item's value is even (rather than the item's ordinal position within the list):

insert_one_after_even_items( [] , [] ).             % if the source list is exhaused, we're done.
insert_one_after_even_items( [X|Xs] , [X,1|Ys] ) :- % otherwise, 
   0 is X mod 2 ,                                   % - if the number is even, prepend it and a 1 to the result list, and
   insert_one_after_even_items( Xs , Ys )           % - recurse down.
   .                                                %
insert_one_after_even_items( [X|Xs] , [X|Ys] ) :-   % otherwise,
   1 is X mod 2 ,                                   % - if the number is odd, prepend it to the result list, and
   insert_one_after_even_items( Xs , Ys )           % - recurse down.
   .                                                % Easy!

For your second problem, producing the difference between two lists, are you talking about set differences? If so, given two sets A and B, are you talking about the relative difference (all elements of A that do not exist in B), or the absolute difference (all elements of either A or B that do not exist in both sets)?

To solve the relative set difference problem (Find all members of A that do not also exist in B), you can use the built-in member/2 predicate:

relative_difference( [] , _ , [] ) .          % if the source list is exhausted, we're done
relative_difference( [A|As] , Bs , R ) :-     % if the source list is non-empty, and
  member(A,Bs) ,                              % - the current A is an element of B,
  ! ,                                         % - we insert a deterministic cut (no backtracking)
  relative_difference( As , Bs , R )          % - and recurse down, discarding the current A
  .                                           %
relative_difference( [A|As] , Bs , [A|R] ) :- % if the source list is non-empty (and A is not an element of B due to the cut inserted earlier)
  relative_difference( As , Bs , R )          % we simply add A to the result list and recurse down.
  .

One thing you will note here: we are building the result list in all of these examples is built from a variable. The tail of the list is unbound (and passed as the new result to the next recursive call, where it either become a new list node or, at the very end, the empty list.

This has the effect of

building the list in order (rather than in reverse order).
if the result was bound on the initial call, unification against the expected result occurs item by item as the recursion proceeds, which means
execution is short-circuited when the first unification failure occurs.

If your prolog implementation doesn't have member/2 as a built in, it's easy enough to implement. Something like this ought to do it:

member(X,[X|T]) :- ! .           % A hit! cut and succeed.
member(X,[_|T]) :- member(X,T) . % ... and a miss. Just recurse down on the tail.

Prolog - solving problems with lists

1 Answers