The simplest schema for processing a list computes a single
result from the contents of a list, treating every member of
the list in exactly the same way. For example, you might be
adding up the numbers in a list, or multiplying them together.
Here is such a schema - we'll call the predicate `listSchema`

.
If you use any of the schemata in this article,
you'll need to change the name `listSchema`

to something appropriate to the problem you are trying to solve:

**Schema 1: doing the same thing to every member of a list**

% first the base case - figure out what should happen to the % empty list, and replaceThe first rule will be used if the list is empty, and the second rule will be used if the list is not empty. Thus, in a particular case, there is only ever one rule that is applicable. For example, if you are adding up the items in a list of numbers, then replaceResultForEmptyListwith the % value that your code should produce for the empty list. listSchema([],ResultForEmptyList). % second and last, the recursive case - if the list isnot% empty, then it has a first element, which is followed by the % rest of the list: listSchema([First | Rest], Result) :- listSchema(Rest, RestResult),compute Result given First, and RestResult.

*ResultForEmptyList*

with
`0`

, and the last line of the recursive rule with
`Result is RestResult + First`

.
So the final code in
this case (renamed as `sumList`

) would be
% sumList(List, Sum) adds up the numbers in a List that consists % only of numbers and binds the result to Sum. sumList([], 0). sumList([First | Rest], Sum) :- sumList(Rest, RestResult), Sum is RestResult + First.

This all works provided the items in the list are indeed all numbers. Use the next schema for dealing with cases where this might not be so.

The schema above works provided the result being produced does
not involve reconstructing the list as you process the items in it.
Schema 2, below, deals with the case where the result is a new list.

**Schema 2: transforming every member of a list, result is a new list**

% First the base case - figure out what should happen to the % empty list, and replaceResultForEmptyListwith the % value that your code should produce for the empty list. % Often, the result for the empty list is the empty list again. listSchema([],ResultForEmptyList). % Second and last, the recursive case - if the list isnot% empty, then it has a first element, which is followed by the % rest of the list: listSchema([First | Rest], [NewFirst | RestResult]) :- listSchema(Rest, RestResult),compute NewFirst, the transformed version of First.

For example, if we are starting with a list of numbers, and
producing as a result the list of squares of those numbers,
then we would replace
*compute NewFirst, the transformed version of First*
with
`NewFirst is First * First`

.

So the final code in
this case (renamed as `squareList`

) would be

% squareList(List, ListOfSquares) binds ListOfSquares to a % list consisting of the squares of the numbers in List. squareList([], []). squareList([First | Rest], [NewFirst | RestResult]) :- squareList(Rest, RestResult), NewFirst is First * First.

A slightly more complex schema is for processing a list,
but testing each item in the list for some condition, and
doing different things with the item depending on whether it
does, or does not, satisfy the condition. This requires a
base case, and *two* recursive cases:

**Schema 3: doing different things to the members of a list**

% First the base case - again, work out what should happen to the % empty list, and replaceOnce again, only one of these three rules can be applicable in a particular case. If the list is empty, the base rule is used. If the list is not empty and the condition is satisfied, the first recursive rule is used. If the list is not empty and the condition is not satisfied, the second recursive rule is used. For example, suppose that we want to add up the numbers in a list of items not all of which are numbers. Once again, the result for the empty list will beResultForEmptyListwith the % value that your code should produce for the empty list. listSchema([],ResultForEmptyList). % Second, the recursive case for when the item satisfies the % condition. As before, if the list isnot% empty, then it has a first element, which is followed by the % rest of the list: listSchema([First | Rest], Result) :-goal to test for condition, listSchema(Rest, RestResult),computeResultgivenFirst, andRestResult. % Third and last, the recursive case for when the item does % not satisfy the condition. As usual, if the list isnot% empty, then it has a first element, which is followed by the % rest of the list: listSchema([First | Rest], Result) :-goal to test that condition is, listSchema(Rest, RestResult),notsatisfiedcomputeResultgivenFirst, andRestResult.

`0`

.
To check that the first item is a number, you could use the
built-in Prolog predicate `number`

