3. For each of the following pairs of types, say whether they can be unified or not. If they can be unified, list the substitutions for type variables that need to be made to achieve this. You are not allowed to rename apart the occurrences of type variables. Be careful not to create infinite types (for example, 'a and 'a list cannot be unified). E.g., the pairs 'a list * Pb and 'c * (int -> 'c) unify, and this achieved by taking 'c 'a list and 'b int -> 'a list. The pairs 'a -> int and bool -> 'a do not unify. (i) 'a -> 'a and 'a -> int list (ii) 'a -> 'b and 'a -> int list (iii) (int -> int) -> (int -> int) and 'a -> 'a (iv) 'a list -> 'a list and 'b -> 'b (v) 'a list -> 'a and 'b -> 'b (vi) ('a -> 'b) -> 'c and 'd -> 'e list
// The standard node-labelled tree datatype type 'a tree = Lf | Br of 'a * 'a tree * 'a tree // A mutable node-labelled tree datatype type 'a refTree = Rlf | RBr of 'a * 'a refTree ref * 'a refTree ref // Convert a standard tree into a mutable tree // makeRefTree : 'a tree -> 'a refTree ref let rec makeRefTree t = match t with | Lf -> ref RLf | Br (x, i, r) -> ref (RBr (x, makeRefTree 1, makeRefTree r)) // Convert a mutable tree into a standard tree // freeze : 'a refTree ref -> 'a tree let rec freeze tref = match !tref with | RLG -> LE | RBr (x, lref, rref) -> Br (x, freeze lref, freeze rref) // Swap the contents of two references // swap : 'a ref -> 'a ref -> unit let swap r1 r2 = let x = !r1 r1 := !r2; r2 := X // Swap the left and right branches of each node, recursively // mirror : 'a refTree ref -> unit let rec mirror tref = failwith "Not implemented" // Do a single rotation (if possible) Il rotate : 'a refTree ref -> unit let rotate tref = match !tref with | RLf -> 0 RBr (x, lref, rref) -> match !lref with RLf -> ( | RBr (y, llref, lrref) -> failwith "Not implemented
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!