Iterating over list elements in turns in prolog

Question

I have this predicate repeat/3 which I need to construct. It is supposed to repeat all the elements in a list n amount of times. For example:

?- repeat([a,b,a,a,c],2,X).

Would produce X = [a, a, b, b, a, a, a, a, c, c].

The current code I have written for it is the following:

repeat([],_,[]).
repeat(_,0,[]).
repeat([A],Int,[A|X]):- Int1 is Int-1, repeat([A],Int1,X).
repeat(A,1,A).
repeat([A|Tail],Int,[A|X]):- Int1 is Int-1, repeat([A|Tail],Int1,X).

It will return:
1) An empty list upon giving it an empty list.
2) An empty list upon giving it the number 0 as an argument.
3) One letter n amount of times.
4) The given list one time.
Now, the issue I'm having with is the final line of code.
5) What this line will do for me currently is return all the elements in a list after repeating the first element n amount of times.
Example:

?- repeat([a,b,b,c],3,X).
X = [a, a, a, b, b, c]

I figure the solution is for me to go through the list and for every element repeat it n amount of times but I do not have any clue as to how to do it.
One idea which I attempted was to have the number I pass into the predicate turn into the original upon reaching 1 and then continue the predicate using the tail:

repeat([],_,[]).
repeat(_,0,[]).
repeat([A],Int,[A|X]):- Int1 is Int-1, repeat([A],Int1,X).
repeat([A|Tail],1,[A|X]):- repeat(Tail,Int,X).  % The line where I made a change.
repeat([A|Tail],Int,[A|X]):- Int1 is Int-1, repeat([A|Tail],Int1,X).

This did not work out. I do now know whether I am on the right track for this or not. Any help would be appreciated.

It repeats the first element N times, the next items are only repeated once. This is because you decrement N until it hits zero. But then there is no information anymore about what the original N was. — Willem Van Onsem
I would remove the [A] cases; you don't need them, they're unnecessary edge cases. [A|Tail] unifies with [a] binding A=a, Tail=[]. Also, I would recommend using succ(Int1, Int) instead of Int1 is Int-1 because it will succeed both ways. — Daniel Lyons
Then, the solution is to pass the original N to the tail-predicate? Or am I not understanding correctly? — T44v1
@T44v1: no, you need access to the original N and an N you decrement. From the moment the decrementing counter hits zero, you proceed to the next element in the source list, and you reset that counter with the N you pass around. — Willem Van Onsem

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2017-10-05T16:39:00

Although there are definitely some other issues as well, the most important issue is that you decrement N until it hits zero to repeat the first element. But after it hits zero, of course you do no longer can obtain the original N.

So how can we store the original N? We can simply introduce a new predicate repeat/4, with:

repeat(L, N, LN) :-
    repeat(L, N, N, LN).

So we redirect repeat/3 to repeat/4 by copying N. The idea is that we will decrement only one of the parameters. From the moment that parameter hits zero, we will "reset" the parameter, by fetching the value from the second N (which we do not decrement).

So now we only need to work out repeat/4. In case we reached the end of the list, then - regardless of the value of N - the repetition is an empty list:

repeat([], _, _, []).

in case the first N has reached zero, we proceed to the next element of the list, and reset that N:

repeat([_|T], 0, N, LN) :-
    repeat(T, N, N, LN).

and finally in case we did not yet hit zero, we of course prepend the result with the head of the first list:

repeat([H|T], A, N, [H|LN]) :-
    A > 0,
    A1 is A-1,
    repeat([H|T], A1, N, LN).

If we put it all together, we obtain:

repeat(L, N, LN) :-
    repeat(L, N, N, LN).

repeat([], _, _, []).
repeat([_|T], 0, N, LN) :-
    repeat(T, N, N, LN).
repeat([H|T], A, N, [H|LN]) :-
    A > 0,
    A1 is A-1,
    repeat([H|T], A1, N, LN).

Iterating over list elements in turns in prolog

1 Answers