CODEWITHSUNDEEP
prolog
thenet
thenet

Reputation: 23

Remove members of given list, which appear after a sublist

I'm trying to remove of all members of a list appearing after a sublist [z,z,z] in Prolog. f.ex removeafterZZZ([a,b,c,z,z,z,a], X) -> X = [a,b,c,z,z,z].

I have the methods sublist and join given.

    % first argument is a sublist of the second argument
    sublist(Sublist, List):-
       join(_List1, List2, List),
       join(Sublist,_List3, List2).


    % we get the list in third argument by joining lists from first two arguments
    join([], L, L).
    join([Head | Tail1], List2, [Head | Tail3]):-
    join(Tail1, List2, Tail3).

So I've been thinking of 3 possible input "options":

1) []

2) something like [a,b,c], [a,b,c,z,z] , where the output automatically would be == input

3) something like [a,b,c,z,z,z,a]

So i thought of 3 Rules:

removeafterZZZ([],[]).   %for empty lists
removeafterZZZ(List,X) :=                   %for lists with no [z,z,z] sublist
       not ( sublist ( [z,z,z], List)) , 
       X = List.

removeafterZZZ([H|T], X) :=           %for lists with sublist [z,z,z]
       join(H, X, X),                 %join the head of list with X
       removeafterZZZ(T, X).          %call function again with tail

So that obviously doesn't work this way, how do i know if i already wrote z,z,z into the output list? Should I use a counter? How?

Upvotes: 2

Views: 751

Answers (3)

salva
salva

Reputation: 10234

Even if it is homework a complete response has already been given so...

remove_after([], _, []).
remove_after([H|L], P, O) :-
        (   append(P, _, [H|L])
        ->  O = P
        ;   O = [H|O1],
            remove_after(L, P, O1) ).

Upvotes: 1

Linear
Linear

Reputation: 22196

If you're allowed to use append (it's a standard list predicate supplied with prolog), here's a generic method to remove a suffix --

% removeAfterSuff(Original List, Suffix To Remove, Result)
removeAfterSuff(X, [], X) :- !.
removeAfterSuff(X, Y, X) :- \+ sublist(Y,X).
removeAfterSuff(X, Y, Z) :- append(A, B, X), append(Y, _, B), append(A,Y,Z).

It uses a cut, so it's a bit ugly, but otherwise predicate 2 will give a bunch of results if you pass in [] (yeah yeah, red cut, whatever).

Here's how it works, if the suffix is NOT a member of the list, option 2 activates and X and Z are equal. Otherwise it says "there exist two lists, A and B that can make my original list. This second list, B, starts with my suffix, and then contains everything (and I don't care what that stuff is). Since I know that A is everything before the suffix, then my result is A concatenated with Y."

Note that this will give you multiple results for a list like

[a,b,z,z,z,a,b,z,z,z]

Edit to add: You can remove the first line if you're okay with an empty list returning results like

removeAfterSuff([a,b,c], [], Z).
Z = []
Z = [a]
Z = [a,b]
Z = [a,b,c]

Upvotes: 1

hugomg
hugomg

Reputation: 69934

I think you need to worry about three cases (so three rules...)

  1. Empty list []
  2. List starting with [z,z,z]
  3. Non-empty list that doesn't start with [z,z,z]

Think of how you would solve this in a traditional language - you walk the list until it ends or you find a [z,z,z] pattern in the middle.

Upvotes: 1

Related Questions