Попытка реализовать предикат разделения в прологе

Question

Я пытаюсь реализовать предикат 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

Так как вы уже определили свои префиксы и суффиксы как

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

просто sma sh два вместе в один вызов,

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

, и это будет it , за исключением того, что у вас есть дополнительные условия относительно сравнительной длины двух близких половинок, поэтому просто добавьте их в смесь:

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

Answer 2

Если вы измените 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, вычисляет сразу несколько вещей, которые имеют глубокие отношения друг с другом, то есть префикс и уникальный суффикс соответствия. Но это одна из вещей, которая делает Пролог таким выразительным и мощным. Привыкайте к этому и извлекайте из этого прибыль!

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])., тогда я get:

[[a], []]
true.

Если я запрашиваю ?- partition([a,b,c,d,e],X,Y), write([X,Y])., тогда я получаю:

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

Answer 4

Я не понимаю это сообщение об ошибке, но это неправильно:

    P is Pre,
    S is Suff.

Это для арифметической c оценки, при которой правая сторона оценивается как арифметическое c выражение и объединено с левой стороной.

Вы просто хотите объединить переменные:

    P = Pre,
    S = Suff.

В качестве альтернативы, вы можете использовать то же самое для P и Pre / S и Suff повсюду.