CODEWITHSUNDEEP
listprologprimes
Qiri
Qiri

Reputation: 251

Prolog list accidentally reversing

I am having trouble writing code in Prolog which takes a list, removes all primes, and returns the rest of the list. I have written a prime checker predicate, prime/1, which works just fine, but when I apply my program to the list, as with almost anything I try to do in Prolog, I get back the list without the primes, as wanted, but in reverse order. 

primemover(L, Lcomp):-
    primeremover(L, [], Lcomp).
primeremover([], A, A).
primeremover([H | T], A, X):-
    \+ prime(H),
    primeremover(T, [H | A], X).
primeremover([H | T], A, X):-
    prime(H),
    primeremover(T, A, X).

I can see why the list comes back reversed by looking at my code, but I just can't find a way around it. If I try reversing the head and tail of the recursive case which moves the non-prime into the middle list, it works and comes out in the correct order, but with every value in its own nested list, which is even worse than coming out backwards.

Is there a simple way to correct this issue?

Upvotes: 1

Views: 434

Answers (4)

Will Ness
Will Ness

Reputation: 71099

Here is a minimal edit of your code to correct the issue. 

%%// primeremover( +L, -Lcomp) 
primeremover(L, Lcomp):-             %// was:
    primeremover(L, [], Lcomp).
primeremover([], A, A).
primeremover([H | T], A, [H | X]):-  %// primeremover([H | T], A, X):-
    \+ prime(H),
    primeremover(T, A, X).           %//     primeremover(T, [H | A], X).
primeremover([H | T], A, X):-
    prime(H),
    primeremover(T, A, X).

Instead of prepending - adding at the front - elements to an accumulator, and returning its final value from the deepest invocation, we append - add at the end - elements to the return list, and set its final end pointer as [] at the deepest invocation. Both are essentially iterative processes, and both are compiled by Prolog as such, i.e. with constant control stack space use.

Both variants are tail recursive, but the new one is tail recursive modulo cons.

Because the variable A no longer serves as an accumulator, and is used instead as a final "pointer" (list's last cons cell), it is customary to call it Z instead.

The new code demonstrates the "difference list" technique: the logical variables A and X form a pair, describing a list's prefix from X to A as a "difference" between a list X and its tail A.

We thus get hold of the end value explicitly, in the interface call:

primeremover(L, Lcomp):-        
    primeremover(L, E, Lcomp), E = [].

We could use any value for E, as we need, not just the hard-coded [], by directly calling the primeremover/3 predicate.

This is actually more natural to code in Prolog, than the usual imperative "accumulator" technique (by cons, prepending), unless we actually need to build our result in reversed order. Although, appending elements to the end of open-ended list can just as rightfully be seen as accumulating.

Upvotes: 1

Paulo Moura
Paulo Moura

Reputation: 18663

You're using in your primeremover/3 predicate the second argument as an accumulator, i.e. an auxiliary argument that works as a stack, collecting intermediate results. This (useful) technique is often used in the definition of recursive predicates to get the benefits of tail recursion. A canonical example of this technique is the definition of a predicate for reversing a list. The naive definition is not tail recursive and thus requires space proportional to the length of the list:

reverse([], []).
reverse([Head| Tail], Reversed) :-
    reverse(Tail, Reversed0),
    append(Reversed0, [Head], Reversed).

Note that the recursive call in the second clause to the reverse/2 predicate is not the last call. Thus, the append/3 predicate call that follows must be suspended by saving it in a stack until the recursive reverse/2 predicate terminates. This stack grows one element per each recursive call. But this stack will not be required if the recursive call is the last call. The tail recursive definition can be coded using an accumulator:

reverse(List, Reversed) :-
    reverse(List, [], Reversed).

reverse([], Reversed, Reversed).
reverse([Head| Tail], List, Reversed) :-
    reverse(Tail, [Head| List], Reversed).

But, in your specific case, and as both Erwin and Guillermo explained, there's no need to use an accumulator as you can construct the output list as you traverse the input list. The code they suggested can be, however, arguably improved by avoiding testing if the current head of the input list is a prime twice (in the case of Erwin solution) and also by avoiding a cut (in case of the Guillermo solution) by using Prolog's standard if-then-else control construct:

prime_remover([], []).
prime_remover([Head| Tail], NonPrimes):-
    (   prime(Head) ->
        prime_remover(Tail, NonPrimes)
    ;   NonPrimes = [Head| NonPrimesTail),
        prime_remover(Tail, NonPrimesTail)
    ).

Note that this version is (also) tail recursive.

Upvotes: 2

Guillermo Merino
Guillermo Merino

Reputation: 3257

You don't need to call an auxiliar function to do this, you can do it directly by using only the input variable and the return

Code:

primeremover([], []).

primeremover([H | T], Y):-
    prime(H),
    !,
    primeremover(T, Y).

primeremover([H | T], [H | Y]):-
        primeremover(T, Y).

Upvotes: 2

Erwin Bolwidt
Erwin Bolwidt

Reputation: 31279

I think this fixes your problem:

primeremover([], []).
primeremover([H | T], [H | Y]):-
    \+ prime(H),
    primeremover(T, Y).
primeremover([H | T], Y):-
    prime(H),
    primeremover(T, Y).

I'm not sure if I am missing something, but I believe that you are approaching this as a functional language rather than a logical language. Also, the third argument doesn't really seem to add something to the solution; it can be removed without loss of functionality.

I don't have your prime predicate but I used this to test:

main :- primeremover([1,2,3,4,5], A), write(A).

prime(X) :- X = 2; X = 3; X = 5.

I used GNU Prolog (1.4.0).

Upvotes: 4

Related Questions