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. ----------