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

Question

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

repeat · Accepted Answer · 2022-11-17T12:37:27.090

3

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|Rs0]) :-
   (  I /\ (I-1) =\= 0
   -> Rs0 = Rs1                  % I is not a power of two
   ;  Rs0 = [X|Rs1]              % I is     a power of two
   ),
   I1 is I + 1,
   ins_aux(Es,X,I1,Rs1).

Sample queries using Scryer Prolog:

?- 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].

?- ins_aux([a,b,c,d,e,f,g,h],0,2,Rs).
   Rs = [a,0,b,c,0,d,e,f,g,0,h].

edited Nov 17 '22 at 12:37

answered Oct 30 '22 at 18:52

repeat

18,496
4
54
166

1

Wow! Thanks so much for the solution, but uhh... I did not know about this /\ operator... is it like pow()? – xlao1241 Oct 30 '22 at 19:15
2

See https://www.swi-prolog.org/pldoc/doc_for?object=f((/%5C)/2) and https://stackoverflow.com/questions/600293/how-to-check-if-a-number-is-a-power-of-2 – brebs Oct 30 '22 at 20:56
1

Are these cuts really necessary? Would not a clean if-then-else be preferable, after all `(=:=)/2` ensures with instantiation errors that the expression and thus `I` is sufficiently instantiated. – false Nov 17 '22 at 09:51
1

And speaking of efficiency, note that the second case is much more frequent than the first.... – false Nov 17 '22 at 09:52
One more: 1 is a power of two. Is it not? – false Nov 17 '22 at 11:42
@false. It is. But this is about the index, not about the element itself. I think the added query should make that clearer. – repeat Nov 17 '22 at 12:38
The 1st element is the (2⁰)th. Is it not? – false Nov 17 '22 at 15:05
@false. Yes. `[1,x,2,x,3,4,x,5,6,7,8,x,...]` vs `[1,x,2,3,x,4,5,6,7,x,8,...]`. Arguably, the former one is the right one, but the OP wanted the latter. – repeat Nov 17 '22 at 15:15

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

1 Answers1