Inserting elements into indexes that are the powers of 2 [Prolog]-CodePudding

I have to insert an element into a list on the positions that are powers of 2

e.g. in the list

L = [1, 2, 3, 4, 5, 6, 7, 8]

I should insert an element E = 0 after the first element, then the third, then the 7th, etc. so the resulting list would be

R = [1, 0, 2, 3, 0, 4, 5, 6, 7, 0, 8]

I tried using the predefined predicate nth1/4 to add an element into a list at a position P and then increase the position P by multiplying it with 2

%empty list
ins_aux(_, [], _, _, []).
%if the position is even, add the element and then multiply P by 2 
%and add a value K which is incremented at every step to get the next position 
ins_aux(E, L, P, K, Res) :- 0 is mod(P, 2), !, 
                         nth1(P, Res, E, L), 
                         P1 is (P*2) K,
                         K1 is K 1,
                         ins_aux(E, Res, P1, K1, Res).
%if the position is odd, add the element to the list 
ins_aux(E, L, P, K, Res) :- nth1(P, Res, E, L),
                         P1 is P 1,
                         ins_aux(E, Res, P1, K, Res).

My issue is that this always outputs false. I am clearly doing something wrong it's just that I don't know what

CodePudding user response：

Why use nth1 in ins_aux? This makes things ... unnecessarily quadratic:)

Here's how you could do it:

ins_aux([],_,_,[]).
ins_aux([E|Es],X,I,[E,X|Rs]) :-
    I /\ (I-1) =:= 0,              % I is a power of two
    !,
    I1 is I   1,
    ins_aux(Es,X,I1,Rs).
ins_aux([E|Es],X,I,[E|Rs]) :-
    I /\ (I-1) =\= 0,              % I is not a power of two
    I1 is I   1,
    ins_aux(Es,X,I1,Rs).

Sample query:

?- ins_aux([1,2,3,4,5,6,7,8],0,2,Rs).
Rs = [1,0,2,3,0,4,5,6,7,0,8].