Более простой способ разделить список на N-м месте в Прологе?

Question

Вот предикат для разделения списка на:

• a "передний список" Front
• элемент в позиции N (на основе 0), Element
• «черный список» Back

... так, чтобы исходный список L можно было изменить с помощью:

append([Front,[Element],Back],L).

Код

% split_list(+List, +Index, Element, Front, Back)

split_list([L|Lr], N, El, [L|Front], Back) :- 
   N>0,!, 
   Nm is N-1, 
   split_list(Lr,Nm,El,Front,Back).

split_list([L|Lr], 0, L, [], Lr).

Это действительно трудно читать.

Тесты

:-begin_tests(split_list).

test(empty0,[fail])  :- split_list([],0,_,_,_).
test(empty1,[fail])  :- split_list([],1,_,_,_).
test(oorange,[fail]) :- split_list([a,b],2,_,_,_).
test(oorange,[fail]) :- split_list([a,b],-1,_,_,_).
test(trivial1)       :- split_list([a,b,c],0,a,[],[b,c]).
test(trivial2)       :- split_list([a,b,c],1,b,[a],[c]).
test(trivial3)       :- split_list([a,b,c],2,c,[a,b],[]).

tt(L,X) :- 
   split_list(L,X,Element,Front,Back),
   format("~w ==> ~w ~w ~w\n",[L,Front,Element,Back]),
   append([Front,[Element],Back],L).

test(long1) :- 
   L=[a,b,c,d,e,f,g,h,i,j,k,l],
   length(L,Llen),
   Nmax is Llen-1,
   foreach(between(0,Nmax,X),tt(L,X)).

:-end_tests(split_list).

Мы запускаем выше:

?- run_tests(split_list).
% PL-Unit: split_list .......
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [] a [b,c,d,e,f,g,h,i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a] b [c,d,e,f,g,h,i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b] c [d,e,f,g,h,i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c] d [e,f,g,h,i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d] e [f,g,h,i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d,e] f [g,h,i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d,e,f] g [h,i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d,e,f,g] h [i,j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d,e,f,g,h] i [j,k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d,e,f,g,h,i] j [k,l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d,e,f,g,h,i,j] k [l]
[a,b,c,d,e,f,g,h,i,j,k,l] ==> [a,b,c,d,e,f,g,h,i,j,k] l []
. done
% All 8 tests passed
true.

Хорошо, так что все работает.

Но:

1. Эффективно ли это?
2. Почему бы это не сделать, например, в library(lists)?
3. Может быть, это какой-то косвенный способ сделать это?

Приложение

Предикат едва читаем.

Как насчет тактического использования диктов?

split_list(L,N,Elem,Front,Back) :-
   split_list(_{list: L, index: N, element: Elem, front: Front, back: Back}).

split_list(
   _{list:    [L|Lr],
     index:   N,
     element: El,
     front:   [L|Front],
     back:    Back}) :- 
   N>0,!, 
   Nm is N-1, 
   split_list(
      _{list:    Lr,
        index:   Nm,
        element: El,
        front:   Front,
        back:    Back}).

split_list(
   _{list:    [L|Lr],
     index:   0,
     element: L,
     front:   [],
     back:    Lr}).

Более разборчиво? Точно сказать не могу. Но, скорее всего, будет медленнее.

Answer 1

Если вы собираетесь обновить элемент и повторно вставить его, вы можете использовать nth0 / 4:

?- L=[a,b,c,d,e],nth0(2,L,X,Temp),nth0(2,U,replaced(X),Temp).
L = [a, b, c, d, e],
X = c,
Temp = [a, b, d, e],
U = [a, b, replaced(c), d, e].

Answer 2

Не решение, а примечание по тестированию (которое не помещается в комментарии). Эта проблема является идеальным кандидатом для использования подхода QuickCheck к тестированию.

Например, используя lgtunit реализацию QuickCheck в Logtalk (текущая версия git), мы можем определить свойство, которое Решение должно соответствовать письму:

property(List, N) :-
    split_list(List, N, Element, Front, Back),
    list::append([Front,[Element],Back], List).

А затем:

| ?- {lgtunit(loader)}.
...
yes

| ?- forall(
         (between(1,10,N), M is N - 1),
         lgtunit::quick_check(
             property(+list(integer,N),+between(integer,0,M))
         )
     ).
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
% 100 random tests passed
yes

Выше мы случайным образом проверяли списки длиной от 1 до 10.

В общем, если требуемые типы уже определены (или могут быть быстро определены), а свойства, которым должна соответствовать реализация, легко определить, QuickCheck стоит рассмотреть как часть вашей настройки тестирования.

PS The lgtunit инструмент также поддерживает QuickCheck тестовые диалекты , что упрощает перенос тестов, подобных приведенному выше, в набор тестов.

Answer 3

Эффективен ли он?

Если известен N, то он работает в O (N) . Поскольку списки являются связанными списками, это наиболее эффективный способ получить элемент с указанным c индексом.

Если элемент имеет индекс N, то это означает, что Front имеет длину N, поэтому мы можем создать предикат:

split_list(List, Index, Element, Front, Back) :-
    <b>length(Front, Index),</b>
    append(Front, [Element|Back], List).

Если известен N, то он будет выполняться в O (n) .