`var(A)` 和执行顺序
`var(A)` and order of execution
本页练习 09 http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ 要求创建一个将重复元素打包到子列表中的谓词。
一个简单的解决方案很简单
pack([], []).
pack([H|T], [I|U]) :-
split(H, T, I, P),
pack(P, U).
其中拆分 split(Head, Tail, HeadGroup, Rest)
定义为
split(A, [], [A], []).
split(A, [B|T], [A], [B|T]) :- A \= B.
split(A, [A|T], [A|U], B) :- split(A, T, U, B).
效果很好,与上述网页上提供的示例解决方案非常一致。
此解决方案失败的地方是像 pack(X, [[a], [b, b]]).
这样的查询。两个解集之间的对应关系是双射的(对于pack(A, B)
中的每个A
,只有一个B
),所以一定有更好的解。
解决它的一种方法是更改求值顺序,帮助 prolog 根据参数类型选择非无限分支,如下所示
pack([], []).
pack(A, B) :-
( var(A) ->
A = [H|T],
B = [I|U],
pack(P, U),
split(H, T, I, P)
; A = [H|T],
B = [I|U],
split(H, T, I, P),
pack(P, U)
).
这方面的两个问题。
首先,这丑得令人难以置信,那么是否有更好的方法来根据参数类型选择规则顺序?
其次,可能是更复杂的问题,有没有办法在没有 var(A)
的情况下重写解决方案,如果没有,为什么?
从声明的角度来看,var/1
和 (\=)/2
等非单调结构非常有问题。
为什么?看看:
?- var(A), A=a.
A = a.
?- A=a, var(A).
false.
因此,这打破了合取的交换性,这是我们在实际推理逻辑程序时所依赖的核心属性之一。
关于 (\=)/2
,您 认为 会表示两个术语不同?看看:
?- X \= Y.
false.
不存在两个不同的术语,是吗? 我觉得有点奇怪,至少可以这么说,所以显然谓词确实有别的意思。
幸运的是,对于您的情况,解决方案非常简单。只需使用纯约束 dif/2
来表示两项 不同 。有关详细信息,请参阅 prolog-dif。您只需更改一行代码即可使您的解决方案更加通用。而不是:
split(A, [B|T], [A], [B|T]) :- A \= B.
只需使用dif/2
:
split(A, [B|T], [A], [B|T]) :- dif(A, B).
通过此更改,您的示例完全按预期运行:
?- pack(X, [[a], [b, b]]).
X = [a, b, b] ;
false.
请注意,现有的 Prolog 文献已经 过时 ,并且大多数此类解决方案都来自 dif/2
在大多数 Prolog 系统中甚至不可用的时代,当然不是免费的。
本页练习 09 http://www.ic.unicamp.br/~meidanis/courses/mc336/2009s2/prolog/problemas/ 要求创建一个将重复元素打包到子列表中的谓词。
一个简单的解决方案很简单
pack([], []).
pack([H|T], [I|U]) :-
split(H, T, I, P),
pack(P, U).
其中拆分 split(Head, Tail, HeadGroup, Rest)
定义为
split(A, [], [A], []).
split(A, [B|T], [A], [B|T]) :- A \= B.
split(A, [A|T], [A|U], B) :- split(A, T, U, B).
效果很好,与上述网页上提供的示例解决方案非常一致。
此解决方案失败的地方是像 pack(X, [[a], [b, b]]).
这样的查询。两个解集之间的对应关系是双射的(对于pack(A, B)
中的每个A
,只有一个B
),所以一定有更好的解。
解决它的一种方法是更改求值顺序,帮助 prolog 根据参数类型选择非无限分支,如下所示
pack([], []).
pack(A, B) :-
( var(A) ->
A = [H|T],
B = [I|U],
pack(P, U),
split(H, T, I, P)
; A = [H|T],
B = [I|U],
split(H, T, I, P),
pack(P, U)
).
这方面的两个问题。
首先,这丑得令人难以置信,那么是否有更好的方法来根据参数类型选择规则顺序?
其次,可能是更复杂的问题,有没有办法在没有 var(A)
的情况下重写解决方案,如果没有,为什么?
从声明的角度来看,var/1
和 (\=)/2
等非单调结构非常有问题。
为什么?看看:
?- var(A), A=a.
A = a.
?- A=a, var(A).
false.
因此,这打破了合取的交换性,这是我们在实际推理逻辑程序时所依赖的核心属性之一。
关于 (\=)/2
,您 认为 会表示两个术语不同?看看:
?- X \= Y. false.
不存在两个不同的术语,是吗? 我觉得有点奇怪,至少可以这么说,所以显然谓词确实有别的意思。
幸运的是,对于您的情况,解决方案非常简单。只需使用纯约束 dif/2
来表示两项 不同 。有关详细信息,请参阅 prolog-dif。您只需更改一行代码即可使您的解决方案更加通用。而不是:
split(A, [B|T], [A], [B|T]) :- A \= B.
只需使用dif/2
:
split(A, [B|T], [A], [B|T]) :- dif(A, B).
通过此更改,您的示例完全按预期运行:
?- pack(X, [[a], [b, b]]).
X = [a, b, b] ;
false.
请注意,现有的 Prolog 文献已经 过时 ,并且大多数此类解决方案都来自 dif/2
在大多数 Prolog 系统中甚至不可用的时代,当然不是免费的。