Prolog - first of findall without actually finding all

Author

first of findall without actually finding all

Reuben Grinberg

2007-04-12, 10:03 pm

I'm using a library that can tokenize based on a regular expression. The
first match is the greediest, which is what I want, but then there are
more matches:

| ?- tokenize(" +|([a-zA-Z][a-zA-Z0-9]*)", "jack bob",Y).
Y = [jack,bob] ? ;
Y = [jack,bo,b] ? ;
Y = [jack,b,ob] ? ;
Y = [jack,b,o,b] ? ;
Y = [jac,k,bob] ? ;
Y = [jac,k,bo,b] ? ;
Y = [jac,k,b,ob] ? ;
....

At first, I got around this problem by calling findall on tokenize and
then using the first element of the generated list. Obviously this isn't
sustainable because it has exponential runtime in the length of the
input string.

Is there a findfirst function or something like that that would work in
this situation?

Thanks,
Reuben

Peter Van Weert

2007-04-12, 10:03 pm

Reuben Grinberg schreef:
> I'm using a library that can tokenize based on a regular expression. The
> first match is the greediest, which is what I want, but then there are
> more matches:
>
> | ?- tokenize(" +|([a-zA-Z][a-zA-Z0-9]*)", "jack bob",Y).
> Y = [jack,bob] ? ;
> Y = [jack,bo,b] ? ;
> Y = [jack,b,ob] ? ;
> Y = [jack,b,o,b] ? ;
> Y = [jac,k,bob] ? ;
> Y = [jac,k,bo,b] ? ;
> Y = [jac,k,b,ob] ? ;
> ...
>
> At first, I got around this problem by calling findall on tokenize and
> then using the first element of the generated list. Obviously this isn't
> sustainable because it has exponential runtime in the length of the
> input string.
>
> Is there a findfirst function or something like that that would work in
> this situation?

Maybe a cut is what you need, i.e.:

| ?- tokenize(" +|([a-zA-Z][a-zA-Z0-9]*)", "jack bob",Y), !.

Cheers,
Peter

Reuben Grinberg

2007-04-13, 4:03 am

Peter Van Weert wrote:
> Reuben Grinberg schreef:
>
> Maybe a cut is what you need, i.e.:
>
> | ?- tokenize(" +|([a-zA-Z][a-zA-Z0-9]*)", "jack bob",Y), !.
>
> Cheers,
> Peter

Awesome! That did it.

Do you have suggestions for going the other way?

One of my functions doesn't return what I need until the last, uh,
iteration (what should I call a different substitution). So right now
I'm using findall and then getting the last element. Is there a better
solution?

Peter Van Weert

2007-04-13, 8:03 am

Reuben Grinberg schreef:
> Peter Van Weert wrote:
....[color=darkred]
>
> Awesome! That did it.
>
> Do you have suggestions for going the other way?
>
> One of my functions doesn't return what I need until the last, uh,
> iteration (what should I call a different substitution). So right now
> I'm using findall and then getting the last element. Is there a better
> solution?

Of course it is always better to concoct an algorithm that gives you the
correct answer immediately. But if this is not possible, you could try
to improve performance as best as you can. In SWI you can e.g. write:

findlast(X, G) :-
(
call(G),
nb_setval(findlast_answer, X),
fail
;
nb_current(findlast_answer, X),
nb_delete(findlast_answer)
).

This way, space complexity is constant instead of linear. It also seems
to run faster:

?- time((Y = 5000000, findall(X, between(1,Y,X), Z), last(Z,A))).
% 10,000,013 inferences, 7.09 CPU in 9.83 seconds (72% CPU, 1409693 Lips)

?- time((Y = 5000000, findlast(A, between(1,Y,A)))).
% 15,000,006 inferences, 3.08 CPU in 3.30 seconds (93% CPU, 4873098 Lips)

Time complexity remains linear in the number of solutions though. Also,
it uses a non-standard non-backtrackable global variable, so it will not
work for every Prolog system.

Cheers,
Peter

Sponsored Links