0
intersection([],L1,L2,L3).
intersection([H|T],L2,L3,[H|L4]):-member(H,L2),intersection(T,L3,L3,L4).
member(H,[H|T]).
member(X,[H|T]):-member(X,T).

This code makes the third list from the first and second list.

last([U],U).
last([_|L3],U) :- last(L3,U).

This piece of code looks for the last item in the list.
My problem is that I can’t figure out how to make these two pieces of code fit into one. That is, the program should find duplicate elements in the first and second list and display them in the third, and from the third list, display the last element multiplied by 3.

false
  • 10,264
  • 13
  • 101
  • 209
GOOse
  • 13
  • 2

1 Answers1

0

The main problem is intersection/4. I assume you wanted to write a deterministic predicate intersection/3 the first two arguments of which are fully instantiated at call time and the last argument of which is an output argument. By deterministic, I mean that intersection/3 should succeed exactly once without leftover choice points. The SWI-Prolog documentation contains a useful overview of determinism and mode declarations (although it does not enforce them).

It is useful to begin by writing a declarative specification of the predicate following the inductive definition of lists:

  1. The intersection of [] and Ys is [].
  2. The intersection of [A|Xs] and Ys is A prepended to the intersection of Xs and Ys if A is a member of Ys.
  3. The intersection of [A|Xs] and Ys is the intersection of Xs and Ys if A is not a member of Ys.

The simplest translation of this specification into standard Prolog is:

intersection([],_,[]).
intersection([A|Xs],Ys,[A|Zs]) :-
    member(A,Ys),
    intersection(Xs,Ys,Zs).
intersection([A|Xs],Ys,Zs) :-
    \+ member(A,Ys),
    intersection(Xs,Zs).

If the first call to member/2 succeeds the second should fail. In order to avoid backtracking, unifying the current goal with the head of the second clause, and performing a redundant call to member/2, we place a cut after the occurrence of member/2 in the second clause.

intersection([],_,[]).
intersection([A|Xs],Ys,[A|Zs]) :-
    member(A,Ys),
    !,
    intersection(Xs,Ys,Zs).
intersection([_|Xs],Ys,Zs) :-
    intersection(Xs,Ys).

If the current goal unifies with the head of the first clause, it will not unify with the heads of later clauses. In order to prevent spurious backtracking, we place a cut in the (empty) body of the first clause. Whether this cut is necessary depends on your choice of Prolog implementation. 

intersection([],_,[]) :-
    !.
intersection([A|Xs],Ys,[A|Zs]) :-
    member(A,Ys),
    !,
    intersection(Xs,Ys,Zs).
intersection([_|Xs],Ys,Zs) :-
    intersection(Xs,Ys).

We are only interested in checking membership in the second list. Thus, we can replace the occurrence of member/2 with the semideterministic predicate memberchk/2. Here, semideterministic means that memberchk/2 succeeds or fails exactly once without leftover choice points.

intersection([],_,[]).
    !.
intersection([A|Xs],Ys,[A|Zs]) :-
    memberchk(A,Ys),
    !,
    intersection(Xs,Ys,Zs).
intersection([_|Xs],Ys,Zs) :-
    intersection(Xs,Ys).

This implementation of intersection/3 is nearly identical to the implementation found in the SWI-Prolog library lists.pl. You can combine this predicate with an implementation of last/2 in order to complete your program. For example:

last_duplicate_tripled(Xs,Ys,N) :-
    intersection(Xs,Ys,Zs),
    last(Zs,M),
    N is M * 3.

From here, I recommend doing the following:

  1. Implement intersection/3 using metalogical predicates like findall/3.
  2. Read @false's answer to this question.
  3. Read @repeat's answer to this question.

They are doing something much more interesting and sophisticated than I attempted in this answer.

emi
  • 5,380
  • 1
  • 27
  • 45