(b) Type Type / | \ / | \ / | \ / | \ Type -> Type Type -> Type / | \ | | / | \ / | \ | | / | \ Type -> Type TVar TVar Type -> Type | | | | | | | | | | | | TVar TVar gamma alpha TVar TVar | | | | | | | | alpha beta beta gamma (b) Type Type / \ / | \ / \ / | \ Type list Type -> Type / | \ | / \ / | \ | / \ Type -> Type TVar Type list | | | | | | | | TVar TVar alpha TVar | | | | | | alpha beta beta
Type ::= A -> Type | A A ::= A list | (Type) | TVar
datatype 'a tree = nod of 'a * 'a tree list;
fun sum_tree (nod (a,L)) = a + aux L and aux (nil) = 0 | aux (T::L) = sum_tree T + aux L;Alternative solution:
fun sum_tree (nod(a,nil)) = a | sum_tree (nod(a,T::L)) = sum_tree T + sum_tree(nod(a,L));Note that in this second solution we use a "clever" trick: we call sum_tree recursively on the tree obtained by pruning the first subtree from the original tree.
Note that this is very different from the following definition:
fun sum_tree (nod(a,nil)) = a | sum_tree (nod(a,L)) = a + sum_tree(L);This latter definition, indeed, will not even pass compilation. L is a list of trees, and as such cannot be the argument of sum_list.
balanced(emp). balanced(nod(T1,X,T2)) :- height(T1,N1), height(T2,N2), diff_within_1(N1,N2), balanced(T1), balanced(T2). height(emp,0). height(nod(T1,X,T2),N) :- height(T1,N1), height(T2,N2), max(N1,N2,M), N is M+1. max(N1,N2,N1) :- N1 >= N2. max(N1,N2,N2) :- N1 < N2. diff_within_1(N1,N2) :- N1 - N2 =< 1, N2 - N1 =< 1.However, this solution is not very efficient because the tree is traversed twice: once for deciding whether it is balanced, and the other time for calculating its height. The two tasks could be performed together. Based on this idea, we present another (more efficient) solution.
balanced(T) :- aux(T,_). aux(emp,0). aux(nod(T1,X,T2),N) :- aux(T1,N1), aux(T2,N2), max_min(N1,N2,M,K), M - K =< 1, N is M+1. max_min(N1,N2,N1,N2) :- N1 >= N2. max_min(N1,N2,N2,N1) :- N2 >= N1.