Please answer in ML (SML). Do the following problem 1 parts (A), (B), (C) and program (D) below:

A Using the definition of entry in directory.sml, write mutually recursive functions print_entries and print_contents (following the pattern of get_entries and get_contents in the same file) that will print each entry name on a line by itself. Using the sample directory in directory.sml, the output should be:

val print_entries = fn : entry -> unit val print_contents = fn : entry list -> unit d1 f1 d2 f2 d3 f3 f4 d3 f5 val it = ( ) : unit

B What does the following function do? Explain how it works.

fun f _ [] = [] | f g (x::xs) = g x :: f (fn y => g (g y)) xs;

(Hint: Examine the call f (fn x => x+1) [1,1,1,1])

C Following the example of ints ( ) in streamtest.sml, write a function, fib ( ), which creates a stream of all the Fibonacci numbers. Fibonacci numbers are defined as follows:

f0 = 0 f1 = 1 fn = fn-1 + fn-2, where n > 1

Use stream.sml for printStrm to obtain the following output:

- val f = fib ( ); val f = Cons (0,fn) : int stream - printStrm 10 f; 0 1 1 2 3 5 8 13 21 34 val it = ( ) : unit

D Write functions for processing a semimap a combination of a map and a set. A semimap is a polymorphic list of two possible items: (key,value) pairs or singleton keys. The types of the keys and values are independent. You can model this with a key-value pair where the value is an option (SOME or NONE). Keys must be unique (enforce this). The storage order of elements in a semimap is not important. (Note: to have two polymorphic type variables in a data type, put those variables in a tuple: datatype (a,b) semipair = ;.)

Here are the datatype and exception definitions to include in your code:

datatype (''a,'b) semipair = Pair of (''a * 'b option); exception KeyError;

The following functions are required:

pairCount : fn : ('a,'b) semipair list -> int returns the number of actual pairs (not singletons, i.e., where the value is not NONE) in the semimap

singCount : fn : ('a,'b) semipair list -> int returns the number of singleton entries (where the value is NONE) in the semimap

hasKey : fn : (''a,'b) semipair list -> ''a -> bool returns whether a key exists in a semimap

getItem : fn : (''a,'b) semipair list -> ''a -> (''a,'b) semipair returns a semipair holding the pair or singleton containing a given key (raises a KeyError exception if the key is not in the list)

getValue : fn : (''a,'b) semipair list -> ''a -> 'b option (raises a KeyError exception if the key is not in the list)

getKeys : fn : ('a,'b) semipair list -> 'a list returns all the keys in the semimap as a list

getValues : fn : ('a,'b) semipair list -> 'b list returns all the non-NONE values from the pairs in the semimap as a 'b list

insertItem : fn: (''a,'b) semipair list -> (''a,'b) semipair -> (''a,'b) semipair list returns a new semimap with a new pair or singleton inserted, unless the key is already in use (in which case an unchanged copy is returned).

removeItem : fn : (''a,'b) semipair list -> ''a -> (''a,'b) semipair list returns a new semimap with the pair or singleton with a given key removed, unless there was there no such key (in which case an unchanged copy is returned).

All functions with more than one parameter should be curried. A sample execution follows. (Note: I used the data constructor Pair in my definition of semipair). See map.sml in the Code folder for a reminder of how to raise exceptions. The code below shows how to handle them.

(* ML Driver: *)

val stuff = [(Pair (1,SOME "one")), Pair (2,NONE)]; pairCount stuff; singCount stuff; getItem stuff 1; getItem stuff 10 handle KeyError => Pair (0,SOME "error!"); getValue stuff 1; getValue stuff 10 handle KeyError => SOME "error!"; getKeys stuff; getValues stuff; hasKey stuff 1; hasKey stuff 3; pairCount stuff; singCount stuff; val stuff2 = insertItem stuff (Pair (3,SOME "three")); val stuff3 = insertItem stuff (Pair (3,SOME "three")); val stuff4 = removeItem stuff 1;

(* Output: val stuff = [Pair (1,SOME "one"),Pair (2,NONE)] : (int,string) semipair list val it = 1 : int val it = 1 : int val it = Pair (1,SOME "one") : (int,string) semipair val it = Pair (0,SOME "error!") : (int,string) semipair val it = SOME "one" : string option val it = SOME "error!" : string option val it = [2,1] : int list val it = ["one"] : string list val it = true : bool val it = false : bool val stuff2 = [Pair (3,SOME "three"),Pair (1,SOME "one"),Pair (2,NONE)] : (int,string) semipair list val stuff3 = [Pair (3,SOME "three"),Pair (1,SOME "one"),Pair (2,NONE)] : (int,string) semipair list val stuff4 = [Pair (3,SOME "three"),Pair (2,NONE)] : (int,string) semipair list