PLOGHELP HIGHER_ORDER                            Simon Nichols, May 1992


A library which defines some higher-order predicates.

    ?- library(higher_order).


         CONTENTS - (Use <ENTER> g to access required sections)

 -- Introduction
 -- Operations on Lists
 -- ... maplist(+Pred, +Xs)
 -- ... maplist(+Pred, +Xs, ?Ys)
 -- ... reduce(+Pred, +Xs, ?Answer)
 -- Operations on Terms
 -- ... mapargs(+Pred, +Term)
 -- ... mapargs(+Pred, +Term1, ?Term2)


-- Introduction -------------------------------------------------------

For practical purposes, a higher-order predicate is one which takes as
arguments a predicate and some data, and applies the predicate to the
data or (more usually) to components of the data. This can be done
efficiently in Poplog Prolog using the call/N family of predicates (see
PLOGHELP * CALL) which are the basis of the predicates defined in
library(higher_order).


-- Operations on Lists ------------------------------------------------

Each of the following operations applies a predicate to successive
elements from a list or lists. The use of maplist/2 and maplist/3 in
particular situations often removes the necessity of writing a special
purpose recursive predicate to process the elements of a list.

-- ... maplist(+Pred, +Xs) --------------------------------------------

is true when Pred(X) is true for each element X in the list Xs.

For example: to determine whether each number in a list of numbers is
odd we need only write a predicate which tests whether a single number
is odd:

    odd(X) :- 1 is X mod 2.
    ?- maplist(odd, [1,3,5,7,9]).
    yes

Used in this way, maplist/1 is equivalent to the function all or every
provided by most functional languages,

Another example: printing a string (list of character codes):

    ?- maplist(put, "Hello world"), nl.
    Hello world
    yes

Used like this, maplist/1 is equivalent to the Lisp function MAPC and
the Pop11 procedure applist.

-- ... maplist(+Pred, +Xs, ?Ys) ---------------------------------------

is true when Pred(X, Y) is true for each corresponding element X in the
list Xs and Y in the list Ys. "Corresponding" means X and Y have the
same index (position) in their respective lists.

This is commonly used to derive a new list Ys obtained by applying Pred
to each element X of Xs. For example, given a list of numbers we can
create a new list in which each element is double the corresponding
element from the original list as follows:

    double(X, Y) :- Y is 2*X.
    ?- maplist(double, [2,3,4,5], X).
    X = [4, 6, 8, 10] ?
    yes

This usage is equivalent to the classic map function of functional
languages, Lisp's MAPCAR and the Pop11 procedure maplist.

-- ... reduce(+Pred, +Xs, ?Answer) ------------------------------------

is true when Pred(X0, [], Answer0) is true and Pred(XI, AnswerI-1,
AnswerI) is true for all I where 0 < I < N and XI is the Ith element of
Xs.

In procedural terms, Pred is initially applied to the head of the list
and the empty list, yielding Answer0. Pred will then be applied to the
second element of the list (if there is one) and Answer0 (the result
from the previous application of Pred), yielding Answer1. The process is
repeated, applying Pred to each subsequent list element and the result
of the previous application. This description assumes a call of reduce/3
with Answer unbound, as an output argument.

For example, to find the sum of all the numbers in a list of numbers:

    add(X,Y,Z) :- Z is X+Y.
    ?- reduce(add, [1,2,3,4,5], X).
    X = 15
    yes

To find the largest number in a list of numbers:

    max(X, Y, X) :- X >= Y.
    max(X, Y, Y) :- X < Y.
    ?- reduce(max, [2,8,3,7,4], X).
    X = 8
    yes

-- Operations on Terms ------------------------------------------------

Each of the following operations applies a predicate to successive
arguments from a term or terms. In any particular situation, their use
removes the necessity of writing a special purpose recursive predicate
to process the arguments of a term, making use of functor/3 and arg/3.

-- ... mapargs(+Pred, +Term) ------------------------------------------

is true when Pred(Arg) is true for each argument Arg of Term.

A good example of the use of mapargs/2 is the definition ground/1, which
is true if its argument is ground (a term which contains no variables):

    ground(X) :-
        nonvar(X),
        mapargs(ground, X).

    ?- ground(f(g(x,y))).
    yes

    ?- ground(f(g(x,Y))).
    no

Note that it is quite in order for mapargs/2 (and mapargs/3) to be given
an atom as the first argument, since an atom is equivalent to a compound
term with no arguments.

-- ... mapargs(+Pred, +Term1, ?Term2) ---------------------------------

is true when Pred(Arg1, Arg2) is true for the Ith argument Arg1 of Term1
and the Ith argument Arg2 of Term2, where Term1 and Term2 have the same
functor and 1 <= I <= arity of each term.

As an example, the predicate simplify/2 applies the rules x+0=x and
0+x=x to simplify an algebraic expression (where variables are
represented by Prolog atoms):

    simplify(X+0, Y) :-
        simplify(X, Y).
    simplify(0+X, Y) :-
        simplify(X, Y).
    simplify(X, Y)  :-
        mapargs(simplify, X, Y).

    ?- simplify(a*b+0-c*d+0, X).
    X = a * b - c * d ?
    yes

Without mapargs/3, the definition of simplify/2 would be much longer and
would involve a subsidiary predicate to process arguments and two calls
each to functor/3 and arg/3.


--- C.all/plog/help/higher_order
--- Copyright University of Sussex 1992. All rights reserved. ----------