Assignment 4

1. Convert the following function definitions into tail-recursive ones.

   •     let rec log2 n = 
            if n=1 then 0 else 1+log2 ((n+1)/2)
     

   •     let rec min lst =
             match lst with
             | h::[] -> h
             | h::t ->
                 let min1 = min t
                 if h<min1 then h else min1
     

2. Define in F# the following functions on lists.
   • min_max lst: Return a pair (min, max) where min is the minimum element and max is the maximum element of the list lst.
   • insert_sort lst: Return a sorted list of lst, using the insertion sort algorithm.
   • merge_sort lst: Return a sorted list of lst, using the merge sort algorithm.
   
   
3. Assume a set is represented as a list without duplicates. Define the following functions on sets:
   • contains(X,S): X is a member of S.
   • proper_subset(S1,S2): S1 is a proper subset of S2.
   • disjoint(S1,S2): S1 and S2 are disjoint.
   • union(S1,S2): the union of S1 and S2.
   • intersection(S1,S2): the intersection of S1 and S2.
   • difference(S1,S2): the difference of S1 and S2.
4. Write a function that returns a list of all permutations of a given list. For example, given the list [1;2;3], it should return

       [[1;2;3];[1;3;2];[2;1;3];[2;3;1];[3;1;2];[3;2;1]]
   

   The permutations may be in a different order.
   
5. Define in F# the following functions on BinaryTree defined as follows:

        type BinaryTree = 
             | Void
             | Node of int*BinaryTree*BinaryTree
   

   A binary tree is either Void (empty tree) or Node(value,left,right), where value is the value stored in the node, left is the left subtree, and right is the right subtree.
   • (count tree): Return the number of nodes in tree.
   • (in_order tree): Return the in-order traversal of tree as a list.
   • (leaves tree): Return the leaves in the tree from left to right as a list.