Format of the solution

Please make sure that your source code can be compiled and executed under Standard ML on Unix. For a brief explanation on how to run SML and how to load and execute programs, see http://www.cse.psu.edu/~catuscia/teaching/sml/sml.html

1. [Points 10] Define a function

      ordered: int list -> boolean
   

   which, given a list of integers, returns true if the list is ordered or if it is empty, false otherwise.

   Examples of results:

   - ordered [];
   val it = true : bool
   - ordered [1];
   val it = true : bool
   - ordered [2,4,5];
   val it = true : bool
   - ordered [2,4,4];
   val it = true : bool
   - ordered [2,4,3];
   val it = false : bool
   

2. [Points 30] Define a function

      sublist: ''a list * ''a list -> boolean
   

   which, given two list of the same type, returns true if the first list is a sublist of the second, false otherwise. Remeber that L1 is a sublist of L2 if and only if the the elements in L1 occur as a contiguous sequence of elements in L2, in any position of L2.

   Examples of results:

   - sublist([],[1,2]);
   val it = true : bool
   - sublist([1],[1,2]);
   val it = true : bool
   - sublist([2,0],[1,2,0]);
   val it = true : bool
   - sublist([2,0],[1,2,0,5,6]);
   val it = true : bool
   - sublist([2,0],[2,1,0]);
   val it = false: bool
   - sublist([2,0],[2,1,2,0]);
   val it = true : bool
   - sublist([2,0],[1,2]);
   val it = false : bool
   - sublist(["b"],["a","b","c"]);
   val it = true : bool
   - sublist(["b"],[]);
   val it = false : bool
   

   For the following two exercises, assume given the following definition of polymorphic binary tree:

      datatype 'a btree = emptybt | consbt of 'a * 'a btree * 'a btree;
   

3. [Points 20] Define a function

      fringe: 'a btree -> 'a list
   

   which, given a binary tree T, returns the fringe of T, namely the sequence (list), from left to right, of all (the data in) the leaves of T. Remember that a leaf is a node in which both the left and the right subtrees are empty.

   Examples of results:

   - fringe(emptybt: int btree);
   val it = [] : int list
   - fringe(consbt("a",emptybt,emptybt));
   val it = ["a"] : string list
   - fringe(consbt(1,  consbt(2,emptybt,emptybt) , consbt(3,emptybt,emptybt) ));      
   val it = [2,3] : int list
   - fringe(consbt(1,  consbt(2,emptybt,emptybt) ,           
   =                   consbt(3, consbt(4,emptybt,emptybt) , emptybt) ) );
   val it = [2,4] : int list
   

4. [Points 40] Define a function

      balanced_tree: 'a list -> 'a btree
   

   that, given a list L, constructs a balanced binary tree containing all the data in L. Remember that a binary tree is balanced if every node has two non-empty subtrees except the nodes of the last and last-but-one levels.

   Examples of results:

   - balanced_tree ([]: int list);
   val it = emptybt : int btree
   - balanced_tree [1];
   val it = consbt (1,emptybt,emptybt) : int btree
   - balanced_tree [1,2];
   val it = consbt (2,consbt (1,emptybt,emptybt),emptybt) : int btree
   - balanced_tree ["a","b","c"];
   val it = consbt ("b",consbt ("a",emptybt,emptybt),consbt ("c",emptybt,emptybt))
     : string btree
   - balanced_tree [2,3,1,4];
   val it = consbt (1,consbt (3,consbt #,emptybt),consbt (4,emptybt,emptybt))
     : int btree
   - Compiler.Control.Print.printDepth := 1000; 
   val it = () : unit
   - balanced_tree [2,3,1,4];
   val it =
     consbt
       (1,consbt (3,consbt (2,emptybt,emptybt),emptybt),
        consbt (4,emptybt,emptybt)) : int btree
   - balanced_tree [1,2,3,4,5,6,7];
   val it =
     consbt
       (4,consbt (2,consbt (1,emptybt,emptybt),consbt (3,emptybt,emptybt)),
        consbt (6,consbt (5,emptybt,emptybt),consbt (7,emptybt,emptybt)))
     : int btree
   

Note: In each of the above exercises, you can define auxiliary functions if you want.