Solutions for Session 7

Trees

lin(nil,[]).
lin(t(Left,Root,Right),Res):-
	lin(Left,L),
	lin(Right,R),
	conc(L,[Root|R],Res).

In a 'normal' tree every leaf is nil. In an open tree, every leaf is either nil or an uninstantiated variable. To close an open tree, we have to replace all instantiated variables by in the leaves with nil.
```
close(nil). % leaf
close(t(Left,_,Right)):- % non-leaf
	close(Left),
	close(Right).
```
The first clause will be used for leaves, the second (recursive) clause will be used for non-leaves. This is how the first clause works: for a leaf containing nil, it will simply succeed; for a leaf containing an uninstantiated variable, it will instantiate this variable with nil and succeed.

Efficiently searching sorted lists

In the solutions we use the predicate gt/2 for the greater than relation: gt(X,Y):- X > Y.

```
occur(X,[X|_]).
occur(X,[H|T]):-
	gt(X,H), % if X>H continue searching, else stop searching
	occur(X,T).
```
This is more efficient because we do not always search the complete list for items that do not occur in the list. In SWI prolog you can use time/1 to check the number of inferences and cpu-time it requires to solve a query (use ?- time(Query). with Query your query).
```
occurthree(X,[_,_,X|_]).

occurthree(X,[_,_,H|Tail]):-
	gt(X,H), occurthree(X,Tail).
	
occurthree(X,[X|_]).	

occurthree(X,[_,X|_]).
```
The third clause corresponds to looking back at the first element, when the search element was not found by looking at the third, sixth, ... . Similarly the fourth clause corresponds to looking bakc at the second element. In addition, the third clause is needed when the list in the original call has only one element (e.g. ?- occurthree(1,[1]).) and the fourth clause is needed when the list in the original call has two elements (e.g. ?- occurthree(2,[1,2]).).

Binary dictionaries

count(nil, 0).
count(t(Left,_,Right),Res):-
	count(Left,Lc),
	count(Right,Rc),
	Res is Lc + Rc + 1 .

A naive (inefficient) version is as follows:

sorted(nil).
sorted(t(Left,Nr,Right)):-
	smaller(Left,Nr), sorted(Left),
	larger(Right,Nr), sorted(Right).
	
smaller(nil,_).
smaller(t(Left,Node,Right),Nr):-
	gt(Nr,Node),
	smaller(Left,Nr),
	smaller(Right,Nr).
	
larger(nil,_).
larger(t(Left,Node,Right),Nr):-
	gt(Node,Nr),
	larger(Left,Nr),
	larger(Right,Nr).

A more efficient version is the following:

sorted_2(nil).
sorted_2(t(Left,Nr,Right)):-
	smaller_and_sorted(Left,Nr),
	larger_and_sorted(Right,Nr).

smaller_and_sorted(Tree,Nr) succeeds if all numbers in Tree are smaller than Nr and Tree is ordered:

smaller_and_sorted(nil,_).
smaller_and_sorted(t(Left,Node,Right),Nr):-
	gt(Nr,Node),
	smaller_and_sorted(Left,Node),
	between_and_sorted(Right,Node,Nr).
	
larger_and_sorted(nil,_).
larger_and_sorted(t(Left,Node,Right),Nr):-
	gt(Node,Nr),
	between_and_sorted(Left,Nr,Node),
	larger_and_sorted(Right,Node).

between_and_sorted(Tree,Low,High) succeeds if all numbers in Tree are greater than Low and smaller than High and Tree is ordered:

between_and_sorted(nil,_,_).
between_and_sorted(t(Left,Nr,Right),Low,High):-
	gt(Nr,Low),
	gt(High,Nr),
	between_and_sorted(Left,Low,Nr),
	between_and_sorted(Right,Nr,High).

As usually, many other variants exist.

Balanced binary dictionaries

balanced(nil).
balanced(t(Left,_,Right)):-
    depth(Left,Dl),
    depth(Right,Dr),
    Dif is Dl - Dr,
    Dif >= -1, Dif =< 1,
    balanced(Left),
    balanced(Right).

depth(nil,0).
depth(t(Left,_,Right),D):-
	depth(Left,Dl),
	depth(Right,Dr),
	max(Dl,Dr,Dtmp),
        D is Dtmp + 1 .
   
max(A,B,A):-gt(A,B),!.
max(_,B,B).

makeOrdered(N, Tree):-
        makeOrdered(1, N, Tree).

makeOrdered(N, N, t(nil, N, nil)).
makeOrdered(Min, Max, nil) :- 
	Min> Max.
makeOrdered(Min, Max, t(Left, Middle, Right)):-
        Min < Max,
        Middle is (Min + Max)//2, % // is integer division
        Max2 is Middle-1,
        Min2 is Middle+1,
        makeOrdered(Min, Max2, Left),
        makeOrdered(Min2, Max, Right).

list_to_balanced([], nil).
list_to_balanced(List, t(L, Middle, R)):-
        length(List, N),
        Half is N // 2,
        split_list(List, Half, List1, Middle, List2),
        list_to_balanced(List1, L),
        list_to_balanced(List2, R).

split_list(List, Half, List1, Middle, List2) with List instantiated with a list, Half instantiated with an integer and List1, Middle and List2 uninstantiated, will split List at the position Half. The result is that Middle will be instantiated to the element at position Half+1, List1 to the list with all elements to the left of position Half+1, and List2 to the list with all elements to the right of position Half+1.

split_list([H|T], 0, [], H, T).
split_list([H|T], SplitPosition, [H|T1], Middle, List):-
        SplitPosition >= 1,
        NewSplitPosition is SplitPosition-1,
        split_list(T, NewSplitPosition, T1, Middle, List).