CENG242 -pe4 - Solved

Programming Language Concepts
1             Problem Definition
In this final programming examination for Haskell, you will once again be dealing with two parts. In the first part, you will be performing safe conversion between data types. And in the second part, you will be dealing with a dictionary-style structure implemented as a special tree. They’re both based around a little inverse phone book implementation. Let’s have some fun!

1.1            General Specifications
•    The signatures of the functions, their explanations and specifications are given in the following section. Read them carefully.

•    Make sure that your implementations comply with the function signatures.

•    You may define any number of helper function(s) as you need.

•    You can (and sometimes even should) use previous functions inside your new function definitions. Some exercises are designed to build up!

•    You are not allowed to import any extra modules for this exam. Data.Maybe is imported for your convenience although it’s not necessary. Please stick to the Prelude for the rest!

•    Observe that the exam is out of 120 points. Each function has 4 extra points included!

1.2            Quick VPL Tips (In case you’ve forgotten them!)
•    Evaluation is fast. If evaluation seems to hang for more than a few seconds, your code is entering an infinite loop or has an abnormal algorithmic complexity. Or you’ve lost your connection, which is much less likely!

•    Although the run console does not support keyboard shortcuts, it should still be possible to copy and paste using the right-click menu (Tested on latest versions of Firefox and Chrome).

•    Get familiar with the environment. Press the plus shapes button on the top-left corner to see all the options. You can download/upload files, change your font and theme, switch to fullscreen etc. Useful stuff!

2             Part I - Digit Conversion
To start off with, we will have a phone book consisting of phone numbers as keys and contact names as values. Being careful programmers, we want our phone book to contain only digits as keys and not arbitrary strings. So, to make our program safer on the type level, we define a custom digit data type as a lightweight wrapper around Char for use in our phone book [1]:

 

Observe that we make our data type convertible to a string, comparable and orderable automatically through the use of deriving. Also, we define an alias for lists of Digits:

 

Our goal in this part is performing safe conversions to our new data type. We will be using Haskell’s standard Maybe type for this.

2.1            toDigit (14 points)
Step one: convert a single character to a Digit safely (so, Maybe Digit)! If the given character is a digit (characters between '0' and '9'), it should be converted to a properly wrapped Digit. If the given character is not a digit, the function should evaluate to Nothing.

Here’s the signature and some example runs:

 

2.2            toDigits (29 points)
And now it’s time for the obvious extension: Converting Strings to a list of Digits (also named PhoneNumber) safely. The rules are simple:

•    An empty string is invalid and should evaluate to Nothing.

•    If any of the characters in the given string is not a digit, the string is invalid and once again the function evaluates to Nothing.

•    Essentially, you should return a list of digits only for non-empty strings that contain only digits.

Here’s the signature and some example runs:

 

3             Part II - Querying a Phonebook
Congratulations on safely converting the digits![2] Now it’s time to go ahead with our little phone book implementation which will be based on the following abstract dictionary tree type:

 

The tree is structured in a way that every internal node contains a bunch of choices matching initial parts of the key, with each choice leading to a different subtree. The leaves at the tips contain the actual values in the dictionary. This allows for some fast querying! Also, the parts of the key are kept in sorted order.

An example will make this clearer. First, we define an alias for a concrete type of DigitTree which will be the type of our phone book:

 

The parts of our key are Digits and the values are Strings representing the names in our phone book. Here’s an example phone book containing some very short phone numbers associated with a list of particular names, in no particular order. There’s also an illustration of the corresponding DigitTree.

 

Of course this is all meaningless without the code! So here’s the code corresponding to the tree representing the phone book:

 

This tree will be referred to as exampleTree in the below examples and is also present in your VPL template.

To summarize, each digit is part of our key (the whole phone number) and the path of digits going to a leaf corresponds to the phone number of a person (or entity). Your work is going to be defining a few functions for querying phone books.

Before moving on, here are a few final specific details for the careful:

•    The digits in the internal node list will always be in sorted order.

•    There is no empty tree and the input will never contain any internal nodes with an empty list. Every internal node’s list will have at least one pair.

•    Similarly, there will be no tree composed of a single leaf. That would be a value with an empty key which does not make much sense!

•    The tree cannot contain values at internal nodes. So, our example tree would not be able to have a phone number like 137: Sussman, since 137 corresponds to an internal node.

3.1            numContacts - 14 pts
Count the number of contacts in the given phone book. That’s it. Remember that the input tree will always be valid as per the final definitions given above. Here’s the signature and some example runs (do not forget our exampleTree!):

numContacts :: DigitTree -> Int

*PE4> numContacts (Node [(Digit '2', Leaf "The One and Only")]) 1

*PE4> numContacts $ Node [(Digit '3', Leaf "Mr. Tee"), (Digit '4', Leaf "Ms. Lef")] 2

*PE4> numContacts $ Node [(Digit '1',Node [(Digit '3',Leaf "Luke Unluke")]),(Digit '4',Node [(Digit '2',Leaf "Kozmos Fehmi"),(Digit '5',Leaf "Tim Time")])] 3

*PE4> numContacts exampleTree

7

 *PE4> numContacts $ Node [(Digit '0',Node [(Digit '7',Leaf "Tynetta")]),(Digit '1', Leaf "Jonathan"),(Digit '2',Node [(Digit '0',Node [(Digit '3',Leaf "Diedre")]),(Dig it '2',Node [(Digit '5',Leaf "Vesta")])]),(Digit '5',Node [(Digit '1',Leaf "Ilka")] ),(Digit '6',Node [(Digit '0',Node [(Digit '9',Leaf "Farah")]),(Digit '5',Leaf "Cle mentine")]),(Digit '7',Node [(Digit '7',Leaf "Kenyatta")]),(Digit '8',Node [(Digit '3',Leaf "Athena")]),(Digit '9',Node [(Digit '7',Node [(Digit '8',Leaf "Lyndsie")])

])]