,
so your condition would be `number(First),`

, and to
compute the `Result`

you would, as in the previous
schema, use `Result is RestResult + First`

.
In the third rule, you'd use `not(number(First)),`

and a first cut at computing the Result in this case would be
`Result = RestResult`

. However, this line could then
be eliminated by simply putting `RestResult`

in the
result position in the head of this rule.
So the final code in
this case (renamed as `addNumbers`

) would be
% addNumbers(List, Sum) adds up the numbers in the List (and ignores % non-numbers) and binds the result to Sum. addNumbers([], 0). addNumbers([First | Rest], Result) :- number(First), addNumbers(Rest, RestResult), Result is First + RestResult. addNumbers([First | Rest], RestResult) :- not(number(First)), addNumbers(Rest, RestResult).

More complicated cases, which need to look at the first *two*
members of the list in order to decide how to handle the list, might
need two base cases - one to handle the empty list, `[]`

,
and one to handle a list with exactly one item in it.

Another type of more complicated case might have more than two
recursive rules, because there are three (or more) ways to proceed
depending on what the next item is. For example, you might want
to ignore non-numbers in the list, do something with positive numbers
and zero,
but do something different with negative numbers. You could do this
with three recursive rules, which would use the three conditions

`not(number(First)),`

`number(First), First >= 0,`

`number(First), First < 0,`

respectively.

Yet another variant, see Schema 4 below, is where a list is being transformed into a new list, with members of the old list being transformed in different ways depending on whether they satisfy some condition.

% First the base case - work out what should happen to the % empty list, and replaceResultForEmptyListwith the % value that your code should produce for the empty list, often []. listSchema([],ResultForEmptyList). % Second, the recursive case for when the item satisfies the % condition. If the list isnotempty, then it has a % first element, which is followed by the rest of the list: listSchema([First | Rest], [NewFirst | RestResult]) :-goal to test for condition, listSchema(Rest, RestResult),computeNewFirstgivenFirst, case where condition holds. % Third and last, the recursive case for when the item does % not satisfy the condition. As usual, if the list isnot% empty, then it has a first element, which is followed by the % rest of the list: listSchema([First | Rest], [NewFirst | RestResult]) :-goal to test that condition is, listSchema(Rest, RestResult),notsatisfiedcomputeNewFirstgivenFirst, case where condition does not hold.

For example, suppose you want to take a list of numbers and
bind Result to the list obtained by squaring the non-negative numbers
and adding 1 to the negative numbers in the list. In the first rule,
`ResultfForEmptyList`

would be `[]`

. In the second
rule, the condition would be `First >= 0`

, and to compute
`NewFirst`

we would use
`NewFirst is First * First`

. In the third rule, the condition
would be `First < 0`

and to compute
`NewFirst`

we would use `NewFirst is First + 1`

.

So the final code in
this case (renamed as `squareOrAdd1List`

) would be

% squareOrAdd1List(List, NewList) binds NewList to a % list consisting of the squares of the non-negative numbers, % and the successors of the negative numbers, in List. squareOrAdd1List([], []). squareOrAdd1List([First | Rest], [NewFirst | RestResult]) :- First >= 0, squareOrAdd1List(Rest, RestResult), NewFirst is First * First. squareOrAdd1List([First | Rest], [NewFirst | RestResult]) :- First < 0, squareOrAdd1List(Rest, RestResult), NewFirst is First + 1.

Other variants on this include where you ignore elements if they don't satisfy the condition - e.g. to copy numbers and ignore non-numbers:

% squareOrIgnore(List, NewList) binds NewList to the result of copying % numbers in List and ignoring non-numbers. squareOrIgnore([], []). squareOrIgnore([First | Rest], [First | NewRest]) :- number(First), squareOrIgnore([Rest, NewRest]. squareOrIgnore([First | Rest], NewRest) :- not(number(First)), squareOrIgnore(Rest, NewRest).

Plenty of other schemata are possible.

See also negation for why it might be preferable
to use \+ rather than `not`

.

See also efficiency for why it is important
to do the test for

or the test for
*condition**not(condition)*__before__ making the recursive
call.