Supprime les membres de la liste donnée, qui apparaissent après une sous-liste

Question

J'essaie d'enlever tous les membres d'une liste apparaissant après une sous-liste [z,z,z] en Prologue. f.ex removeafterZZZ([a,b,c,z,z,z,a], X) -> X = [a,b,c,z,z,z].

J'ai les méthodes sous-liste y rejoindre donné.

    % 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).

J'ai donc réfléchi à trois "options" d'entrée possibles :

1) []

2) quelque chose comme [a,b,c], [a,b,c,z,z] , où la sortie serait automatiquement == entrée

3) quelque chose comme [a,b,c,z,z,z,a]

J'ai donc pensé à 3 règles :

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

Cela ne fonctionne évidemment pas de cette façon, comment puis-je savoir si j'ai déjà écrit z,z,z dans la liste de sortie ? Devrais-je utiliser un compteur ? Comment ?

Answer 1

Je pense que vous devez vous préoccuper de trois cas (donc trois règles...)

1. Liste vide []
2. Liste commençant par [z,z,z]
3. Liste non vide qui ne commence pas par [z,z,z]

Pensez à la façon dont vous résoudriez ce problème dans un langage traditionnel : vous parcourez la liste jusqu'à ce qu'elle se termine ou que vous trouviez un élément de la liste. [z,z,z] motif au milieu.

Answer 2

Si vous êtes autorisé à utiliser append (il s'agit d'un prédicat de liste standard fourni avec prolog), voici une méthode générique pour supprimer un suffixe --

% 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).

Il utilise une coupe, donc c'est un peu moche, mais sinon le prédicat 2 donnera un tas de résultats si vous passez dans [] (ouais ouais, coupe rouge, peu importe).

Voici comment cela fonctionne, si le suffixe n'est PAS un membre de la liste, l'option 2 est activée et X et Z sont égaux. Sinon, elle dit "il existe deux listes, A et B, qui peuvent constituer ma liste d'origine. Cette deuxième liste, B, commence par mon suffixe, et contient ensuite tout (et je me fiche de ce que c'est). Puisque je sais que A est tout ce qui précède le suffixe, alors mon résultat est A concaténé avec Y."

Notez que cela vous donnera des résultats multiples pour une liste telle que

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

Modifier pour ajouter : Vous pouvez supprimer la première ligne si vous êtes d'accord pour qu'une liste vide renvoie des résultats tels que

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

Answer 3

Même s'il s'agit d'un travail à domicile, une réponse complète a déjà été donnée, alors...

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