Блог

Я пытаюсь разделить список на 2 в prolog. Но я все еще новичок в этом, и любая помощь была бы высоко оценена.

Моя проблема в том, что:

Реализуйте предложение choose(N,L, R,S), которое выбирает N элементов из L и помещает их в R, а остальные элементы из L оставляют в S

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

 split(0,_L1,_L2,_L4). 
split(X,[H|T],L1,T):-
     X>0,
     X1 is X-1,
     split(X1,T,[H|L1],T).
  

Когда я пытаюсь убежать

 split(2,[1,2,4,5],X,Y).
false
  

Вот какой результат я получаю. Что я делаю не так?

Если X > 0, то первый элемент L списка также должен быть первым элементом R списка. Например, это должно содержать: split(1, [a | Rest], [a], Rest) . Если мы хотим, чтобы эта взаимосвязь сохранялась, мы должны выразить ее в заголовке правила.

Поэтому ваше второе предложение должно выглядеть примерно так:

 split(X, [H|T], [H|L1], Rest) :-
     X > 0,
     X1 is X - 1,
     split(X1, T, L1, Rest).
  

Это правильно удаляет префикс, но остальное еще не правильно:

 ?- split(2, [1, 2, 4, 5], R, S).
R = [1, 2|S] ;
false.
  

Вам нужно еще раз подумать о случае, когда 0 элементов должны быть разделены. Каким должен быть результат split(0, [a, b, c], R, S) ?

Ваша самая большая проблема заключается в том, как вы конструируете / деконструируете 3-й аргумент.

И вы упускаете особый случай.

Большинство рекурсивных задач имеет пару специальных, обычно завершающих, случаев и один общий случай. У этой проблемы есть два особых случая.

Общий случай прост. Вы заметите здесь, что мы объединяем третий аргумент с [X|Pfx] . Это добавляет X к началу результата left / prefix и дает нам его (вероятно, несвязанный) конец. Этот хвост передается при рекурсии.

 partition( N , [X|Xs] , [X|Pfx] , Sfx ) :-
    N > 0 ,
    N1 is N-1 ,
    partition( N1, Xs, Pfx, Sfx )
    .
  

[Вы могли заметить, что по ходу работы мы создаем список в 3-м аргументе (список префиксов)… но это не легальный список: хвост предположительно несвязан. Мы позаботимся об этом в конце.

Итак … это касается общего случая. Но как мы узнаем, когда закончим?

Один особый / завершающий случай — это когда исходный список исчерпан. Если это произойдет до N уменьшения на 0 , мы закончили. Мы можем обработать это следующим образом:

 partition( _ , [], [], [] ).
  

На самом деле нас не волнует, какое значение N имеет, но может быть полезно включить ограничение, которое N >= 0 . Что здесь происходит, так это то, что когда исходный список (2-й аргумент) исчерпан и является пустым списком, мы (1) закрываем список префиксов (3-й аргумент) и объединяем список суффиксов с пустым списком.

Следующий особый случай — это когда N окончательно уменьшается до нуля. Это не сложнее:

 partition( 0 , Sfx, [], Sfx ).
  

Мы объединяем все, что осталось от исходного списка, с помощью списка суффиксов (4-й аргумент) и закрываем список префиксов пустым списком.

Оставшийся частный случай — это когда N окончательно уменьшается до 0 . Это так же просто. Вот:

 partition( 0 , Xs, [], Xs ).
  

Соедините все это вместе, и вы получите:

 partition( _ , []     , []      , []  ).
partition( 0 , Sfx    , []      , Sfx ).
partition( N , [X|Xs] , [X|Pfx] , Sfx ) :-
  N > 0 ,
  N1 is N-1,
  partition( N1, Xs , Pfx , Sfx ).