let rec length = function
  | [] -> 0
  | head :: tail -> 1 + length tail;;

let rec (@) xs ys = 
  match xs with
    | [] -> ys
    | x :: xs ->
	let newlist = xs @ ys in
	  x :: newlist;;

let rec (@) xs ys = 
  match xs with
    | [] -> ys
    | x :: xs -> x :: (xs @ ys);;

let rec (@) xs ys = 
  match ys with
    | [] -> xs
    | y :: ys -> (xs @ [y]) @ ys;;

let sum nums =
  List.fold_left (+) 0 nums;;

type 'a tree = Empty | Node of 'a tree * 'a * 'a tree;;

let rec preorder tr  =
    match tr with
    | Empty -> []
    | Node(l,x,r) -> x :: ((preorder l ) @ (preorder r ));;

let rec postorder tr  =
    match tr with
    | Empty -> []
    | Node(l,x,r) -> (postorder l ) @ (postorder r ) @ [x];;

type expr =
  | Const of int
  | Add of expr * expr
  | Mul of expr * expr;;

let rec eval = function
  | Const n -> n
  | Add (e1, e2) -> eval e1 + eval e2
  | Mul (e1, e2) -> eval e1 * eval e2;;