时间戳

首页 > 解决方案 > 尝试在 Prolog 中实现拆分谓词

list - 尝试在 Prolog 中实现拆分谓词

问题描述

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

partition(L,P,S)

前缀和后缀的定义如下：

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

例如：

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

标签： listsplitprologpredicate

解决方案

如果您按照 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 如此富有表现力和强大的原因之一。习惯它并从中获利！

推荐阅读