Separating a list into a list of fixed length sublists

Question

Given a list L, for instance, [1,2,3,4,5,6,7] and a number N, for instance 3, I would like to make a predicate that would separate the elements of L into lists of size N.

So, the result will be: [[1,2,3], [4,5,6], [7]] in our case.

What I have tried:

% List containing the first N elements of given list.
    takeN([X|Xs], 0, []) :- !.
    takeN([X|Xs], N, [X|Ys]) :- N1 is N-1, takeN(Xs, N1, Ys).

% Given list without the first N elements.      
    dropN(R, 0, R) :- !.
    dropN([X|Xs], N, R) :- N1 is N-1, dropN(Xs, N1, R).

% size of list.
    sizeL([], 0) :- !.
    sizeL([X|Xs], N) :- sizeL(Xs, N1), N is N1+1.

blockify(R, N, [R|[]]) :- sizeL(R, N1), N1 < N, !.
blockify([X|Xs], N, [Y|Ys]) :- sizeL(R, N1), N1 >= N, takeN([X|Xs], N, Y),
     dropN([X|Xs], N, Res), blockify(Res, N, Ys).

It doesn't work (blockify([1,2,3], 2, R) for example returns false, instead of [[1,2], [3]]).

I can't find where I'm mistaken, though. What's wrong with this?

See [this answer](http://stackoverflow.com/a/27161196/772868) for take. — false, Mar 02 '17 at 16:52
You know that Prolog has `length/2` for the "size of a list"? — lurker, Mar 03 '17 at 01:42

Willem Van Onsem · Accepted Answer · 2017-03-02T14:09:52.060

I think you are making thinks a bit overcomplicated. First of all let's exclude the case where we want to blockify/3 the empty list:

blockify([],_,[]).

Now in the case there are elements in the original list, we simply make use of two accumulators: - some kind of difference list that stores the running sequence; and - an accumulator that counts down and look whether we reached zero, in which case we append the running difference list and construct a new one.

So this would be something like:

blockify([H|T],N,R) :-
    N1 is N-1,
    blockify(T,N1,N1,[H|D],D,R).

Now the blockify/5 has some important cases:

we reach the end of the list: in that case we close the difference list and append it to the running R:
```
blockify([],_,_,D,[],[D]).
```
we reach the bottom of the current counter, we add the difference list to R and we intialize a new difference list with an updated counter:
```
blockify([H|T],N,0,D,[],[D|TR]) :-
    blockify(T,N,N,[H|D2],D2,TR).
```
none of these cases, we simply append the element to the running difference decrement the accumulator and continue:
```
blockify([H|T],N,M,D,[H|D2],TR) :-
    M > 0,
    M1 is M-1,
    blockify(T,N,M1,D,D2,TR).
```

Or putting it all together:

blockify([],_,[]).
blockify([H|T],N,R) :-
    N1 is N-1,
    blockify(T,N1,N1,[H|D],D,R).

blockify([],_,_,D,[],[D]).
blockify([H|T],N,0,D,[],[D|TR]) :-
    blockify(T,N,N,[H|D2],D2,TR).
blockify([H|T],N,M,D,[H|D2],TR) :-
    M > 0,
    M1 is M-1,
    blockify(T,N,M1,D,D2,TR).

Since in each recursive call all clauses run in O(1) and we do the recursion O(n) deep with n the number of elements in the original list, this program runs in O(n).

Nice solution! Thank you! – SomeoneWithAQuestion Mar 02 '17 at 13:52 — SomeoneWithAQuestion, Mar 02 '17 at 13:52

score 1 · Answer 2 · answered Mar 03 '17 at 15:13

1

if your Prolog provides length/2, a compact solution could be:

blockify(R, N, [B|Bs]) :-
    length(B, N),
    append(B, T, R),
    !, blockify(T, N, Bs).
blockify(R, _N, [R]).

answered Mar 03 '17 at 15:13

CapelliC

59,646
5
47
90

score 0 · Answer 3 · answered Mar 02 '17 at 13:51

0

Let me teach you how to debug a Prolog query:

1) blockify([1,2,3], 2, R)
2) does it match blockify(R, N, [R|[]]) ? oh yes,
   it can be bound to blockify([1, 2, 3], 2, [[1, 2, 3]])
3) let's evaluate the body: sizeL(R, N1), N1 < N, !.
   Replace R and N, we get: sizeL([1, 2, 3], N1), N1 < 2, !.
4) evaluate sizeL([1, 2, 3], N1): for brevity, since it's a common
   list count predicate, the result should be obvious: N1 = 3
5) evaluate N1 < N: 3 < 2 => false
6) since the rest are all , (and operator) a single false
   is enough to make the whole body to evaluate to false
7) there you go, the predicate is false

See where your mistake is?

answered Mar 02 '17 at 13:51

LeleDumbo

9,192
4
24
38

Wait, I thought that in prolog if `blockify(R, N, [R|[]])` is false, it will just try the next declaration (`blockify([X|Xs], N, [Y|Ys])`), which works. Or is it not? – SomeoneWithAQuestion Mar 02 '17 at 13:54
use `trace/0` then execute your query to get the predicate per predicate stacktrace. hint: yes, it tries the next predicate, but still ends in false because the singleton variables there are useless. actually, occurrence of singleton variables is an indicator that your rules are wrong. note that R in your second `blockify/3` has nothing to do with R from the first. – LeleDumbo Mar 03 '17 at 03:19

Separating a list into a list of fixed length sublists

3 Answers3