To split a list: splitlist(ListToBeSplitted, Splititem, BeforeSplit, AfterSplit)

```
splitlist([],_,[],[]).
splitlist([H|R], H, [], R).
splitlist([H|R], X, [H|S2],E) :-
splitlist(R, X, S2, E).
```

To split a list: splitlist(ListToBeSplitted, Splititem, BeforeSplit, AfterSplit)

```
splitlist([],_,[],[]).
splitlist([H|R], H, [], R).
splitlist([H|R], X, [H|S2],E) :-
splitlist(R, X, S2, E).
```

Or you can just use the built-in append/3:

```
append(BeforeSplit, [SplitItem|AfterSplit], ListToBeSplit)
```

what about splitting a list into N pieces, or pieces of size L

Hereâ€™s something similar, as an example:

```
split_list_at_nth1(LongLst, Nth1Index, UptoLst, AfterLst) :-
must_be(nonneg, Nth1Index),
split_list_at_nth1_(LongLst, Nth1Index, UptoLst, AfterLst).
% Close the Upto loop
split_list_at_nth1_(L, 0, [], L) :- !.
split_list_at_nth1_([H|T], N, [H|UptoTail], AfterLst) :-
succ(N0, N),
split_list_at_nth1_(T, N0, UptoTail, AfterLst).
```

```
?- split_list_at_nth1([a, b, c, d], 2, U, A).
U = [a,b],
A = [c,d].
```

What about this (putting the index in front is what I would do).

```
split_list_at_nth1(Nth, Long, Start, End) :-
length(Start, Nth),
append(Start, End, Long).
```

1 Like

I have been wondering why this seems to be the convention. Given that a helper predicate (as in my example above) for list processing usually needs *the* list as the first argument, to take advantage of the `[]`

vs `[H|T]`

indexing, isnâ€™t it a better convention to reduce such argument reordering?

It is easier to use ~~partial evaluation~~ *meta predicates. So you can write for example with nth1/3:

```
?- maplist(nth1(2), [[a, b, c], [e, f, g]], R).
R = [b, f].
```

(â€śPartial evaluationâ€ť is something else apparently)

1 Like

I think *partial evaluation* should be *high order predicates*, no? Or maybe *meta predicates*?

And yes, this is typically a reason to put keys/selectors, etc. at the front, leading to the order

`x(action params, object to act upon, result).`

2 Likes

You are correct. I thought that you can use meta predicates and the call mechanism for partial evaluation in Prolog but now that I read the Wikipedia page it turns out I was mixed up. How about partial *application*? Can we say â€śin Prolog, you can use call and meta-predicates to implement partial applicationâ€ť?

You can use append/2 for splitting into N pieces, trivially.

```
?- N = 2, length(R, N), append(R, [a,b]).
N = 2,
R = [[], [a, b]] ;
N = 2,
R = [[a], [b]] ;
N = 2,
R = [[a, b], []] ;
false.
```

For â€śpieces of size Lâ€ť you might have to do the recursive step yourself.

Working code:

```
split_list_into_lens(Len, Lst, Lsts) :-
must_be(positive_integer, Len),
split_list_into_lens_(Lst, Len, Lsts).
split_list_into_lens_([], _, []).
split_list_into_lens_([H|T], Len, [LstSplit|Lsts]) :-
( length(LstSplit, Len),
append(LstSplit, LstRemainder, [H|T]) -> true
; LstSplit = [H|T],
length(LstSplit, LenSplitFinal),
LenSplitFinal < Len,
LstRemainder = [] ),
split_list_into_lens_(LstRemainder, Len, Lsts).
```

```
?- split_list_into_lens(3, [a, b, c, d, e, f, g, h, i], Lsts).
Lsts = [[a,b,c],[d,e,f],[g,h,i]].
% Presumably desirable:
?- split_list_into_lens(3, [a, b, c, d, e, f, g, h, i, j, k], Lsts).
Lsts = [[a,b,c],[d,e,f],[g,h,i],[j,k]].
```

1 Like

I come up with this :

```
split([],_,_).
split(Lst,N,[FirstN|Res]) :-
length(FirstN,N), append(FirstN,Rest,Lst), split(Rest,N,Res).
```

it almost worksâ€¦

```
%%odd length i.e. the last split is smaller
?- L= [1,2,3,4,5],split(L,2,R).
false.
%% it should stop at 5,6
?- L= [1,2,3,4,5,6],split(L,2,R).
L = [1, 2, 3, 4, 5, 6],
R = [[1, 2], [3, 4], [5, 6]|_10990] ;
false.
```

What iâ€™m missing

this works

```
split([],_,[]) :- !.
split(Lst,N,[Lst|Res]) :- length(Lst,X), X < N, split([],N,Res).
split(Lst,N,[FirstN|Res]) :-
length(FirstN,N), append(FirstN,Rest,Lst), split(Rest,N,Res).
```

Note that your method is very inefficient, by checking the final situation (`X < N`

) each time:

```
?- time((numlist(1, 100000, L), split(L, 3, S))).
% 466,673 inferences, 8.181 CPU in 8.126 seconds (101% CPU, 57046 Lips)
```

```
?- time((numlist(1, 100000, L), split_list_into_lens(3, L, S))).
% 366,685 inferences, 0.067 CPU in 0.066 seconds (101% CPU, 5511456 Lips)
```

