CODEWITHSUNDEEP
prolog
pw94
pw94

Reputation: 401

Add following numbers to difference list in Prolog

I created a program in Prolog which returns following powers of two starting from one:

twos(N, L) :- twosH(N, 1, L).

twosH(0, _, L) :- L = [], !.
twosH(N, I, [R|L]) :- R is 2*I, N1 is N-1, twosH(N1, R, L).

I would like it to use difference list instead of regular one. I know how to append an element to difference list:

appendD(A-B, B-C, A-C).

but I don't know how to incorporate it into my program.

Upvotes: 1

Views: 45

Answers (1)

lurker
lurker

Reputation: 58254

If you use a DCG, then you are using a difference list:

powers_of_2(0, 1) --> [1].
powers_of_2(N, PT) --> [PT], { PT #= 2 * PT1, N #> 0, N #= N1 + 1 }, powers_of_2(N1, PT1).

powers_of_2(N, PT) :-
    phrase(powers_of_2(N, _), PT).

| ?- powers_of_2(4, P).

P = [16,8,4,2,1] ? ;

no
| ?-

A listing of what the DCG looks like as standard predicates (obtained by entering listing. then I changed the variable names a little):

powers_of_2(0, 1, [1|T], T).
powers_of_2(N, PT, [PT|PTs], T) :-
        PT #= 2 * PT1,
        N #> 0,
        N #= N1 + 1,
        powers_of_2(N1, PT1, PTs, T).

If you called it directly, you would give it the empty list as the final tail:

| ?- powers_of_2(4, P, PT, []).

P = 16
PT = [16,8,4,2,1] ? ;

no

If you want the numbers in the reverse order, I'll leave that as an exercise. :)

Upvotes: 2

Related Questions