You must provide definitions for a contacts directory $($mirroring the video rental database type presented in class$)$ such that "rows" are list of $3-$tuples with the first element being a last name, the second element an email address, and the third element a Metaphone code.

Each "column" will be a string, and the snippet below can be used as a starting point:

type $...=[$Char$]$

type $...=[$Char$]$

type $...=[$Char$]$

type Row $=(...,...,...)$

type Database $=[$Row$]$

$$ You must create a function named "returnSampleData" that takes no arguments and, when called, returns a sample database of $2-$tuples $($i$.$e$.,[([$Char$],[$Char$])]$ with at least $10$ entries $($including yourself$)$ that contain both a last name and an email address; The type definition for this function is provided below:

returnSampleData :: $[([$Char$],[$Char$])]$

$$ You must create a function that will transform an argument list of $2-$tuples of strings into a return database of $3-$tuples, by calling your metaphone code generating function $($described below$)$ on each row. It should thus transform the return value of your returnSampleData function above into an instance of the Database type mentioned on the previous page. This function must use a list comprehension to achieve this conversion. The type definition for

this function is provided below:

convertDatabase :: $[([$Char$],[$Char$])]->$ Database

$$ You must design and implement a series of functions that will be called in sequence $($by another function you will write$)$ to generate a simplified Metaphone code according to therules provided on the following page. Please note that these rules represent a simplified

variation on the Metaphone code $($and not the actual Metaphone code published described in

"Hanging on the Metaphone", Lawrence Philips. Computer Language, Vol. $7,$ No$.12,1990).$

Please note that there are several constraints on these rules that absolutely must

be observed, so read this specification very carefully and thoroughly.

$$ Finally, you must include a single "query" function $($implemented using a list comprehension$)$ that, when called with a database of $3-$tuples $($as the first argument$)$ and a string "search target" $($as the second argument$),$ returns all of the records in the database associated with a Metaphone code that matches the Metaphone code that would be generated for the second argument.

Listed below are the Metaphone transformation "rules" that you must implement. Please note the following constraints that must be observed:

No indexing operators are permitted, not even ones you write yourself.

No length function is permitted, not even one you write yourself.

Only the provided selector functions head', tail', last', and init' are permitted$2.$

No concatenation $(\text{'}++\text{'})$ is permitted, so you must use the list construct:or $(\text{'}$:$\text{'})$ instead Every function must be recursive EXCEPT for the implementations of Rules $2$ and $3$

No recursive helper functions are permitted EXCEPT for the implementation of Rule $16$

Rule Description:

$1.$ Remove all adjacent duplicate letters except the letter $\text{'}$C$\text{'}.$

$2.$ If the argument begins with $\text{'}$KN$\text{'},\text{'}$GN$\text{'},\text{'}$PN$\text{'},\text{'}$AE$\text{'},$ or $\text{'}$WR$\text{'},$ then drop the first letter.

$($n$.$b$.,$ This function will not be recursive.$)$

$3.$ If the argument ends with an $\text{'}$MB$\text{'},$ the drop the last letter $($i$.$e$.,$ drop the $\text{'}$B$\text{'}).$

$($n$.$b$.,$ This function will not be recursive.$)$

$4.$ If an instance of $\text{'}$C$\text{'}$ is followed by $\text{'}$IA$\text{'}$ or $\text{'}$H$\text{'},$ then it must be changed to an $\text{'}$X$\text{'},$ but if an instance of $\text{'}$C$\text{'}$ is followed by $\text{'}$I$\text{'},\text{'}$E$\text{'},$ or $\text{'}$Y$\text{'},$ then it must be changed to an $\text{'}$S$\text{'}.$ Every other instance of the letter $\text{'}$C$\text{'}$ must be changed into $\text{'}$K$\text{'}.$

$5.$If an instance of $\text{'}$D$\text{'}$ is followed by $\text{'}$GE$\text{'},\text{'}$GY$\text{'},$ or $\text{'}$GI$\text{'},$ then it must be changed to a $\text{'}$J$\text{'}.$ Every other instance of the letter $\text{'}$D$\text{'}$ must be changed into $\text{'}$T$\text{'}.$

$6.$ If an instance of $\text{'}$G$\text{'}$ is followed by an $\text{'}$H$\text{'}$ or an $\text{'}$N$\text{'},$ then it must be removed, but if an instance of $\text{'}$G$\text{'}$ is followed by $\text{'}$I$\text{'},\text{'}$E$\text{'},$ or $\text{'}$Y$\text{'},$ then it must be changed to a $\text{'}$J$\text{'}.$ Every other instance of the letter $\text{'}$G$\text{'}$ must be changed into $\text{'}$K$\text{'}.$

$7.$ Remove every instance of $\text{'}$H$\text{'}$ that appears after a vowel but not before a vowel.

$8.$ Transform every instance of $\text{'}$CK$\text{'}$ into an instance of $\text{'}$K$\text{'}.$

$($n$.$b$.,$ This function has been provided for you as an example, on the following page.$)$

$9.$ Transform every instance of $\text{'}$PH$\text{'}$ into an instance of $\text{'}$F$\text{'}.$

$10.$Transform every instance of $\text{'}$Q$\text{'}$ into an instance of $\text{'}$K$\text{'}.$

$11.$ If an instance of $\text{'}$S$\text{'}$ is followed by $\text{'}$H$\text{'},\text{'}$IA$\text{'},$ or $\text{'}$IO$\text{'},$ then it must be changed to an $\text{'}$X$\text{'}.$

$12.$ If an instance of $\text{'}$T$\text{'}$ is followed by $\text{'}$IA$\text{'}$ or $\text{'}$IO$\text{'},$ then it must be changed to an $\text{'}$X$\text{'}.$

$13.$ Transform every instance of $\text{'}$V$\text{'}$ into an instance of $\text{'}$F$\text{'}.$

$14.$ Transform every instance of $\text{'}$X$\text{'}$ into the sequence $\text{'}$KS$\text{'}.$

$15.$Transform every instance of $\text{'}$Z$\text{'}$ into an instance of $\text{'}$S$\text{'}.$

$16.$ Remove every instance of a vowel or $\text{'}$Y$\text{'}$ unless it appears at the very beginning.

$($n$.$b$.,$ This function will require a recursive "helper function", so that the replacement is considered for every character except the first character.