Подсписки последовательных похожих элементов из списка в Прологе

Question

Я новичок в Прологе и пытаюсь ответить на этот вопрос. У нас есть список

List = [a,a,a,a,b,c,c,a,a,d,e,e,e,e]

Я хочу упаковать его в подсписки похожих элементов.

Pack( [a,a,a,a,b,c,c,a,a,d,e,e,e,e], Sublists)

должно дать

Sublists = [[a,a,a,a],[b],[c,c],[a,a],[d],[e,e,e,e]]

Это то, что я пробовал до сих пор:

pack([],[],[]).
pack([H],[H],[H]).
pack([H,H1|T],Z,X):- H==H1 , append([H],Z,Z1) , pack([H1|T],Z1,X).
pack([H,H1|T],Z,X):- H=\=H1 , append([H],Z,Z1) , 
                              append(Z1,X,Xs) , pack([H1|T],Z1,Xs).

Ниже приведена ошибка:

  Arithmetic: `a/0' is not a function

  In:
     [4] a=\=b
     [3] pack([a,b|...],[a,a],_1608) at  line 13
     [2] pack([a,a|...],[a],_1688) at  line 13
     [1] pack([a,a|...],[],_1762) at  line 13

Заранее спасибо. Я пытаюсь решить эти проблемы:

• P-99: Девяносто девять проблем Пролога .

Answer 1

Вы можете решить эту проблему с помощью простой обработки списка и использования SWI Prolog's dif/2 для общего решения:

pack([], []).       % packing empty is empty
pack([X], [[X]]).   % packing a single element
pack([X,X|T], [[X|PH]|PT]):- % rule for packing when next two terms are the same
    pack([X|T], [PH|PT]).
pack([X,Y|T], [[X]|PT]):-    % rule for different term
    dif(X, Y),
    pack([Y|T], PT).

2 ?- pack([a,a,a,a,b,c,c,a,a,d,e,e], L).
L = [[a, a, a, a], [b], [c, c], [a, a], [d], [e, e]] ;
false.

3 ?- pack(L, [[a,a,a], [b,b], [c]]).
L = [a, a, a, b, b, c] ;
false.

4 ?-

Answer 2

Обратите внимание, что решение lurker все еще имеет некоторые проблемы с производительностью. Смотрите ; false для каждого решения? Это указывает на то, что Пролог все еще сохраняет некоторую память (называемую точкой выбора - на самом деле таких точек выбора может быть даже несколько). Однако во многих случаях такая точка выбора не требуется. Вот решение, которое преодолевает эту проблему (имя group вместо pack довольно часто встречается в контексте Haskell)

group([], []).
group([E|Es], [[E|Gs]|Gss]) :-
   igroup(Es, E, Gs, Gss).

igroup([], _, [], []).
igroup([E|Es], F, Gs1, Gss1) :-
    (   E\=F
    ->  Gs1=[], Gss1=[[E|Gs2]|Gss2]
    ;   E==F
    ->  Gs1=[E|Gs2], Gss1=Gss2
    ;   E=F,
        Gs1=[E|Gs2], Gss1=Gss2
    ;   dif(E, F),
        Gs1=[], Gss1=[[E|Gs2]|Gss2]
    ),
    igroup(Es, E, Gs2, Gss2).

Обратите внимание, как тестирование на равенство E иF делится на четыре случая:

1. Сначала E \= F, что означает, что оба они определенно различаются.

2. Затем E == F, которыйозначает, что оба определенно идентичны.

3. Тогда E = F, который является общим случаем равенства, и

4. dif(E, F), который являетсяслучай общего неравенства

Для последних двух случаев нет ->, потому что оба могут быть истинными. Поскольку поддерживать такое количество дел довольно громоздко, для SICStus и SWI существует library(reif), что позволяет записать то же более компактно:

igroup([], _, [], []).
igroup([E|Es], F, Gs1, Gss1) :-
   if_(E = F
      , ( Gs1 = [E|Gs2], Gss1 = Gss2 )
      , ( Gs1 = [], Gss1 = [[E|Gs2]| Gss2] )),
   igroup(Es, E, Gs2, Gss2).

Answer 3

Вы получили ошибку, потому что =\=/2 истинно, если expr1 равно число , не равное expr2. Вместо этого вы можете использовать \=\2, который оценивает \+term1=term2. ==/2 оценивается как term1 equivalent to term2, =:=/ - истина, если expr1 - это число , которое равно до expr2. Еще одна ошибка, которую я обнаружил в вашем коде, заключается в том, что вы не очищаете промежуточный список. Вы должны сбросить значения в нем после добавления аналогичного списка элементов в список Sublists. Я использовал cut !, чтобы уменьшить возврат. Вместо этого, если вы пишете взаимоисключающие предикаты, лучше.

Я отредактировал ваш код:

pack1([],[],[]).
pack1([H],L,[Z]):- append([H],L,Z),!.
pack1([H,H1|T],Z,X):- H == H1 , append([H],Z,Z1) , pack1([H1|T],Z1,X),!.
pack1([H,H1|T],Z,[Z1|Zs]):- H\=H1 ,append([H],Z,Z1) ,pack1([H1|T],[],Zs),!.

Вывод:

?-pack1([a,a,a,a,b,c,c,a,a,d,e,e,e,e],[],Z).
  Z=[[a, a, a, a], [b], [c, c], [a, a], [d], [e, e, e, e]]
?-pack1([a,a,a,a,b,c,1,c,a,a,d,e,e,e,e],[],Z).
  Z= [[a, a, a, a], [b], [c], [1], [c], [a, a], [d], [e, e, e, e]]
?-pack1([],[],Z).
  Z= []

Надеюсь, это поможет.