Creating a Decision Tree in Prolog

What Decision Trees Are

A decision tree is a tree data structure that allows selecting from a list of options, then from more and more options until reaching a terminal node, preventing the need to painstakingly check each whole set of options.

The following algorithm takes a set of options and converts them into a decision tree. Following the algorithm are some examples.

Some Prolog Code

make_mind_reading_tree4(Options0,Options3) :-
sort(Options0,Options1),
string_to_list1(Options1,1,_,[],Options2),
maplist(append,[Options2],[Options2a]),
make_mind_reading_tree4_a(Options2a,Options3).

make_mind_reading_tree4_a(Options2a,Options3) :-
merge_lists_a([1],Options2a,[],
Options3a),
sort(Options3a,Options3),!.

string_to_list1([],N,N,Options,Options) :- !.
string_to_list1(Options1,N1,N2,Options2a,Options2b) :-
Options1=[B|Rest],
string_to_list2(B,B,N1,N3,Options2a,Options2c),
[Options2c]=Options2d,
string_to_list1(Rest,N3,N2,[],Options2e),
Options2d=[[[_,D1,D2]|D3]],
Options2f=[[[1,D1,D2]|D3]],
append(Options2f,Options2e,Options2b).

string_to_list2(B,B1,N1,N2,A1,A2) :-
string_concat(D,"",B),
string_length(D,1),
append(A1,[[N1,D,[-,B1]]],A2),
N2 is N1 + 1,!.
string_to_list2(A,B1,N1,N2,B,C) :-
string_concat(D,E,A),
string_length(D,1),
N3 is N1 + 1,
append(B,[[N1,D,N3]],F),
string_to_list2(E,B1,N3,N2,F,C).

merge_lists_a([],Options1,Options2,Options3) :-
append(Options1,Options2,Options3),!.
merge_lists_a(N1,Options1,Options2,
Options3) :-
N1=[M1|Ms],
% If all As lead to the same letter then merge them
findall(A,(member([M1,A,_N2],Options1)),A1),
sort(A1,A11),
merge_lists_a1(M1,A11,Options1,[],Options31,[],N21),
append(Options2,Options31,Options32),
append(Ms,N21,M21),
sort(M21,M2),
merge_lists_a(M2,Options32,[],Options3).

merge_lists_a1(_,[],Options1,Options2,Options3,N,N) :-
append(Options1,Options2,Options3),!.
merge_lists_a1(N1,A1,Options1,Options2,Options3,NA61,NA7) :-
A1=[A2|A3],
findall([N2,A5,N3],(member([N1,A2,N2],Options1),
member([N2,A5,N3],Options1)),A4),
findall([N1,A2,N2],(member([N1,A2,N2],Options1)),A6),
((merge_lists_a2(A4))->
(%% merge N1 A2 N..., change N... in other states
merge_lists_a3(A6,Options1,Options4),
findall(N2,(member([N1,A2,N2],Options4)),NA6));
(merge_lists_a3(A6,Options1,Options4),
findall(N2,(member([N1,A2,N2],Options4)),NA6)
)),
append(Options2,Options4,Options5),
append(NA61,NA6,NA62),
merge_lists_a1(N1,A3,Options5,[],Options3,NA62,NA7).

merge_lists_a2(A4) :-
A4=[[_N1,A,_N2]|A5],
merge_lists_a22(A,A5).
merge_lists_a22(_A,[]) :- !.
merge_lists_a22(A,A5) :-
A5=[[_N1,A,_N2]|A6],
merge_lists_a22(A,A6).

merge_lists_a3(A6,Options1,Options3) :-
A6=[[N1,A,N2]|A8],
delete(Options1,[N1,A,_],Options1a),
(append(Options1a,[[N1,A,N2]],Options1aa)),
merge_lists_a4(N2,A8,Options1aa,[],Options3).

% delete transition to be merged
merge_lists_a4(N2,[],Options1,Options2,Options3
) :-
append(Options1,Options2,Options3),!.
merge_lists_a4(N2,A8,Options1,Options2,Options3) :-
A8=[[N1,A,N3]|A9],
delete(Options1,[N1,A,N3],Options2aa),
merge_lists_a5(N2,N3,Options2aa,[],Options4,[],Options5),
findall(N4,(member([N4,,_],Options4)),N41),
subtract1(Options5,N41,[],Options45),
append(Options2,Options45,Options245),
merge_lists_a4(N2,A9,Options245,[],
Options31),
append(Options31,Options4,Options3).

