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 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.

The order of the keys is not important. You are welcome to use functions in the List structure for this part.

(* 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 stuff2 (Pair (3,SOME "three"));
val stuff4 = removeItem stuff3 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 = [1,2] : int list
val it = ["one"] : string list
val it = true : bool
val it = false : bool
val it = 1 : int
val it = 1 : int
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
*)
*In ML (SML) programming language.