view release on metacpan or  search on metacpan

lib/AI/Prolog/Cookbook.pod  view on Meta::CPAN

This definition depends on the C<member/3> predicate defined in this document.

 gather([], _, []).
 gather([First|Remaining], FromList, [ResultHead|ResultTail]) :-
    member(First, ResultHead, FromList),
    gather(Remaining, FromList, ResultTail).

Example queries:

 gather([2,4], [a,b,c,d,e], Result).      % Result = [b,d]
 gather(FromIndices, [a,b,c,d,e], [b,d]). % FromIndices = [2,4]

This example is tricky when one realizes that one can reuse predicates.  In
this case, it might be tempting to see I<which> lists from which one can
gather certain values from certain indices.  The first time you try it, you
may get results as follows:

 gather([2,4], WhichList, [x,y]).

This query, when executed in the C<aiprolog> shell will output a response
similar to this:

 gather([2,4], [A,x,B,y|C], [b,d]).

When examining this, we see that the first, third, and fifth elements (and
beyond) of the list are variables.  Unfortunately, as an infinite number of
lists will satisfy this goal, attempting to fetch the a second result from the
same query will result in an infinite loop.

=head2 Determine the intersection of two lists.

Usage: C<intersection(List1, List2, Intersection).>

This definition depends on the C<member/2> predicate defined in this document.

 intersection([H|T], L, [H|U]) :-
    member(H,L),
    intersection(T,L,U).
 intersection([_|T], L, U) :-
    intersection(T,L,U).
 intersection(_,_,[]).

The C<intersection/3> predicate will compute the intersection of two lists.
You probably only want the first result from this predicate.  See C<trace/0>
to understand why it returns more than one intersection.

=head2 Reverse a list.

Usage:  C<reverse(List, ReversedList).>

 reverse(List, Reverse) :-
    reverse_accumulate(List, [], Reverse).
 reverse_accumulate([], List, List).
 reverse_accumulate([Head|Tail], Accumulate, Reverse) :-
    reverse_accumulate(Tail, [Head|Accumulate], Reverse).

Reversing a list is tricky.  If this predicate were written in an imperative
manner, it might look something like this:

 sub reverse {
   my @list = @_;
   my @reverse;
   while (my $element = shift @list) {
     unshift @reverse, $element;
   }
   return @reverse;
 }

This method of reversing a list runs in C<O(n)> time.  However, new Prolog
programmers often  write what is known as the "naive reverse" which uses the
C<append/3> predicate to reverse a list:

 reverse([],[]).
 reverse([Head|Tail], Reverse) :- 
    reverse(Tail, ReverseTail), 
    append(ReverseTail, [Head], Reverse).

For this, you take the tail of the list, reverse it and append the head of the
list to it.  However, this runs in C<O(N^2)>.  This runs so slowly that
reversing a 30 element list takes 496 logical inferences.  As a result, the
naive reverse is frequently used as a benchmarking tool for logic programs.

If reversing a 30 element list via the naive reverse takes .1 seconds, we can
say that the Prolog implementation is running at about 5000 logical inferences
per second.  This is known by the unfortunate acronym of LIPS, the standard
measure of the speed of logic programs.  Modern Prolog implementations
frequently measure their performance in MLIPS, or MegaLIPS.  By contrast, the
human mind is frequently estimated to run between 1 to 4 LIPS.  This
demonstrates that there's much more to cognition than logic.

=head2 Checking if a list is a subset of another list.

Usage:  C<subset(Subset, List).>

This definition depends on the C<member/2> predicate defined in this document.

 subset([Head|Tail], List) :-
    member(Head, List),
    subset(Tail, List).
 subset([], _). % The empty list is a subset of all lists

=head2 Delete all occurences of a term from a list, giving a new list.

Usage:  C<delete(Term, List, Result).>

 delete(_,[],[]). % deleting anything from an empty list yields an empty list
 delete(Term, [Term|Tail], Result) :- 
    delete(Term, Tail, Result).
 delete(Term, [Head|Tail], [Head|TailResult]) :- 
    delete(Term, Tail, TailResult).

=head2 Partition a list where list values <= Value.

Usage: C<partition(Value, List, LHS, RHS).>

Note that the term at I<Value> will be included in the I<LHS>.

 partition(Value, [Head|Tail], [Head|LHS], RHS) :-
    Head <= Value,
    partition(Value, Tail, LHS, RHS).
 partition(Value, [Head|Tail], LHS, [Head|RHS]) :-
    partition(Value, Tail, LHS, RHS).
 partition(_,[],[],[]).

=head2 Quicksort.

Usage: C<sort(List, Sorted).>

This definition depends on the C<partition/4> and C<append/3> predicates
defined in this document.

 sort([], []).
 sort([Head|Tail], Sorted) :-
    partition(Head, Tail, LHS, RHS),
    sort(LHS, Temp1),
    sort(RHS, Temp2),
    append(Temp1, [Head|Temp2], Sorted).

Note that (currently), this will only sort numeric values.

=head1 SEE ALSO

L<AI::Prolog>

L<AI::Prolog::Builtins>

L<AI::Prolog::Introduction>

W-Prolog:  L<http://goanna.cs.rmit.edu.au/~winikoff/wp/>

X-Prolog:  L<http://www.iro.umontreal.ca/~vaucher/XProlog/>

Roman BartE<225>k's online guide to programming Prolog:
L<http://kti.ms.mff.cuni.cz/~bartak/prolog/index.html>

=head1 AUTHOR

Curtis "Ovid" Poe, E<lt>moc tod oohay ta eop_divo_sitrucE<gt>

Reverse the name to email me.