/*  The CUT - and how to learn to live with it  */


/*  C & M II page 81
    (nb - the version published is wrong.)  */

sum_to(1,1) :- !.
sum_to(N,Result) :-
            N1 is N-1,
            sum_to(N1,Result1),
            Result is Result1+N.

?-sum_to(4,X).

/* In this program the cut is needed only if sum_to is itself called as
a sub-goal by another predicate.  The idea is that if some later goal fails,
and the sum_to goal is retried, funny things might happen.  */

/*  A better version of the same thing  */

sum_to(N,1) :- N =< 1, !.
sum_to(N,Result) :-
            N1 is N-1,
            sum_to(N1,Result1),
            Result is Result1 + N.



/*  Here are versions of these two predicates using 'not' instead of
    the cut.    */

/*  (1) */

sum_to(1,1).
sum_to(N,Result) :-
            not(N=1),
            N1 is N-1,
            sum_to(N1,Result1),
            Result is N1 + Result1.

/*  (2) */

sum_to(N,1) :-  N =< 1.
sum_to(N,Result) :-
            not(N=<1),
            N1 is N - 1,
            sum_to(N1,Result1),
            Result is N1 + Result1.

/*  In the case of each of these versions, it is easier to see the
    logic of the definition, but there may be some loss of efficiency,
    as the system will have to attempt to make a goal g succeed in order
    to test the goal not(g).  This will get worse as g gets more complicated.
*/


/*  The definition of 'not' in terms of the cut.    */

not(G) :- call(G), !, fail.
not(G).



/*  Cut-fail illustrated:  a naive way of defining non-prime numbers. */

non_prime(X) :- X < 4, !, fail.
non_prime(X) :- N is X/2, integer(N).
non_prime(X) :- N is X/3, integer(N).

?-non_prime(4).


/*  Using the cut as way of accelerating rejections .
(Cf. 'taxpayer example, C&M II pp 85 ff.
*/


worth_reading(Rag):-
    owns(Rag,murdoch),
    !, fail.
worth_reading(Rag):-
    cartoonist(Rag,jak),
    !,
    write(Rag),write(' -  no **** way!'),nl,
    fail.
worth_reading(Rag) :-
    cartoonist(Rag,posy_simmonds).
worth_reading(Rag) :-
    coverage(cricket,Rag,pages(N)),
    N > 3.
worth_reading(Rag) :-
    tv_critic(Rag,clive_james).
worth_reading(Rag) :-
    political_columnist(Rag,hugo_young).

owns(times,murdoch).
owns(sun,murdoch).
owns(sunday_times,murdoch).
owns(mirror,maxwell).

cartoonist(evening_standard,jak).
cartoonist(guardian,posy_simmonds).
coverage(cricket,guardian,pages(1)).
coverage(cricket,observer,pages(4)).
political_columnist(observer,conor_cruise_o_brien).
political_columnist(sunday_times,hugo_young).


?-worth_reading(daily_mail).

?-worth_reading(times).

?-worth_reading(evening_standard).

?-worth_reading(observer).

?-worth_reading(X).

/*  This unspecific goal fails, because of the presence of the cut-fail
    combination in the first clause for worth_reading.
    This seems to be a case where the cut can be a liability, as compared
    with the use of not.

*/

/*  findall - a predicate for repeatedly satisfying a goal, and putting
    successful values into a list
*/

on(block1,table).
on(block2,block1).
on(block3,table).
on(block4,block3).
on(block5,block4).
on(block6,block5).
on(block7,block2).


supported_by(B,B1) :-
    on(B,B1).
supported_by(B,B1) :-
    on(B,Inter),
    supported_by(Inter,B1).

?-supported_by(block6,X).
?-supported_by(block6,X),write(X),nl,fail.

/*  This is one way of getting a list of all the values satisfying a given
    goal - but it's obviously not very satisfactory.

    The following program is discussed in C & M II, pp 162 ff.
*/

findall(X,G,_) :-
    asserta(found(mark)),
    call(G),
    asserta(found(X)),
    fail.
findall(_,_,L) :-
    collect_found([],M),
    !,
    L = M.

collect_found(S,L) :-
    getnext(X),
    !,
    collect_found([X|S],L).
collect_found(L,L).

getnext(X) :-
    retract(found(X)),
    !,
    X \== mark.



/*  Findall(X,G,L)  will find all items X satisfying a certain goal G, and
    will put them all into a list L.
*/

member(X,[X|_]).
member(X,[_|T]) :-
    member(X,T).

?-findall(X, supported_by(block6,X), List).

?-findall
    (X,
    (member(X, [2,4,8,10,12,14,12,10,2,6,4,8,6,4,3,2]), X < 10),
    List ).


/*

Exercises.

1.  Write some further extensions to the newspaper choosing program,
using the cut-fail combination to eliminate alternatives.

Can you think of any way round the problem that the open-ended query

    ?- worth_reading(X).

will immediately fail, as so defined?

2.  Using the bicycle-parts example, at the end of Chapter 3 of Clocksin
and Mellish, apply it to a classification tree for daily, weekly and Sunday
newspapers, so that the terminals of the tree are the actual newspapers, and
the nodes of the tree are labelled appropriately.

3.  Apply the findall program to this.

4.  Find a way of amending the findall predicate so that it never
includes duplicates in any list of answers it outputs.  If possible, make sure
that the list comes out in the appropriate order.

5.  A bag is a list which may contain duplicates (e.g. [a,b,c,b,a]).
A set is a list which contains no duplicate members (e.g. [a,b,c]).
Write a program which converts a bag into a list.
Modify the program so that it counts the number of occurrences of each item in
the bag (so converting, e.g., [a,b,c,b,a] to [a,2,b,2,c,1] ).

6.  Using as many features of Prolog as you already know about, write a
program which offers you a good food guide or good pub guide to the Brighton
area.  (Use the Yellow Pages as a reference if necessary.)




*/