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.

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? — lurker, Feb 03 '14 at 02:00
`MULT2=[2,1,8,4]` would be the correct answer for `MULT2` in this case. — lurker, Feb 03 '14 at 02:11
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! — yannisalexiou, Feb 03 '14 at 02:25

repeat · Accepted Answer · 2017-12-01T19:36:29.440

5

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
   ).

edited Dec 01 '17 at 19:36

answered May 13 '15 at 09:48

repeat

18,496
4
54
166

1

Purer! As for `tfilter(power_of_two_t, [X], P)`. – false Nov 16 '17 at 15:14
@false. Thanks! I forgot about that one in the meantime ... Better now? – repeat Dec 01 '17 at 17:10
1

Cough, `det_call/1`. Why not use a purer shell for SICStus? [Cor.3](http://www.complang.tuwien.ac.at/ulrich/iso-prolog/WDCor3#variable_names) has the missing functionality, and SICStus supports this [perfectly](http://www.complang.tuwien.ac.at/ulrich/iso-prolog/variable_names)! – false Dec 01 '17 at 17:33
1

Since when I am non-deterministic? `det_call(false)` fails – false Dec 01 '17 at 17:34
@false. I feel the same. Is the name `goal_succeeds_deterministically/1` any better? – repeat Dec 01 '17 at 17:44
@mat. My first `clpz` code and I wouldn't even know how to express the same with SICStus' own clpfd :) – repeat Dec 01 '17 at 17:58
Wrong interface. Goals and determinism are something different! – false Dec 01 '17 at 18:00
@false. So `call_succeeds_deterministically/1`...? – repeat Dec 01 '17 at 18:01
You cannot overload failure of a goal with meaning something else. – false Dec 01 '17 at 18:02
@false. So using exceptions could be a proper way here? – repeat Dec 01 '17 at 18:04
What about `/2`? – false Dec 01 '17 at 18:04
1

@false. `call_det(G,Det)` succeeds if `G` succeeds, unifying `Det` with `true` or `false` accordingly? – repeat Dec 01 '17 at 18:07
@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? – repeat Dec 01 '17 at 19:50
So why did you suggest "using exceptions" and rename the concept? ((It's OK for /2)). – false Dec 01 '17 at 19:58
@false. I don't know. Presumably a mixture of ignorance and laziness;) – repeat Dec 01 '17 at 20:03
@mat. Wait a minute... is `popcount/1` supported by `clpz` on SICStus? – repeat Dec 01 '17 at 23:24
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. – repeat Dec 01 '17 at 23:31
1

Nts: help repair `library(reif)`. – repeat Dec 02 '17 at 00:03

score 1 · Answer 2 · answered Feb 03 '14 at 02:02

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."

Find powers of 2 in a list Prolog

2 Answers2

Linked