Generating partial list

Help!
1

Hello,

I am blanking on the following:

I am writing a recursive search procedures that is supposed to generate a list (actually two lists, but for now, lets consider one).

The procedure progresses in the search space via recursive calls, and at each step, checks if a condition holds. If it does then a element is added to the list and if the condition doesn’t hold the list stays the same for the next iteration.

Usually, one uses the [First | Rest] accumulator pattern to generate a First that gets appended during recursion to Rest, but in my case First may be omitted sometimes.

I am blanking on the pattern to use …

much appreciating any thoughts,

thanks

p.s. in the arg list there are indeed two [First_1 | Rest_1], [First_2, Rest_2] and each First_1 and First_2 can independently be omitted due to a condition that holds or doesn’t hold.

Edit:

I could use global variables as accumulators and use the recursion to simply search across the search space, … to avoid dealing with accumulators and their respective variant calls under different conditions.

2

How about using DCG to accumulate the list?
Say we’re looking for primes, we could write:

primes(N) -->
    {   searched_for_long_enough(N)   },
    !.
primes(N0) -->
    {   is_prime(N0),
        !,
        N is N0 + 1
    },
    [N],
    primes(N).
primes(N0) -->
    {   N is N0 + 1   },
    primes(N).
3

I often use something like this:

p -->
    (  { q(..., NewValue) }
    -> [NewValue]
    ;  []
    ),
    ....

Note that if you use EDCGs instead of DCGs, you can have multiple accumulators; you annotate the [...] with the name of an accumulator.

4

There is a whole chapter on the topic of searching with Prolog in “The Craft of Prolog”. It is maybe the most generally useful chapter of that book.

5

Would you mind presenting this in a vanilla prolog style …and not DCG, i am curious how this would look like

6

You can always use listing/1,2 to see the DCG converted to native code.

One place loaded with lots of working examples of recursive list construction is in the SWI-Prolog source code on GitHub.

Having spent much time browsing those files I know that Jan W. uses the conditional (-> ;) often with the pattern you seek. However searching for that is not easy but the code often also uses = [] and that does lead to examples of what you seek, e.g. (ref)

%!  zipper_members_(+Zipper, -Members) is det.
%
%   Simplified version of zipper_members/2 from library(zip). We already
%   have a lock  on  the  zipper  and   by  moving  this  here  we avoid
%   dependency on another library.
%
%   @tbd: should we cache this?

zipper_members_(Zipper, Members) :-
    zipper_goto(Zipper, first),
    zip_members__(Zipper, Members).

zip_members__(Zipper, [Name|T]) :-
    zip_file_info_(Zipper, Name, _Attrs),
    (   zipper_goto(Zipper, next)
    ->  zip_members__(Zipper, T)
    ;   T = []
    ).
7

Right, the T= patterns comes to mind, but if i insert it in the head of an argument then i end up with composite list of empty lists which needs flattening – something i wanted to avoid.

8

That is confusing. T is the tail but you are noting head which is typically used with the variable H.

The problem with trying to find more practical and simple examples is that as the others have noted, this is typically done with DCG or EDCG.

Earlier I checked to see if RosettaCode had a nice FizzBuzz example for Prolog doing what you wanted but the examples there were so terrible I didn’t even want to reference them.

EDIT

Since what you need seems similar to partition/4 here is the code behind the predicate

%!  partition(:Pred, +List, ?Included, ?Excluded) is det.
%
%   Filter elements of List according  to   Pred.  True  if Included
%   contains all elements  for  which   call(Pred,  X)  succeeds and
%   Excluded contains the remaining elements.
%
%   @see include/3, exclude/3, partition/5.

partition(Pred, List, Included, Excluded) :-
    partition_(List, Pred, Included, Excluded).

partition_([], _, [], []).
partition_([H|T], Pred, Incl, Excl) :-
    (   call(Pred, H)
    ->  Incl = [H|I],
        partition_(T, Pred, I, Excl)
    ;   Excl = [H|E],
        partition_(T, Pred, Incl, E)
    ).