list - 在 Prolog 的第 N 个位置拆分列表的更简单方法？

Question

这是一个将列表拆分为的谓词:

• 一个“前台列表”Front
• 位置 N 处的元素(从 0 开始)，Element
• “返回列表”返回

...这样原始列表 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. 也许是，可能是某种间接的方式？

附录

谓词几乎难以辨认。

dicts 的战术使用怎么样？

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

Is it efficient?

如果 N 已知，则它在 O(N) 中运行。由于列表是链表，这是获取特定索引处元素的最有效方法。

如果元素在索引 N 处，则意味着 Front 的长度为 N，因此我们可以创建一个谓词:

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

如果 N 已知，那么这将在 O(n) 内运行。