Eliminuj kolejne duplikaty elementów listy za pomocą prologu
Pierwotnym problemem było wymyślenie sposobu na uzyskanie następujących rzeczy
remove([a,a,a,b,q,q,q,q,e,e,e]),X)
X = [a,b,q,e]
Odpowiedzi
Możemy rozwiązać ten problem, wykonując jedną iterację wzdłuż listy. W dowolnym miejscu na liście sprawdzamy aktualny element i następny element, jeśli są takie same, to ignorujemy bieżący element, w przeciwnym razie, jeśli są różne, bierzemy bieżący element.
rm_dup([], []).
rm_dup([X], [X]).
rm_dup([X1, X2 | Xs], [X1 | Ys]) :-
dif(X1, X2), rm_dup([X2|Xs], Ys).
rm_dup([X, X | Xs], Ys) :-
rm_dup([X | Xs], Ys).
Pierwsza i druga klauzula to klauzule podstawowe, w których nie ma zduplikowanych elementów. Trzecia i czwarta klauzula to reguły rekurencyjne.
W trzeciej klauzuli stwierdzamy, że jeśli lista wejściowa ma dwie wartości X1
i X2
i są one różne dif(X1, X2)
, to zachowaj bieżącą wartość.
W czwartej klauzuli, jeśli mamy te same kolejne wartości, to ignorujemy bieżącą wartość.
Trzecia i czwarta klauzula wykluczają się wzajemnie, dlatego aby predykat był deterministyczny, lepiej połączyć je w następujący sposób
rm_dup([X], [X]) :- !.
rm_dup([X1, X2 | Xs], Ys) :-
dif(X1, X2) -> (rm_dup([X2 | Xs], Ys1), Ys = [X1 | Ys1]);
rm_dup([X2 | Xs], Ys).
Jeszcze lepiej jest po prostu użyć równości jako warunku i odwrócić klauzule then i else .
rm_dup([X], [X]) :- !.
rm_dup([X1, X2 | Xs], Ys) :-
X1 = X2 -> rm_dup([X2 | Xs], Ys);
rm_dup([X2 | Xs], Ys1), Ys = [X1 | Ys1].
Trochę długo, ale to rozwiązało problem.
delete(_,[],[]).
delete(X,[X|T],R):- delete(X,T,R).
delete(X,[H|T],[H|R]) :- delete(X,T,R).
remove([],[]).
remove([H|T], [H|R]) :-
member(H,T),!,
delete(H,T,R1),
remove(R1,R).
remove([H|T],[H|R]):-
remove(T,R).