Simple counting from 0 - N
treize
As I have just started learning Prolog I am still trying to grasp how
exactly certain problems are best handled in this language and I
decided to test my knowledge with a simple problem (or so I thought).
The problem I devised for myself was to write a simple predicate that
takes two arguments (lets call them N and R) and if you pass in an
integer value for N it will return every value from 0 to N as the
solution for R. The best thing I could come up with involved using
lists and goes something like:
test(N,R) :-
test(N,[], L),
member(R,L).
test(0,L,L).
test(N,A,L) :-
N>0,
B is N - 1,
test(B,[N|A],L).
where member() is used to assign the different solutions. But I keep
thinking to myself that there must be a much simpler way of achieving
this without using lists, but so far all my attempts have ended up in
the stack running out of space or the error that my variables weren't
instantiated properly (I am using SWI).
Can anyone offer any tips, hints or perhaps even a solution for
addressing this deceptively simple issue?
Thanks for any insights you may provide.
Markus Triska
> solution for R. The best thing I could come up with involved using
> lists and goes something like:
This does not satisfy the requirement, as R=0 is never a solution, e.g.:
?- test(0, R).
%@ false.
?- test(1, R).
%@ R = 1 ;
%@ false.
> Can anyone offer any tips, hints or perhaps even a solution for
> addressing this deceptively simple issue?
The following solutions work for non-negative N; you can adapt them to
work for all integers. A simple solution in SWI Prolog is:
zero_to_n(N, R) :- between(0, N, R).
If you do not want to use between/3, you can use:
zero_to_n(N, R) :-
N >= 0,
zero_to_n_(0, N, R).
zero_to_n_(From, _, From).
zero_to_n_(From0, N, R) :-
From0 < N,
From is From0 + 1,
zero_to_n_(From, N, R).
Example:
?- zero_to_n(3, N).
%@ N = 0 ;
%@ N = 1 ;
%@ N = 2 ;
%@ N = 3 ;
%@ false.
--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
Guy Barry
"treize" <treize...@gmail.com> wrote in message
news:5b6a2dfc-64d0-413d...@m16g2000yqc.googlegroups.com...
> Hi,
>
> As I have just started learning Prolog I am still trying to grasp how
> exactly certain problems are best handled in this language and I
> decided to test my knowledge with a simple problem (or so I thought).
> The problem I devised for myself was to write a simple predicate that
> takes two arguments (lets call them N and R) and if you pass in an
> integer value for N it will return every value from 0 to N as the
> solution for R.
I haven't used Prolog for years, but I think this ought to work:
test(N, R) :-
N > 0,
N1 is N-1,
test(N1, R).
test(N, N).
--
Guy Barry
Markus Triska
> test(N, R) :-
> N > 0,
> N1 is N-1,
> test(N1, R).
>
> test(N, N).
Consider though:
%?- test(10^10, R).
%@ ERROR: Out of local stack
%@ Exception: (1,863,623) test(9998136384, _G0) ? abort
%@ % Execution Aborted
whereas:
%?- zero_to_n(10^10, R).
%@ R = 0 ;
%@ R = 1 ;
%@ R = 2 ;
%@ R = 3 ;
%@ etc.
Guy Barry
"Markus Triska" <tri...@logic.at> wrote in message
news:m2pr83b...@logic.at...
> "Guy Barry" <guy....@blueyonder.co.uk> writes:
>
> > test(N, R) :-
> > N > 0,
> > N1 is N-1,
> > test(N1, R).
> >
> > test(N, N).
>
> Consider though:
>
> %?- test(10^10, R).
> %@ ERROR: Out of local stack
> %@ Exception: (1,863,623) test(9998136384, _G0) ? abort
> %@ % Execution Aborted
Indeed - implementational elegance versus computational efficiency. Thanks
for pointing that out.
--
Guy Barry
metaperl
>
> Indeed - implementational elegance versus computational efficiency. Thanks
> for pointing that out.
I'm missing it - why did yours blow the stack? It looks 'tail-
recursive' to me.
Guy Barry
"metaperl" <sche...@gmail.com> wrote in message
news:483f8065-f538-44f9...@r36g2000vbn.googlegroups.com...
On Oct 31, 11:58 am, "Guy Barry" <guy.ba...@blueyonder.co.uk> wrote:
> I'm missing it - why did yours blow the stack? It looks 'tail-
> recursive' to me.
I admit that I thought the same thing when I suggested it. I presume it's
because of the number of copies of local variables that have to be kept in
memory - you need to store every integer from N down to 1 before the first
result appears.
That raises a question about Markus Triska's program, though: wouldn't it
run into the same problem eventually, with the number of solutions returned
limited by the size of the stack? There's no actual difference in
*structure* between my program and his, except that in his the base clause
comes first and in mine it comes last.
--
Guy Barry
Markus Triska
> run into the same problem eventually, with the number of solutions
> returned limited by the size of the stack?
No, local stack usage is O(1) for zero_to_n/2. For illustration:
?- zero_to_n(10^10, R), ignore((R mod 10^6 =:= 0,writeln(R))), false.
%@ 0
%@ 1000000
%@ 2000000
%@ 3000000
%@ 4000000
%@ 5000000
%@ 6000000
%@ 7000000
%@ 8000000
%@ 9000000
%@ 10000000
%@ 11000000
%@ 12000000
%@ etc.
> There's no actual difference in *structure* between my program and
> his, except that in his the base clause comes first and in mine it
> comes last.
Tail call optimisation only applies in deterministic cases. metaperl
correctly said that your recursive call is also in a tail position.
However, when alternatives are left to try, stack frames are preserved.
Guy Barry
> Tail call optimisation only applies in deterministic cases. metaperl
> correctly said that your recursive call is also in a tail position.
> However, when alternatives are left to try, stack frames are preserved.
Suppose, then, that I reverse the order of clauses in my program so that it
counts down from N to 0:
test(N, N).
test(N, R) :-
N > 0,
N1 is N-1,
test(N1, R).
I presume from what you're saying that this wouldn't run into overflow
problems. Am I right?
--
Guy Barry
Ulrich Neumerkel
You are discussing efficiency issues, but please do not forget the
correctness issues too!
?- test(-1, R).
Is this counting down from N to 0?
Guy Barry
"Ulrich Neumerkel" <ulr...@mips.complang.tuwien.ac.at> wrote in message
news:2009Nov...@mips.complang.tuwien.ac.at...
> You are discussing efficiency issues, but please do not forget the
> correctness issues too!
>
> ?- test(-1, R).
>
> Is this counting down from N to 0?
I was assuming the program wouldn't be used with negative integers, but an
appropriate condition can be added to the base clause if necessary.
--
Guy Barry
g9414002.p...@gmail.com
No, both your codes and Markus's codes would run into stack overflow.
No optimization actually reduces the number of items that must be kept
in
the stack.
Markus's illustrations showed that available answers were output
and not blocked by alternative solving actions, but it didn't mean
that the
space limit of stack was overcame.
I've tried Markus's codes with the fashion of yours, i.e.,
zero_to_n( ......
zero_to_n_(From0, N, R) :-
From0 < N,
From is From0 + 1,
zero_to_n_(From, N, R).
zero_to_n_(From, _, From).
In GNU Prolog, when querying and pressing 'a' to generate all answers,
it
stopped because of out of stack.