% point second in pair to changed first state
merge_lists_a5(_N2,_N3,[],Options1,Options1,Options2,Options2) :- !.
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
Options1=[[N3,A,N4]|A9],
delete(Options2,[N3,A,N4],Options2aa),
append(Options2aa,[[N2,A,N4]],Options2a),
merge_lists_a5(N2,N3,A9,Options2a,Options4,Options5,Options6).
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
Options1=[[N2,A,N4]|A9],
delete(Options2,[N3,A,N4],Options2aa),
append(Options2aa,[[N2,A,N4]],Options2a),
merge_lists_a5(N2,N3,A9,Options2a,Options4,Options5,Options6).
merge_lists_a5(N2,N3,Options1,Options2,Options4,Options5,Options6) :-
Options1=[[N31,A,N4]|A9],
not(N2=N31),
append(Options5,[[N31,A,N4]],Options5a),
merge_lists_a5(N2,N3,A9,Options2,Options4,Options5a,Options6).

subtract1([],N41,Options45,Options45) :- !.
subtract1(Options5,N41,Options451,Options45) :-
Options5=[[N42,,_]|Options51],
member(N42,N41),
subtract1(Options51,N41,Options451,Options45).
subtract1(Options5,N41,Options451,Options45) :-
Options5=[[N42,A,B]|Options51],
not(member(N42,N41)),
append(Options451,[[N42,A,B]],Options452),
subtract1(Options51,N41,Options452,Options45).

Examples

1. make_mind_reading_tree4(["abc","abd"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"b",3],[3,"c",[-,"abc"]],[1,"a",5],[5,"b",6],[6,"d",[-,"abd"]]]

DT2=[[1,"a",2],[2,"b",3],[3,"c",[-,"abc"]],[3,"d",[-,"abd"]]]

This is self-explanatory.

1. make_mind_reading_tree4(["aaa","aab","acc"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"a",3],[3,"a",[-,"aaa"]],[1,"a",5],[5,"a",6],[6,"b",[-,"aab"]],[1,"a",8],[8,"c",9],[9,"c",[-,"acc"]]]

DT2=[[1,"a",2],[2,"a",3],[2,"c",9],[3,"a",[-,"aaa"]],[3,"b",[-,"aab"]],[9,"c",[-,"acc"]]]

1. make_mind_reading_tree4(["cca","ccb"],DT2).

(Intermediate) DT1=[[1,"c",2],[2,"c",3],[3,"a",[-,"cca"]],[1,"c",5],[5,"c",6],[6,"b",[-,"ccb"]]]

DT2=[[1,"c",2],[2,"c",3],[3,"a",[-,"cca"]],[3,"b",[-,"ccb"]]]

1. make_mind_reading_tree4(["acc","bcc"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"c",3],[3,"c",[-,"acc"]],[1,"b",5],[5,"c",6],[6,"c",[-,"bcc"]]]

DT2=[[1,"a",2],[1,"b",5],[2,"c",3],[3,"c",[-,"acc"]],[5,"c",6],[6,"c",[-,"bcc"]]]

The c's stay separate here, although can't be merged because the terminal strings are different.

1. make_mind_reading_tree4(["ac","bc"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"c",[-,"ac"]],[1,"b",4],[4,"c",[-,"bc"]]]

DT2=[[1,"a",2],[1,"b",4],[2,"c",[-,"ac"]],[4,"c",[-,"bc"]]]

1. make_mind_reading_tree4(["aqa","awx","awy"],DT2).

(Intermediate) DT1=[[1,"a",2],[2,"q",3],[3,"a",[-,"aqa"]],[1,"a",5],[5,"w",6],[6,"x",[-,"awx"]],[1,"a",8],[8,"w",9],[9,"y",[-,"awy"]]]

DT2=[[1,"a",2],[2,"q",3],[2,"w",9],[3,"a",[-,"aqa"]],[9,"x",[-,"awx"]],[9,"y",[-,"awy"]]]

1. make_mind_reading_tree4(["ca","cb"],DT2).

(Intermediate) DT1=[[1,"c",2],[2,"a",[-,"ca"]],[1,"c",4],[4,"b",[-,"cb"]]]

DT2=[[1,"c",2],[2,"a",[-,"ca"]],[2,"b",[-,"cb"]]]

You can read more about how this algorithm is used by my Mind Reader repository on GitHub in my Essay Helper repository and my Music Composer repository.

Cover image by Svilen Milev (svilen001-32617, FreeImages).