I am searching some predicate:
reduce_2n_invariant(+I, +F, -O)
based on:
IF of form fx,which generates some output list O, that satisfies following general condition:
∀x:(x ∈ O ↔ ∀ n ∈ ℕ ∀ y ∈ O: x ≠ F(F(...F(y)...)),
whereby F is applied 2 times n times to y.
Is their some easy way to do that with swi-prolog?
E.g. the list
l = [a, b, f(f(a)), f(f(c)), f(f(f(a))), f(f(f(f(a)))), f(b),f(f(b))]
with operator f should result in:
O = [a, b, f(f(c)), f(f(f(a))), f(b)]
My code so far:
invariant_2(X, F, Y) :-
Y = F(F(X)).
invariant_2(X, F, Y) :-
Y = F(F(Z)), invariant_2(X, F, Z).
reduce_2n_invariant(LIn, F, LOut) :-
findall(X, (member(X, LIn), forall(Y, (member(Y, LIn), not(invariant(Y,F,X))))), LOut).
leads to an error message:
/test.pl:2:5: Syntax error: Operator expected
/test.pl:4:5: Syntax error: Operator expected
after calling:
invariant_2(a,f,f(f(a))).
The error message is due to the fact that Prolog does not accept terms with variable functors. So, for example, the goal Y2 = F(F(Y0)) should be encoded as Y2 =.. [F,Y1], Y1 =.. [F,Y0]:
?- F = f, Y2 = f(f(f(a))), Y2 =.. [F,Y1], Y1 =.. [F,Y0].
F = f,
Y2 = f(f(f(a))),
Y1 = f(f(a)),
Y0 = f(a).
A goal of the form Term =.. List (where the ISO operator =.. is called univ) succeeds if List is a list whose first item is the functor of Term and the remaining items are the arguments of Term. Using this operator, the predicate invariant_2/3 can be defined as follows:
invariant_2(X, F, Y2) :-
( Y2 =.. [F, Y1],
Y1 =.. [F, Y0]
-> invariant_2(X, F, Y0)
; Y2 = X ).
Examples:
?- invariant_2(a, f, f(f(a))).
true.
?- invariant_2(a, f, f(f(f(a)))).
false.
?- invariant_2(g(a), f, f(f(g(a)))).
true.
?- invariant_2(g(a), f, f(f(f(g(a))))).
false.
The specification of reduce_2n_invariant/3 is not very clear to me, because it seems that the order in which the input list items are processed may change the result obtained. Anyway, I think you can do something like this:
reduce_2n_invariant(Lin, F, Lout) :-
reduce_2n_invariant_loop(Lin, F, [], Lout).
reduce_2n_invariant_loop([], _, Lacc, Lout) :-
reverse(Lacc, Lout).
reduce_2n_invariant_loop([X|Xs], F, Lacc, Lout) :-
( forall(member(Y, Lacc), not(invariant_2(Y, F, X)))
-> Lacc1 = [X|Lacc]
; Lacc1 = Lacc ),
reduce_2n_invariant_loop(Xs, F, Lacc1, Lout).
Example:
?- reduce_2n_invariant([a,b,f(f(a)),f(f(c)),f(f(f(a))),f(f(f(f(a)))),f(b),f(f(b))], f, Lout).
Lout = [a, b, f(f(c)), f(f(f(a))), f(b)].