CODEWITHSUNDEEP
listprolog
rwehresmann
rwehresmann

Reputation: 1168

Split a list dynamically in Prolog

I started with prolog a few weeks, and yet I'm seeing more deeper the construction of recursive predicates who manipulate lists. My question is: it's possible build a predicat that split a gived list in a given number of other lists?

For example, what I imagine:

split([H|T], NumberLists, Lists) -- recursive implementation --

?- split([1,2,3,4,5,6,7,8],2,Lists).
Lists = [[1,2,3,4],[5,6,7,8]].

?- split([1,2,3,4,5,6,7,8],4,Lists).
Lists = [[1,2],[3,4],[5,6],[7,8]].

Someone can give me an example of implementation?

Thanks!

Upvotes: 2

Views: 207

Answers (3)

Nicholas Carey
Nicholas Carey

Reputation: 74197

Something like this ought to do. No built-in predicates:

partition( [] , _ , []       ) .  % the empty list is already partitioned
partition( Xs , N , [Pfx|Ys] ) :- % for a non-empty list, we...
  take(N,Xs, Pfx , Sfx ) ,        % - split it into a prefix of (at most) length N and its suffix.
  partition(Sfx,N,Ys)             % - recursively partition the suffix
  .                               % Easy!

take( 0 , Xs  , []     , Xs  ) .     % if we reach zero, we're done. Close the prefix and hand back whatever is left over.
take( N , []  , []     , []  ) :-    % if we exhaust the source list, we're done. close the prefix and hand back the empty list as the suffix.
  N > 0                              % - assuming, of course, that N is greater than zero.
  .                                  %
take( N , [X|Xs] , [X|Ys] , Sfx ) :- % otherwise prepend the current item to the prefix
  N > 0 ,                            % - assuming N is greater than zero,
  N1 is N-1 ,                        % - then decrement N
  take(N1,Xs,Ys,Sfx)                 % - and recurse down.
  .                                  % Also easy!

Upvotes: 1

repeat
repeat

Reputation: 18726

How about using and ?

:- use_module(library(clpfd)).
:- use_module(library(lambda)).

We define split/3 like this:

split(Xs,N,Yss) :-
   length(Xs,L),
   N #=< L,
   [L0,L1] ins 1..sup,
   L0 #= L / N,
   L1 #= L - L0*(N-1),

   % enumerate `N` *now* if domain is finite.
   % ideally, length/2 does something like this (by itself).
   ( fd_size(N,Size),integer(Size) -> indomain(N) ; true ),

   length(Yss,N),
   append(Yss0,[Ys],Yss),            % creates useless choicepoint
   maplist(\Ls^length(Ls,L0),Yss0),
   length(Ys,L1),
   append(Yss,Xs).                   % note we use append/2 here, not append/3

First, the queries the OP gave:

?- split([1,2,3,4,5,6,7,8],2,Lists).
  Lists = [[1,2,3,4], [5,6,7,8]]
; false.

?- split([1,2,3,4,5,6,7,8],4,Lists).
  Lists = [[1,2], [3,4], [5,6], [7,8]]
; false.

Then, a more general example:

?- split([1,2,3,4,5,6,7,8],N,Lss).
  N = 1, Lss = [[1,2,3,4,5,6,7,8]] 
; N = 2, Lss = [[1,2,3,4], [5,6,7,8]] 
; N = 3, Lss = [[1,2], [3,4], [5,6,7,8]] 
; N = 4, Lss = [[1,2], [3,4], [5,6], [7,8]] 
; N = 5, Lss = [[1], [2], [3], [4], [5,6,7,8]] 
; N = 6, Lss = [[1], [2], [3], [4], [5], [6,7,8]] 
; N = 7, Lss = [[1], [2], [3], [4], [5], [6], [7,8]] 
; N = 8, Lss = [[1], [2], [3], [4], [5], [6], [7], [8]] 
; false.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60004

the examples you show (all lists of same length) can be covered with

split(L, N, S) :-
    length_list(N, S),
    append(S, L),
    maplist(length_list(_), S).

length_list(Length, List) :- length(List, Length).

Upvotes: 2

Related Questions