CODEWITHSUNDEEP
listrecursionprolog
Drew Amsden
Drew Amsden

Reputation: 1

Removing consecutive elements from a list in Prolog

So far I've tried to have three separate functions, one of which is the first called function, the other two decide whether or not to append the element passed to our result list if it does not match the head of the list. Recursion confuses me as it confuses many others so somewhere here I've got an infinite loop that causes the stack to overflow. But I'm not sure on a lot of prolog concepts (or syntax) so I'm confused where I'm going wrong here. Thank you for the help!

append( [], X, X).                                  
append( [X | Y], Z, [X | W]) :- append( Y, Z, W). 

remove([], []).
remove([H|T], X) :-
    append(X, [H], X),
    remove(T, H, X),
    !.
remove([Y|T], Y, X):-
    remove(T, Y, X),
    !.
remove([H|T], Y, X):-
    append(X,[H], X),
    remove(T,Y,X),
    !.

Upvotes: 0

Views: 113

Answers (1)

Nicholas Carey
Nicholas Carey

Reputation: 74197

Well... first off, Prolog has no "functions": it has predicates.

If I understand your problem statement, you want to "remove consecutive elements from a list", which I understand to mean as "collapse runs of identical elements to a single value", so that a list like:

[a,b,b,b,,c,c,d,e,e,e,e]

is reduced to

[a,b,c,d,e]

Assuming that that is the case, you don't need (or want) append/3. The general scheme is to

  • Recurse down to the end of the list, then
  • As you pop up the call stack, you repeatedly either add or omit the current item, based on the head of the returned list

Like so:

remove( []     , [] ) .
remove( [X|Xs] , Ys ) :- remove(Xs,Ts), try_add(X,Ts,Ys) .

try_add/3 is responsible for deciding whether to add/prepend an item to the returned list. It, too, is trivial:

  • If the returned list is empty, then prepend the candidate X to it.
  • If the returned list is non-empty, then test the candidate X with the head of the returned list:
    • If they are unifiable, omit the candidate X,
    • Otherwise, prepend the candidate X to the returned list
try_add( X , []     ,      [X] ) .
try_add( X , [T|Ts] ,   [T|Ts] ) :- X  = T.
try_add( X , [T|Ts] , [X,T|Ts] ) :- X \= T.

Putting all together, you get this:

remove( []     , [] ) .
remove( [X|Xs] , Ys ) :- remove(Xs,Ts), try_add(X,Ts,Ys) .

try_add( X , []     ,      [X] ) .
try_add( X , [T|Ts] ,   [T|Ts] ) :- X  = T.
try_add( X , [T|Ts] , [X,T|Ts] ) :- X \= T.

This runs in O(n) time and space. Its drawback is that it is not tail-recursive, meaning that given a sufficiently long list, it will crash your program with a stack overflow.

Another, tail recursive approach — one that runs in O(n) time and O(1) space — is this:

remove( []     , [] ) .
remove( [X|Xs] , Ys ) :- remove(Xs, [X], Ts ), reverse(Ts,Ys) .

remove( []     , Ys     , Ys ) .
remove( [X|Xs] , [T|Ts] , Ys ) :- X  = T , remove( Xs ,  [X|Ts] , Ys ) .
remove( [X|Xs] , [T|Ts] , Ys ) :- X \= T , remove( Xs ,[X,T|Ts] , Ys ) .

Its drawback is that it builds the return list in reverse order, so that another traversal via reverse/2 is required to put things back in the correct order.

Upvotes: 1

Related Questions