CODEWITHSUNDEEP
recursionprolog
Gabriel Copat
Gabriel Copat

Reputation: 11

Prolog - Recursion exiting giving the wrong value

So I made this code to find the intersection between two lists.

intersect([], _, C).
intersect([A1|AS], B, C) :-
    member(A1, B), length(C, L), L =:= 0, intersect(AS, B, [A1]);
    member(A1, B), length(C, L), L =\= 0, append(C, [A1], D), intersect(AS, B, D);
    intersect(AS, B, C).

And it indeed finds the intersections when the list A is empty, however it the value for C will be an empty list. Using trace on this command "intersect([1,2,3,4,5,6,7,8],[4,5,6], C)." I get this:

    > Call: (16) intersect([], [4, 5, 6], [4, 5, 6]) ? creep    Exit: (16) 
    > intersect([], [4, 5, 6], [4, 5, 6]) ? creep    Exit: (15)
    > intersect([8], [4, 5, 6], [4, 5, 6]) ? creep    Exit: (14)
    > intersect([7, 8], [4, 5, 6], [4, 5, 6]) ? creep    Exit: (13)
    > intersect([6, 7, 8], [4, 5, 6], [4, 5]) ? creep    Exit: (12)
    > intersect([5, 6, 7, 8], [4, 5, 6], [4]) ? creep    Exit: (11)
    > intersect([4, 5, 6, 7, 8], [4, 5, 6], []) ? creep    Exit: (10)
    > intersect([3, 4, 5, 6, 7, 8], [4, 5, 6], []) ? creep    Exit: (9)
    > intersect([2, 3, 4, 5, 6, 7, 8], [4, 5, 6], []) ? creep    Exit: (8)
    > intersect([1, 2, 3, 4, 5, 6, 7, 8], [4, 5, 6], []) ? creep

Note how at the Call the value of C has been found and it is correct. However as it exits the recursion it just reverts back to its original value, how can I fix this? (If I add write(C) at the base case it will print the right value.)

Upvotes: 1

Views: 61

Answers (1)

false
false

Reputation: 10102

Here is a specialization of your program by adding false goals:

intersect([], _, C).
intersect([A1|AS], B, C) :-
   (  false, member(A1, B), length(C, L), L =:= 0,
      intersect(AS, B, [A1])
   ;  false, member(A1, B), length(C, L), L =\= 0,
      append(C, [A1], D),
      intersect(AS, B, D)
   ;  intersect(AS, B, C)
   ).

By adding false certain solutions have been removed. However, what remains is the last alternative, which always applies. You need to address this.

And write in stead of length(C, L), L =:= 0 rather C = [] and instead of length(C, L), L =\= 0 rather C = [_|_].

Upvotes: 5

Related Questions