Performance can be regained with a slight rewrite:

```
split2([],_,[]) :- !.
split2(Lst, N, [FirstN|Res]) :-
length(FirstN, N),
append(FirstN, Rest, Lst), !,
split2(Rest, N, Res).
split2(Lst, N, Lst) :-
length(Lst, Len),
Len < N.
```

```
?- time((numlist(1, 100000, L), split2(L, 3, S))).
% 366,679 inferences, 0.074 CPU in 0.074 seconds (100% CPU, 4968454 Lips)
```

1 Like

niceâ€¦ thanks

havent used time-ing in prolog

I see the third runs only once at the end â€¦clever

Q: why from the ones below the 1st is ok but the second is not.

```
split(Lst, N, [FirstN|Res]) :-
......
split(Rest, N, Res).
split(Lst, N, Res) :-
......
split(Rest, N, [Res|FirstN]).
```

the head is a â€śmatchâ€ť â€¦ at the tail is a â€ścallâ€ťâ€¦ this is where concatenation should happen, right ?

That would be a concatenation in reverse order, though. A difference list can be used to â€śappendâ€ť in the intended order.

Here is the same split implemented as a DCG, with basically the same performance as split_list_into_lens/3 (the cut increases performance):

```
% For string//1 at https://www.swi-prolog.org/pldoc/man?section=basics
:- use_module(library(dcg/basics)).
split_list(Len, Lst, LstSplit) :-
must_be(positive_integer, Len),
phrase(split(LstSplit, Len), Lst).
split([H|T], Len) --> split1(H, Len), !, split(T, Len).
% Terminate at end of list
split([], _) --> [].
% Grab list of intended length
split1(L, Len) --> { length(L, Len) }, string(L).
% ... or what remains at the end
split1(L, _Len) --> [L].
```

```
?- split_list(3, [a, b, c, d, e, f, g, h, i, j, k], Lsts).
Lsts = [[a,b,c],[d,e,f],[g,h,i],j,k].
```

1 Like

You could take advantage of the *Rest* argument of phrase/3; and there is also sequence//2 from library(dcg/high_order). It would be enough to define:

```
length_list(N, L) -->
{ length(L, N) },
L. % yes don't need string//1
```

Then:

```
?- use_module(library(dcg/high_order)).
true.
?- phrase(sequence(length_list(2), Sublists), [a,b,c,d], Rest), !.
Sublists = [[a, b], [c, d]],
Rest = [].
?- phrase(sequence(length_list(2), Sublists), [a,b,c,d,e], Rest), !.
Sublists = [[a, b], [c, d]],
Rest = [e].
```

But of course it all depends on the use case.

EDIT: since there are some â€ślikesâ€ť on this, I would like to point out two issues.

- As it stands, using
`L`

instead of`string(L)`

is indeed a bit slower. - Since sequence//2 leaves choice points, it will eventually run out of memory if the list we are parsing is long enough. Cutting on every matched prefix will avoid this.

3 Likes

I understand it is a reverse.

my question was what is the interpretation/thinking of putting it in the head.

In algorithming languages you always do it at the end, because they cant do â€śactionâ€ť in the head.

I have hard time of understanding the logic/mechanism of how it works.

If I use `L`

instead of `string(L)`

, then this increases from 4 to 11 seconds:

```
?- numlist(1, 10000000, L), time(split_list(3, L, S)).
```

Slightly more elegant than previous:

```
:- use_module(library(dcg/basics)).
split_list(Len, Lst, LstSplit) :-
must_be(positive_integer, Len),
phrase(split(LstSplit, Len), Lst).
split([H|T], Len) --> list_length(H, Len), !, split(T, Len).
% Terminate at end of list
split([H], _) --> [H], !.
split([], _) --> [].
list_length(L, Len) --> { length(L, Len) }, string(L).
```

1 Like

There is something complicated, the DCG rewrite rules invoke phrase/3

```
?- listing(split_list:length_list).
length_list(N, L, A, B) :-
length(L, N),
C=A,
phrase(L, C, B).
```

instead of the simpler pattern I would like to see.

```
length_list(3, [A,B,C]) --> [A,B,C].
```

that is

```
?- listing(split_list:length_list).
length_list(3, [A, B, C], [A, B, C|D], D).
```

Precomputing the non terminal list_chunk//1 we can get back the efficiency of basic pattern matching:

```
:- dynamic list_chunk/3.
split_list(ListToBeSplitted, N, Sublists, Rest) :-
retractall(list_chunk(_, _, _)),
length(T, N),
bind_last(T, A, D),
assertz(list_chunk(T, A, D)),
phrase(sequence(list_chunk, Sublists), ListToBeSplitted, Rest), !.
bind_last([Last], [Last|D], D).
bind_last([H|Tail], [H|Rest], D) :- bind_last(Tail, Rest, D).
```

I tried to use @janâ€™s split_list_at_nth1/4 solution above to split strings as follows:

```
split_string_at_nth1(Nth,S,Start,End):-
string_codes(S,L),
split_list_at_nth1(Nth,L,SL,EL),
string_codes(Start,SL),
string_codes(End,EL).
```

This worked in the forward direction but not in the backward. What is the right way to get it to work in both directions?

Thanks in advance.