% Computational Intelligence: a logical approach. 
% Prolog Code.
% Decision-tree learner
%    binary attributes, , full search for smallest tree, no noise.
% Copyright (c) 1998, Poole, Mackworth, Goebel and Oxford University Press.

% dtlearn(Goal, Examples, Attributes, DT)
%    Given Examples and Attributes induces a decision tree DT for Goal.
%    non-myopic - does full search for smallest tree, for binary attributes 
%    Does not handle noisy data

dtlearn(Goal, Examples, Attributes, DT) :-
   length(Attributes,NAtts),
   power(2,NAtts,MaxTree),
   int(N,MaxTree),
   dtlearn(Goal, Examples, Attributes, DT,N,0).

dtlearn(Goal, Examples, _ , Val,N,N) :-
   all_examples_agree(Goal, Examples, Val).


dtlearn(Goal, Examples, Atts, if(Cond=YesVal,YT,NT),N0,N3) :-
   N0>0,
   \+ all_examples_agree(Goal, Examples, _),
   select_split(Goal, Examples, Atts, Cond, Rem_Atts),
   split(Examples, Cond,YesVal, Yes, No),
   N1 is N0-1,
   dtlearn(Goal, Yes, Rem_Atts, YT,N1,N2),
   dtlearn(Goal, No, Rem_Atts, NT,N2,N3).

% all_examples_agree(Goal, Examples, Val) is true if all examples agree that
%      Val is the value of attribute Goal.
all_examples_agree(_,[],_).
all_examples_agree(Att,[Obj|Rest],Val) :-
   val(Obj,Att,Val),
   all_examples_agree(Att,Rest,Val).


% split(Examples,Att,YesVal,T,F) is true if T is
% the examples in Examples with attribute Att
% having value YesVal and F is the examples with
% attribute Att having the other value.
split([],_,_,[],[]).
split([Obj|Rest],Cond,YesVal,[Obj|Yes],No) :-
   val(Obj,Cond,YesVal),
   split(Rest,Cond,YesVal,	Yes,No).
split([Obj|Rest],Cond,YesVal,Yes,[Obj|No]) :-
   val(Obj,Cond,NoVal),
   \+ NoVal = YesVal,
   split(Rest,Cond,YesVal,Yes,No).


% select_split(Goal, Examples, Atts, Cond, Rem_Atts)
% is true if Cond is an attribute in Atts to split on
select_split(_, _, Atts, Cond, Rem_Atts) :-
   remove(Cond,Atts,Rem_Atts).
select_split(_, Examples, [], _, _) :-
   writeln(['The examples ',Examples,' cannot be split.']),
   fail.

% remove(E,L,R) removes one occurrence of element E from list L resulting in R
remove(A,[A|R],R).
remove(A,[B|C],[B|R]) :-
   remove(A,C,R).

% int(N,M) is true if N is an integer in the range 0 =< N < M
% This enumerates the integers in order.

int(0,M) :- M>0.
int(N,M) :-
   M>0,
   M1 is M-1,
   int(N1,M1),
   N is N1+1.

% power(X,N,P) is true if P=X^N
power(_,0,1).
power(X,N,PX) :-
   1 is N mod 2,
   N1 is N-1,
   power(X,N1,P),
   PX is P*X.
power(X,N,XN) :-
   0 is N mod 2,
   N>0,
   XX is X*X,
   N2 is N // 2,
   power(XX,N2,XN).

writeln([]) :- nl.
writeln([H|T]) :-
   write(H),
   writeln(T).