从某些序言列表中删除不变量？

Question

我正在搜索一些谓词：

reduce_2n_invariant(+I, +F, -O)

基于：

一些输入列表I
形式为fx、

F

生成一些输出列表 O，满足以下一般条件：

∀x:(x ∈ O ↔ ∀ n ∈ ℕ ∀ y ∈ O: x ≠ F(F(...F(y)...)),

因此 F 被应用 2 times n 次到 y。

他们有使用 swi-prolog 的简单方法吗？

例如名单

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 应该导致：

O = [a, b, f(f(c)), f(f(f(a))), f(b)]

到目前为止我的代码：

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

导致错误消息：

/test.pl:2:5: Syntax error: Operator expected
/test.pl:4:5: Syntax error: Operator expected

调用后：

invariant_2(a,f,f(f(a))).

Answer 1

错误消息是由于 Prolog 不接受带有 variable 函子的条款。因此，例如，目标 Y2 = F(F(Y0)) 应编码为 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).

如果 List 是一个列表，Term =.. List 形式的目标（其中 ISO 运算符 =.. 被称为 univ）成功第一项是 Term 的 functor，其余项是 Term 的 arguments。使用此运算符，谓词 invariant_2/3 可以定义如下：

invariant_2(X, F, Y2) :-
    (   Y2 =.. [F, Y1],
        Y1 =.. [F, Y0]
    ->  invariant_2(X, F, Y0)
    ;   Y2 = X ).

示例：

?- 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.

reduce_2n_invariant/3的规范我不是很清楚，因为似乎输入列表项的处理顺序可能会改变获得的结果。无论如何，我认为你可以这样做：

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

示例：

?- 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)].

Answer 2

@slago 比我快了几分钟，但既然我已经写好了，我还是 post 它：

我回避 findall，因为不变量的否定很难直接表达。特别是，不变量比较的术语必须是我实现的基础（例如 [f(a), f(g(f(a)))] 不应丢失任何术语，但 [f(a), f(f(f(a)))] 应减少为 [f(a)] 这意味着定义的基本情况可以'在两个术语不在这种关系中的情况下，只是参数形状的模式匹配）。

另一个问题已经解释过了，因为 F=f, X=F(t) 在语法上不正确，我们需要 meta-logical =.. 来表达这个。

term_doublewrapped_in(X, Y, Fun) :-
    Y =.. [Fun, T],
    T =.. [Fun, X].
term_doublewrapped_in(X, Y, Fun) :-
    Y =.. [Fun, T],
    T =.. [Fun, Z],
    term_doublewrapped_in(X, Z, Fun).

除了 term_doublewrapped_in 当第二个参数包含变量时不一定终止外，由于默认情况下禁用发生检查，它也可能导致错误的答案：

?- term_doublewrapped_in(X, f(X), F).
X = f(X),    % <-- cyclic term here
F = f ;
% ...

因此，该程序的健全性实际上需要基础条件。

我刚刚将这个概念提升到列表中：

anymember_doublewrapped_in(Terms, X, F) :-
    member(T, Terms),
    term_doublewrapped_in(T,X,F).

并将其包装成 filter/3 的变体，否定给定的谓词：

functor_list_reduced_acc(_F, _L, [], []).
functor_list_reduced_acc(F, L, R, [X|Xs]) :-
    anymember_doublewrapped_in(L, X, F)
    -> functor_list_reduced_acc(F, L, R, Xs)
    ;  ( R = [X|Rs], functor_list_reduced_acc(F, L, Rs, Xs) ).

functor_list_reduced(F,L,R) :-
    functor_list_reduced_acc(F,L,R,L).

我首先尝试使用 partiton/4 来做同样的事情，但随后我们需要包含库（lambda）或类似的实现来动态实例化不变量到正确的 F 和列表元素.

从某些序言列表中删除不变量？

Remove invariants from some prolog list?

reduce

invariants

prolog