10

3.2            getContacts - 34 pts
Convert the given phone book to a list of pairs, containing all the phone numbers in the phone book along with their associated contact names.

The order of the contacts is important: you should follow the list of each internal node in the given order from start to finish. This means that if you draw the tree, the names of the contacts in the list will correspond to the left-to-right order of the leaves. Remember that the digits in the leaves will always be in sorted order.

As always, the signature and some example runs:

getContacts :: DigitTree -> [(PhoneNumber, String)]

*PE4> getContacts (Node [(Digit '0', Leaf "I, Me & Myself Co.")])

[([Digit '0'],"I, Me & Myself Co.")]

*PE4> getContacts $ Node [(Digit '1', Leaf "Reception"), (Digit '4', Leaf "Emergenc y"), (Digit '5', Leaf "Bar")]

[([Digit '1'],"Reception"),([Digit '4'],"Emergency"),([Digit '5'],"Bar")]

*PE4> getContacts $ Node [(Digit '3', Node [(Digit '2', Leaf "T"), (Digit '7', Node [(Digit '7', Leaf "Z")])])]

[([Digit '3',Digit '2'],"T"),([Digit '3',Digit '7',Digit '7'],"Z")]

*PE4> getContacts exampleTree

[([Digit '1',Digit '3',Digit '7',Digit '8'],"Jones"),([Digit '1',Digit '5'],"Steele

"),([Digit '1',Digit '9',Digit '1'],"Marlow"),([Digit '1',Digit '9',Digit '2',Digit

'3'],"Stewart"),([Digit '3'],"Church"),([Digit '7',Digit '2'],"Curry"),([Digit '7' ,Digit '7'],"Hughes")]

 *PE4> getContacts $ Node [(Digit '1',Node [(Digit '1',Node [(Digit '7',Node [(Digit '8',Leaf "Sassy")])])]),(Digit '2',Node [(Digit '6',Leaf "French Fry"),(Digit '8', Node [(Digit '3',Node [(Digit '1',Leaf "Junior")])])]),(Digit '3',Node [(Digit '9', Leaf "Frogger")]),(Digit '4',Node [(Digit '0',Leaf "Thor")]),(Digit '6',Node [(Digi t '4',Node [(Digit '8',Node [(Digit '5',Leaf "Sunshine")])]),(Digit '5',Leaf "Doll" ),(Digit '8',Node [(Digit '5',Leaf "Tomcat")])]),(Digit '7',Node [(Digit '3',Node [ (Digit '3',Leaf "Pecan")]),(Digit '7',Node [(Digit '7',Node [(Digit '4',Leaf "Lulu"

)])])]),(Digit '8',Node [(Digit '6',Node [(Digit '2',Node [(Digit '5',Leaf "Tank")] )])]),(Digit '9',Leaf "Bud")]

[([Digit '1',Digit '1',Digit '7',Digit '8'],"Sassy"),([Digit '2',Digit '6'],"French

Fry"),([Digit '2',Digit '8',Digit '3',Digit '1'],"Junior"),([Digit '3',Digit '9'], "Frogger"),([Digit '4',Digit '0'],"Thor"),([Digit '6',Digit '4',Digit '8',Digit '5' ],"Sunshine"),([Digit '6',Digit '5'],"Doll"),([Digit '6',Digit '8',Digit '5'],"Tomc at"),([Digit '7',Digit '3',Digit '3'],"Pecan"),([Digit '7',Digit '7',Digit '7',Digi t '4'],"Lulu"),([Digit '8',Digit '6',Digit '2',Digit '5'],"Tank"),([Digit '9'],"Bud ")]

3.3            autocomplete - 29 pts
This time, the goal is to autocomplete a given input with a list of possible suffixes and contact names (a bit like a search bar).

For example, if our phone book contains 212: Bill, 222: Sarah, 213: Tony, then an autocompletion for "21" should result in 2: Bill, 3: Tony. Of course, an empty string should not be autocompleted (like an empty search bar!).

Once again, the signature and some example runs follow. All the examples are given on the exampleTree for extra clarity:

autocomplete :: String -> DigitTree -> [(PhoneNumber, String)]

*PE4> autocomplete "" exampleTree

[]

*PE4> autocomplete "asdfg" exampleTree

[]

*PE4> autocomplete "19" exampleTree

[([Digit '1'],"Marlow"),([Digit '2',Digit '3'],"Stewart")]

*PE4> autocomplete "77" exampleTree

[([],"Hughes")]

*PE4> autocomplete "7" exampleTree

[([Digit '2'],"Curry"),([Digit '7'],"Hughes")]

*PE4> autocomplete "13789" exampleTree

[]

*PE4> autocomplete "1378" exampleTree

[([],"Jones")]

*PE4> autocomplete "137" exampleTree

[([Digit '8'],"Jones")]

*PE4> autocomplete "13" exampleTree

[([Digit '7',Digit '8'],"Jones")]

*PE4> autocomplete "1" exampleTree

 [([Digit '3',Digit '7',Digit '8'],"Jones"),([Digit '5'],"Steele"),([Digit '9',Digi t '1'],"Marlow"),([Digit '9',Digit '2',Digit '3'],"Stewart")]