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

发布于 2025-01-23 07:00:36 字数 1067 浏览 0 评论 0原文

我正在搜索一些谓词：

reduce_2n_invariant(+I, +F, -O)

基于：

一些输入列表i
表单fx的一些输入操作员 f

生成了一些输出列表o，满足一般条件：

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

f被应用2次n次到y。

他们的某种简单方法可以使用SWI-Prolog做到这一点吗？

例如，使用运算符f的列表

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

应导致：

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

原文

I am searching some predicate:

reduce_2n_invariant(+I, +F, -O)

based on:

some input list I
some input operator F 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))).

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

风筝在阴天搁浅。 2025-01-30 07:00:36

错误消息是由于Prolog不接受变量函数的术语。因此，例如，目标y2 = f（f（y0））应编码为y2 = .. [f，y1]，y1 = .. [f，y0] < /code>：

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

表单term = .. list的目标（其中ISO操作员 = .. 被称为 univ ），如果list是一个列表，其第一个项目为术语的函数，其余项目是term term的参数。使用此操作员，可以将谓词variant_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.

redaim> redaim_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)].

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

回复收藏 0 原文

断舍离 2025-01-30 07:00:36

@slago击败了我几分钟，但是由于我已经写了它，我仍然会发布它：

我回避了Findall，因为不变的否定很难直接表达。特别是，由不变性比较的术语必须是我实施的基础（例如[f（a），f（g（f（a））） 不应丢失任何条款，而是[ f（a），f（f（f（a）））应将缩小为[f（a）]，这意味着定义的基本情况不仅仅是模式在此情况下，参数形状的匹配不在此关系中）。

另一个问题已经解释了，在f = f，x = f（t）上不是句法正确的，我们需要元逻辑= ..来表达这一点。

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和列表元素动态实例化。

@slago beat me by a few minutes but since I've already written it, I'll still post it:

I'm shying away from the findall because the negation of the invariant is very hard to express directly. In particular, terms compared by the invariant must be ground for my implementation (e.g. [f(a), f(g(f(a)))] should not lose any terms but [f(a), f(f(f(a)))] should reduce to [f(a)] which means that the base case of the definition can't just pattern match on the shape of the parameter in the case two terms are not in this relation).

The other problem was already explained, in that F=f, X=F(t) is not syntactically correct and we need the meta-logical =.. to express this.

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

Apart from term_doublewrapped_in not necessarily terminating when the second parameter contains variables, it might also give rise to false answers due to the occurs check being disabled by default:

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

Therefore the groundness condition is actually required for the soundness of this procedure.

I just lifted this notion to lists:

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

and wrapped it into a variant of filter/3 that negates the predicate given:

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

I first tried using partiton/4 to do the same but then we would need to include library(lambda) or a similar implementation to make dynamically instantiate the invariant to the correct F and list element.

回复收藏 0 原文

~没有更多了~