An easier way to split a list at the N-th place in Prolog?

user_884463 0
Viewed 275

Here is a predicate to split a list into:

  • a "front list" Front
  • the element at position N (0-based), Element
  • the "back list" Back

...so that that the original list L can be recomposed with:

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

Code

% 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).

This is really hard to read.

Tests

:-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).

We run the above:

?- 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.

Ok, so it works.

But:

  1. Is it efficient?
  2. Why isn't this in library(lists) for example?
  3. Maybe it is, possibly some indirect way of doing this?

Addendum

The predicate is barely legible.

How about the tactical use of 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}).

More legible? Not sure. But it is highly likely to be slower.

prolog list
3 Answers

Is it efficient?

If N is known, then it runs in O(N). Since lists are linked lists, that is the most efficient way to get an element at a specific index.

If the element is at index N, then it means that the Front has length N, so we can create a predicate:

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

If N is known, then this will run in O(n).

user_675790

If you're going to update an element and reinsert, you could use 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].
user_8740240

Not a solution but a note on testing (that doesn't fit in a comment). This problem is perfect candidate for using a QuickCheck approach to testing.

For example, using Logtalk's lgtunit QuickCheck implementation (current git version), we can define the property that the solution must comply with by writing:

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

And then:

| ?- {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

Above, we random tested lists with length from 1 to 10.

In general, when the required types are already defined (or can be quickly defined) and the properties that an implementation must comply with are easy to define, QuickCheck is worth considering as part of your testing setup.

P.S. The lgtunit tool also support QuickCheck test dialects, making it trivial to move tests such as the one above to a test suite.

user_6346290
Related