%%% Some Prolog solutions for DM509 exam winter 2009 %%%


%% 2a:

height(leaf(_),0).
height(node(Left,Right),H) :- height(Left,HL),height(Right,HR),H is 1 + max(HL,HR).

%% 2b:

% simple version
flatten_plain(leaf(X),[X]).
flatten_plain(node(Left,Right),Out) :- flatten_plain(Right,OutR),
                                       flatten_plain(Left,OutL),
                                       append(OutL,OutR,Out).

% more efficient version using an accumulator:

flatten(Tree,List) :- flatten_acc(Tree,[],List).
flatten_acc(leaf(X),Acc,[X|Acc]).
flatten_acc(node(Left,Right),Acc,Out) :- flatten_acc(Right,Acc,OutR),
                                         flatten_acc(Left,OutR,Out).

%% 2c:

sameshape(node(L1,R1),node(L2,R2)) :- sameshape(L1,L2),sameshape(R1,R2).
sameshape(leaf(_),leaf(_)).


% example trees:
tree1(node(node(node(leaf(_),leaf(_)),leaf(_)),node(leaf(_),leaf(_)))).
tree2(node(node(node(leaf(a),leaf(b)),leaf(c)),node(leaf(d),leaf(f)))).
tree3(node(leaf(a),node(node(leaf(b),leaf(c)),leaf(d)))).
tree4(node(leaf(1),node(node(leaf(x),leaf(2)),leaf(y)))).
tree5(node(node(node(leaf(a),leaf(b)),leaf(c)),leaf(d))).


%% 3a:

f(Z,b,Z) :- g(Z).
f(1,Z,1) :- g(Z).
g(a) :- !.
g(b).
g(c).


%% 3c (for testing through cut-n-paste into gprolog):

% q(q(X,Y),q(alice,bob)) , q(Z,Z)
% alice(X,bob(X),X) , alice(bob(Y),Y,bob(Y))
% 2=3 , X=Y
% length([1,2,3]) , 3
% append([1,2],[3,4],Z) , append(X,[3,4],[2,3])