Find powers of 2 in a list Prolog

Question

I'm trying to create a list in Prolog (SWI Prolog) and check which numbers are powers of 2 and second find how many times a specific number is in the list (in this example I'm trying to find how many times the number 3 is in the list). For a example, if you ask

?- check([0,2,3,-5,-2,1,8,7,4], MULT2, THREE).

you should see

MULT2=[2,8,4] 
THREE=1 

My first try to find a solution is to search the list with head and doing head mod 2 = 0 to find all numbers which are powers of 2, but something went wrong and I only get "false" as an answer.

Anvil

You need to show your coding attempt. Also, is there a reason you are doing powers of 2 and frequency of a given number in a single predicate? They really are two different ideas and would make sense as two different predicates. Is this a homework assignment? – Coeternity

MULT2=[2,1,8,4] would be the correct answer for MULT2 in this case. – Coeternity

I 'm studying Prolog at University I am new in this programming language and I want to learn more things, but this task is for me to understand this difficult (for myself part of Prolog) lists. My previous task was to split the array, and I understand many things. But now I m trying to find how can I crete a predicate to do multiple things. Thanks for the answer! – Anvil

Answer 1

Here's how you can find the "powers of two" in logically-pure way!

Using sicstus-prolog 4.3.5, library(reif) and library(clpz):

:- use_module([library(reif), library(clpz)]).

power_of_two_t(I, T) :-
   L #= min(I,1),
   M #= I /\ (I-1),
   call((L = 1, M = 0), T).      % using (=)/3 and (',')/3 of library(reif)

Sample query¹ using meta-predicate tfilter/3 in combination with power_of_two_t/2:

?- tfilter(power_of_two_t, [0,2,3,-5,-2,1,8,7,4], Ps).
Ps = [2,1,8,4].                  % succeeds deterministically

Here's a more general query suggested by a comment:

?- tfilter(power_of_two_t, [X], Ps).
   Ps = [X], 0#=X/\_A, _A+1#=X, X in 1..sup, _A in 0..sup
;  Ps = [], dif(_A,0), _A#=X/\_B, _B+1#=X, X in 1..sup, _B in 0..sup
;  Ps = [], dif(_A,1), _A#=min(X,1), _B#=X/\_C, _C+1#=X, X#>=_A, _A in inf..1.

---

^{Footnote 1: The answer sequences shown above were brushed up to indicate the determinism of calls.}

^{Footnote 2: To reproduce the results use call_det/2 which is defined like this:}

call_det(G_0, Det) :-
   call_cleanup(G_0, Flag = set),
   (  nonvar(Flag)
   -> Det = true
   ;  Det = false
   ).

Hoard

Purer! As for tfilter(power_of_two_t, [X], P). – Kata

@false. Thanks! I forgot about that one in the meantime ... Better now? – Hoard

Cough, det_call/1. Why not use a purer shell for SICStus? Cor.3 has the missing functionality, and SICStus supports this perfectly! – Kata

Since when I am non-deterministic? det_call(false) fails – Kata

@false. I feel the same. Is the name goal_succeeds_deterministically/1 any better? – Hoard

@mat. My first clpz code and I wouldn't even know how to express the same with SICStus' own clpfd :) – Hoard

Wrong interface. Goals and determinism are something different! – Kata

@false. So call_succeeds_deterministically/1...? – Hoard

You cannot overload failure of a goal with meaning something else. – Kata

@false. So using exceptions could be a proper way here? – Hoard

What about /2? – Kata

@false. call_det(G,Det) succeeds if G succeeds, unifying Det with true or false accordingly? – Hoard

@false. Yes, it looked it up recently. call_semidet/1 throws an exception as soon as a second answer comes up, so it cannot be directly used when we want to know if a choicepoint (which may or may not lead to another answer) is left open, right? – Hoard

So why did you suggest "using exceptions" and rename the concept? ((It's OK for /2)). – Kata

@false. I don't know. Presumably a mixture of ignorance and laziness;) – Hoard

@mat. Wait a minute... is popcount/1 supported by clpz on SICStus? – Hoard

Note to self: clpz:run_propagator//2 is the key: clpz covers exactly the same as (is)/2 does, so msb/1 is supported but popcount/1 is not with SICStus. – Hoard

Nts: help repair library(reif). – Hoard

Answer 2

It's a strange thing to have two such a different tasks to do in one predicate. You should probably have two separate predicates, one for counting number of powers of 2 and one to count 3s. Then you can combine them in one predicate like:

check(Nums, MULT2, THREE) :-
    count2powers(Nums, MULT2),
    count3s(Nums, THREE).

After that you can decompose further and have a separate predicate to check if a number is a power of 2:

is2power(1).
is2power(N) :-
    N > 0,
    N2 is N // 2,
    N2 * 2 =:= N,
    is2power(N2).

This is basic software engineering and this way you can build your program step by step and you will be able to ask more concrete and meaningful questions than just "The whole program returns false."

Usable