gistfile1.txt

datatype ('a, 'b) t2
  = E2
  | Nd2 of 'a * ('a, 'b) t3 * ('a, 'b) t3
and ('a, 'b) t3
  = E3
  | Nd3 of 'b * ('a, 'b) t2 * ('a, 'b) t2 * ('a, 'b) t2

(* Collect all the items from a t2/t3 tree into a
 * pair of lists. All items must appear in those lists,
 * and items that appear n times in the tree must appear
 * n times in the lists as well. The order of the items in
 * the lists in the result doesn't matter.
 *)

fun collect2 (Nd2 (a, t, t')) = let
	val (lsubA, lsubB) = collect3(t)
	val (rsubA, rsubB) = collect3(t')
in
	(List.concat([[a], lsubA, rsubA]), List.concat([lsubB, rsubB]))
end
  | collect2 (E2) = (nil, nil)

and collect3 (Nd3 (b, t, t', t'')) = let
	val (subA, subB) = collect2(t)
	val (rsubA, rsubB) = collect2(t')
	val (lsubA, lsubB) = collect2(t'')
in
	(List.concat([subA, rsubA, lsubA]),
	 List.concat([[b], subB, rsubB, lsubB]))
end
  | collect3 (E3) = (nil, nil)