Блог

Мне нужно реализовать эту функцию:

 cod_first(X, L, Lrem, Lfront). 
  

Lfront содержит все копии, X которые находятся в начале L , включая X ; Lrem является списком остальных элементов.

Я пытался реализовать это с помощью append, но я совсем новичок в Prolog и немного заблудился.

Ожидаемый результат для программы примерно такой:

 ?- cod_first(1, [1, 1, 2, 3], Lrem, Lfront) 
Lrem = [2, 3],
Lfront = [1, 1, 1];
false.

?- cod_first(1, [2, 3, 4], Lrem, Lfront)
Lrem = [2, 3, 4],
Lfront = [1];
false.
  

Обновление: Я нашел эту функцию, которая объединяет одни и те же элементы в список:

 pack([], []).
pack([X], [[X]]).
pack([X, X| L], [[X| Xs]| R]) :-
    pack([X| L], [Xs| R]).
pack([X, Y| L], [[X]| R]) :-
    X = Y,
    pack([Y| L], R).
  

Я думаю, что эта функция может быть адаптирована к той, которую я ищу, любая помощь?

Сначала давайте проверим найденный вами код! Я протестирую это, рассмотрев все списки, начиная с самого короткого:

 ?- N=N, length(Xs,N), pack(Xs, Xss).
   N = 0, Xs = [], Xss = []
;  N = 1, Xs = [_A], Xss = [[_A]]
;  N = 2, Xs = [_A,_A], Xss = [[_A,_A]]
;  N = 3, Xs = [_A,_A,_A], Xss = [[_A,_A,_A]]
;  N = 4, Xs = [_A,_A,_A,_A], Xss = [[_A,_A,_A,_A]]
;  ... .
  

Итак, согласно этому запросу, ваш код работает только для списков, где все элементы одинаковы. На самом деле за это отвечает цель X = Y . Лучше выразить неравенство с помощью dif(X, Y) . С этим небольшим изменением мы получаем:

  ?- N=N, length(Xs,N), pack(Xs, Xss).
    N = 0, Xs = [], Xss = []
 ;  N = 1, Xs = [_A], Xss = [[_A]]
 ;  N = 2, Xs = [_A,_A], Xss = [[_A,_A]]
 ;  N = 2, Xs = [_A,_B], Xss = [[_A],[_B]], dif(_A,_B)
 ;  N = 3, Xs = [_A,_A,_A], Xss = [[_A,_A,_A]]
 ;  N = 3, Xs = [_A,_A,_B], Xss = [[_A,_A],[_B]], dif(_A,_B)
 ;  N = 3, Xs = [_A,_B,_B], Xss = [[_A],[_B,_B]],  dif(_A,_B)
 ;  N = 3, Xs = [_A,_B,_C], Xss = [[_A],[_B],[_C]], dif(_A,_B), dif(_B,_C)
 ;  N = 4, Xs = [_A,_A,_A,_A], Xss = [[_A,_A,_A,_A]]
 ;  ... .
  

Теперь мы получаем действительно все решения. Давайте рассмотрим два ответа на N = 2 . В первом говорится, что, поскольку все элементы Xs равны, Xss содержит только один элемент. Во втором говорится, что, когда Xs элементы отличаются, они отображаются в отдельных элементах Xss . Обратите внимание на dif(_A,_B) , который гарантирует, что выбираются только отличающиеся термины.

Однако вас интересует только одно такое разделение:

 cod_first(X, [], [], [X]).
cod_first(X, [X|Es], Lrem, [X|Xs]) :-
   cod_first(X, Es, Lrem, Xs).
cod_first(X, [E|Es], [E|Es], [X]) :-
   dif(X,E).

?- N=N, length(Xs, N), cod_first(X, Xs, Lrem, Lfront).
   N = 0, Xs = [], Lrem = [], Lfront = [X]
;  N = 1, Xs = [X], Lrem = [], Lfront = [X,X]
;  N = 1, Xs = [_A], Lrem = [_A], Lfront = [X], dif(_A,X)
;  N = 2, Xs = [X,X], Lrem = [], Lfront = [X,X,X]
;  N = 2, Xs = [X,_A], Lrem = [_A], Lfront = [X,X], dif(_A,X)
;  N = 2, Xs = [_A,_B], Lrem = [_A,_B], Lfront = [X], dif(_A,X)
;  N = 3, Xs = [X,X,X], Lrem = [], Lfront = [X,X,X,X]
;  N = 3, Xs = [X,X,_A], Lrem = [_A], Lfront = [X,X,X], dif(_A,X)
;  N = 3, Xs = [X,_A,_B], Lrem = [_A,_B], Lfront = [X,X], dif(_A,X)
;  N = 3, Xs = [_A,_B,_C], Lrem = [_A,_B,_C], Lfront = [X], dif(_A,X)
;  N = 4, Xs = [X,X,X,X], Lrem = [], Lfront = [X,X,X,X,X]
;  ... .
  

Вот другая версия, которую я предпочитаю использовать library(reif) доступна
для
SICStusи
SWI.

 cod_first2(X, Es, Lrem, [X|Xs]) :-
   cod_first2i(Es, X, Xs, Lrem).

cod_first2i([], _, [], []).
cod_first2i([E|Es], X, Xs0, Ys) :-
   if_( E = X
      , ( Xs0 = [X|Xs], cod_first2i(Es, X, Xs, Ys) )
      , ( Xs0 = [], Ys = [E|Es] )
      ).
  

Это намного эффективнее, но дает точно такие же ответы.