Programming Language Concepts Programming Exam 4

CENG 242
Programming Language Concepts

Programming Exam 4

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!
1
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
:
newtype Digit = Digit Char deriving (Show, Eq, Ord)
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:
type PhoneNumber = [Digit]
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:
toDigit :: Char - Maybe Digit
*PE4 toDigit '3'
Just (Digit '3')
*PE4 toDigit '9'
Just (Digit '9')
*PE4 toDigit 'a'
Nothing
*PE4 toDigit '?'
Nothing
*PE4 toDigit '\n'
Nothing
*PE4 toDigit '0'
Just (Digit '0')
*PE4 toDigit '+'
Nothing
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.
1
In real life, you should go for data Digit = Zero | One | ... | Nine which would be actually safe! The
current type can be misused. We didn’t go for it in this exam to keep things simpler.
2
• 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:
toDigits :: String - Maybe PhoneNumber
*PE4 toDigits ""
Nothing
*PE4 toDigits "1"
Just [Digit '1']
*PE4 toDigits "101"
Just [Digit '1',Digit '0',Digit '1']
*PE4 toDigits "5553332211"
Just [Digit '5',Digit '5',Digit '5',Digit '3',Digit '3',Digit '3',Digit '2',Digit
'2',Digit '1',Digit '1']
*PE4 toDigits "abcdef"
Nothing
*PE4 toDigits "ceng242"
Nothing
*PE4 toDigits "555x333"
Nothing
*PE4 toDigits "?27"
Nothing
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:
data DictTree k v = Node [(k, DictTree k v)] | Leaf v deriving Show
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:
type DigitTree = DictTree Digit String
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.
2Unless you’re reading ahead... If so, please go back and convert the digits first before I get angry!
3
Jones
Steele
Marlow
Stewart
Church
Curry Hughes
1
3
7
8
5
9
1
2
3
3
7
2 7
Phone Book:
-------------
1378: Jones
15: Steele
191: Marlow
1923: Stewart
3: Church
72: Curry
77: Hughes
Of course this is all meaningless without the code! So here’s the code corresponding to the tree representing
the phone book:
exampleTree :: DigitTree
exampleTree = Node [
(Digit '1', Node [
(Digit '3', Node [
(Digit '7', Node [
(Digit '8', Leaf "Jones")])]),
(Digit '5', Leaf "Steele"),
(Digit '9', Node [
(Digit '1', Leaf "Marlow"),
(Digit '2', Node [
(Digit '3', Leaf "Stewart")])])]),
(Digit '3', Leaf "Church"),
(Digit '7', Node [
(Digit '2', Leaf "Curry"),
(Digit '7', Leaf "Hughes")])]
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.
4
• 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:
5
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:
6
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")]
4 Regulations
1. Implementation and Submission: The template file named “PE4.hs” is available in the Virtual
Programming Lab (VPL) activity called “PE4” on OdtuClass. At this point, you have two options:
• You can download the template file, complete the implementation and test it with the given
sample I/O on your local machine. Then submit the same file through this activity.
• You can directly use the editor of VPL environment by using the auto-evaluation feature of
this activity interactively. Saving the code is equivalent to submit a file.
The second one is recommended. However, if you’re more comfortable with working on your local
machine, feel free to do it. Just make sure that your implementation can be compiled and tested in
the VPL environment after you submit it.
There is no limitation on online trials or submitted files through OdtuClass. The last one you
submitted will be graded.
2. Evaluation: Your program will be evaluated automatically using “black-box” technique so make
sure to obey the specifications. No erroneous input will be used. Therefore, you don’t have to
consider the invalid expressions.
7
Important Note: The given sample I/O’s are only to ease your debugging process and NOT
official. Furthermore, it is not guaranteed that they cover all the cases of required functions. As
a programmer, it is your responsibility to consider such extreme cases for the functions. Your
implementations will be evaluated by the official testcases to determine your actual grade after the
deadline.
8