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

      prime: int -> bool
   

   which, given a positive integer number, returns true is such a number is prime, false otherwise.

   Examples:

      - prime 2;
      val it = true : bool
      - prime 23;
      val it = true : bool
      - prime 35;
      val it = false : bool
      

   Note: the remainder operator in ML is mod. (5 mod 3 = 2, 9 mod 4 = 1 etc.)

2. [Points 10] Define a function

      lengths: 'a list list -> int list
   

   which, given a list of lists, returns the list which contains all the lengths of the lists. Formally:

      lengths [ L1, L2, ... , Lk ] = [ #(L1), #(L2), ... , #(Lk) ]
   

   where #(L) stands for the length of L.

   Examples:

      - lengths [];
      val it = [] : int list
      - lengths [[1,2]];
      val it = [2] : int list
      - lengths [[0],[1,2,3]];
      val it = [1,3] : int list
      - lengths [["a"],[],["b","c","d"]];
      val it = [1,0,3] : int list
      

3. [Points 20] Define a function

      palindrome: ''a list -> bool
   

   which, given a list, returns true if the list is a palindrome, and false otherwise. Remember that a palindrome is a sequence which can be read in the same way from left to right and viceversa.

   Note: ''a represents an equality type, namely a type in which you can test the equality of two elements. You don't need to worry about it: if you define the function palindrome correctly, ML will infer the type ''a list -> bool automatically.

   Examples:

      - palindrome [];
      val it = true : bool
      - palindrome [1];
      val it = true : bool
      - palindrome [2,3];
      val it = false : bool
      - palindrome [2,3,3,2];
      val it = true : bool
      

4. [Points 10] Define a datatype "tertree", whose elements are ternary trees, namely trees in which each node is either a leaf, or has three subtrees. Assume that the base case is the tree containing only one node. We want the datatype to be polymorphic, namely the information of the nodes can be of any type. Use leaf and node as constructors.

   Examples:

     
       T1                  T2                    T3
        
       5                   5                    "a"
                          /|\                   /|\
     leaf(5)             / | \                 / | \
                        6  7  9              "b""c""d"
                       /|\
                      / | \                  node( 
                     1  4  3                    "a",
                                                leaf("b"),
                    node(                       leaf("c"),
                       5,                       leaf("d")
                       node(6,               )
                          leaf(1),
                          leaf(4),
                          leaf(3)
                       ),
                       leaf(7),
                       leaf(9)
                    )
   

   Define a function

      pret: 'a tertree -> 'a list
   

   which does the preorder traversal of the tree, namely it traverses the tree in the following order: for every node, first it visits the node, then the leftmost subtree, then the central subtree, and finally the rightmost subtree. The nodes should be collected in a list.

   Examples. With the trees T1, T2 and T3 defined as above, we should have:

      - pret T1;
      val it = [5] : int list
      - pret T2;
      val it = [5,6,1,4,3,7,9] : int list
      - pret T3;
      val it = ["a","b","c","d"] : char list
   

5. [Points 50] Given the following definition of binary tree on integers:

      datatype bintree = emp | nod of bintree * int * bintree;
   

   Define a function

      search_tree: int list -> bintree
   

   that, given a list L, constructs a balanced search tree (AVL) containing all the data in L. Remember that a search tree is a binary tree characterized by the property that, for every node, the information in the node id greater than all the informations in the left subtree, and smaller than all the informations in the right subtree. Also remember that a binary tree is balanced if, for every node, the heights of the left and right subtrees differ at most for one.

   Examples:

      - search_tree [];
      val it = emp : bintree
      - search_tree [1];
      val it = nod(emp,1,emp) : bintree
      - search_tree [2,1];
      val it = nod(nod(emp,1,emp),2,emp) : bintree
      - search_tree [1,4,2];
      val it = nod(nod(emp,1,emp),2,nod(emp,4,emp)) : bintree
      - Compiler.Control.Print.printDepth := 1000; (* display data structures in more detail *)
      val it = () : unit
      - search_tree [1,3,6,4,7,5,2];
      val it =
        nod
          (nod (nod (emp,1,emp),2,nod (emp,3,emp)),4,
           nod (nod (emp,5,emp),6,nod (emp,7,emp))) : bintree
   

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