尝试在Prolog中实现拆分谓词

Question

我正在尝试在Prolog中实现一个partition谓词，它将列表分成两半，前缀和后缀，长度大致相同。

partition(L,P,S)

其中前缀和后缀定义如下：

prefix(P,L) :- append(P,_,L).
suffix(S,L) :- append(_,S,L).

• 如果L[]，则Prefix和S[]。
• 如果L是[H]，则P是[H]的，S是[]的。
• 如果L有两个或更多元素，则列表如何划分为其前缀和后缀：
  • L的长度为N，P的长度为div(N,2)。S的长度是N - div(N,2).

例如：

?- partition([a,b,c,d],X,Y).
X = [a,b]
Y = [c,d]
?- partition([a],X,Y).
X = [a]
Y = [ ]

这是我的代码和我得到的错误：

partition([],[],[]).
partition([H],[H],[]). 
partition(L, P, S) :-
length(L, N),
Plen is div(N,2),
Slen is N - div(N,2),
length(Pre, Plen),
length(Suff, Slen),
prefix(Pre, L),
suffix(Suff, L),
P is Pre,
S is Suff.
partition([a,b,c,d],X,Y).
>>> Type error: `[]' expected, found `[a,b]' (a list) 
("x" must hold one character)

Answer 1

我不明白这个错误消息，但这是错误的：

P is Pre,
S is Suff.

这是用于算术计算，其中右侧被评估为算术表达式并与左侧统一。

您只想统一变量：

P = Pre,
S = Suff.

或者，您可以对P和Pre/S和Suff使用相同的相同内容。

Answer 2

如果你按照David Tonhofer的回答的建议将is改为=，整个事情就会起作用。

但我想补充一点，你让事情有点复杂。您已正确确定append/3可用于计算列表前缀和后缀。但是对于任何要分区的列表和任何前缀，后缀都是唯一的，并且已经由append/3！反过来：如果你要求它计算后缀，它也会计算你寻找的前缀。但是，您丢弃了这些答案，并尝试重新计算匹配的前缀或后缀。没有必要这样做。

如果我们使您的前缀和后缀谓词更明确一些：

list_prefix_theonlypossiblematchingsuffix(List, Prefix, TheOnlyPossibleMatchingSuffix) :-
append(Prefix, TheOnlyPossibleMatchingSuffix, List).
list_suffix_theonlypossiblematchingprefix(List, Suffix, TheOnlyPossibleMatchingPrefix) :-
append(TheOnlyPossibleMatchingPrefix, Suffix, List).

我们可以看到，一旦我们为列表有了给定的前缀，后缀就没有更多的选择(反之亦然)：

?- list_prefix_theonlypossiblematchingsuffix([a, b, c, d], Prefix, MatchingSuffix).
Prefix = [],
MatchingSuffix = [a, b, c, d] ;
Prefix = [a],
MatchingSuffix = [b, c, d] ;
Prefix = [a, b],
MatchingSuffix = [c, d] ;
Prefix = [a, b, c],
MatchingSuffix = [d] ;
Prefix = [a, b, c, d],
MatchingSuffix = [] ;
false.

因此，无需尝试分别计算前缀和后缀并匹配它们的长度。限制前缀就足够了，因为后缀将紧随其后：

partition(List, Prefix, TheOnlyPossibleMatchingSuffix) :-
length(List, N),
PrefixLength is N div 2,
length(Prefix, PrefixLength),
list_prefix_theonlypossiblematchingsuffix(List, Prefix, TheOnlyPossibleMatchingSuffix).

这如您所愿：

?- partition([a, b, c, d], Prefix, Suffix).
Prefix = [a, b],
Suffix = [c, d].
?- partition([a, b, c, d, e], Prefix, Suffix).
Prefix = [a, b],
Suffix = [c, d, e].

一旦你有了这个，就更清楚的是，用真正的意思来代替涉及list_prefix_verylongpredicatename的目标：

partition(List, Prefix, Suffix) :-
length(List, N),
PrefixLength is N div 2,
length(Prefix, PrefixLength),
append(Prefix, Suffix, List).

来自其他编程语言，像append/3这样的谓词同时计算几个彼此之间有深厚关系的东西，即前缀和唯一匹配的后缀，这可能有点不寻常。但这是使Prolog如此富有表现力和强大的原因之一。习惯它并从中获利！

Answer 3

在我看来，你在这里做了很多不必要的工作。

这就是我认为你所需要的：

partition(L,P,S) :-
partition(L,L,P,S).
partition(L,[],[],L).
partition(([H|L],[_],[H],L).
partition([H|L],[_,_|L2],[H|P],S) :-
partition(L,L2,P,S).

如果我查询?- partition([a],X,Y), write([X,Y]).，那么我会得到：

[[a], []]
true.

如果我查询?- partition([a,b,c,d,e],X,Y), write([X,Y]).那么我会得到：

[[a, b, c], [d, e]]
true.

Answer 4

因为您已经将前缀和后缀定义为

prefix(P,L) :- append(P, _, L).         % prefix
suffix(S,L) :- append(_, S, L).         % suffix

只需将两者粉碎成一个电话，

partition(L,P,S) :- 
append(P, S, L),

就是这样，除了你对两个近半的比较长度有额外的条件，所以只需将它们添加到组合中：

length( P, N), length( A, N),      % same length, fresh list A
(A = [_|S] ; A = S).               % S one shorter than P, or same length

仅此而已。测试：

2 ?- partition( [1,2,3], A, B ).
A = [1, 2],
B = [3].
3 ?- partition( L, [1,2], [3] ).
L = [1, 2, 3].
15 ?- partition( L, A, B ).
L = A, A = B, B = [] ;
L = A, A = [_G2477],
B = [] ;
L = [_G2477, _G2483],
A = [_G2477],
B = [_G2483] ;
L = [_G2477, _G2483, _G2492],
A = [_G2477, _G2483],
B = [_G2492] ;
L = [_G2477, _G2483, _G2489, _G2492],
A = [_G2477, _G2483],
B = [_G2489, _G2492]
....