Home Page > > Details

Functional Programming Tutorial 8

 The Barcode Reader

Informatics 1 – Introduction to Computation
Functional Programming Tutorial 8
Banks, Heijltjes, Melkonian, Scott, Vlassi-Pandi, Wadler
Week 9
due 4pm Wednesday 18 November 2020
tutorials on Friday 20 November 2020
Attendance at tutorials is obligatory; please send email to lambrose@ed.ac.uk if you
cannot join your assigned tutorial.
Good Scholarly Practice: Please remember the good scholarly practice requirements
of the University regarding work for credit. You can find guidance at the School page
http://web.inf.ed.ac.uk/infweb/admin/policies/academic-misconduct.
This also has links to the relevant University pages. Please do not publish solutions to
these exercises on the internet or elsewhere, to avoid others copying your solutions.
1
1 The barcode reader
In this tutorial we will take a look at a barcode scanner. Of course, we will not be doing the actual
scanning, but what we will do is search a database for the item that belongs to a scanned barcode.
We will read the database from a file and store it in different shapes, to see which gives the fastest
retrieval times.
The Haskell files that come with this tutorial are Tutorial8.hs, KeymapList.hs, and KeymapTree.hs.
There is also the database itself: database.csv (csv stands for ‘comma-separated values’).
Let’s start by opening KeymapList.hs. This file defines an abstract data type for a keymap. The
file starts as follows:
module KeymapList ( Keymap,
size,
...
)
where
This declaration means that KeymapList is a module that can be used by other Haskell files, just
like Data.Char and Test.QuickCheck. The functions and constructors mentioned in parentheses
(Keymap, size, etc.) are the ones that are exported by the module, i.e. the ones that can be used
when the module is imported somewhere else.
Next, let’s take a look at the type declaration for Keymap.
newtype Keymap k a = K [(k,a)]
This defines the polymorphic data type Keymap. The first argument (k), is what’s used as the key
in the keymap, the second (a) is the type of the values stored. For instance, a keymap of type
Keymap Int String associates keys of type Int with values of type String.
Finally, there is the definition itself, K [(k,a)]. As you see, a keymap is simply stored as a list of
key—value pairs. The type-constructor K is just a wrapper that prevents us from using normal list
functions on keymaps. This is precisely the idea: we want the type to be abstract, so we can hide
the fact that we are using lists underneath. This ensures that we don’t use ordinary list functions on
keymaps and accidentally invalidate the representation. And it frees us to change our representation
whilst guaranteeing that our users’ code still works.
Now, let’s look at the functions in the file. The constraints Eq k mean that whatever the type k, it
must support equality testing. In other words, if we want to use a type as a key, we have to be able
to use the function (==) on values of that type—otherwise, we would have no way to identify the
right key in the keymap.
• size :: Eq k => Keymap k a -> Int
This function gives the number of entries in a Keymap. • get :: Eq k => k -> Keymap k a -> Maybe a
Given a key, this function looks up the associated value in a Keymap. In this function keys are
matched using (==), which is why the constraint Eq k is needed. The value returned is not
just of type a, but Maybe a, because a key might not occur in a Keymap. We will get back to
this later.
• set :: Eq k => k -> a -> Keymap k a -> Keymap k a
Given a key and a value, this function sets the value associated with the key to the given value
in a Keymap. If the key already had a value, this value is replaced; otherwise the key is newly
added to the keymap.
2
• del :: Eq k => k -> Keymap k a -> Keymap k a
This function deletes an entry from a keymap.
• select :: Eq k => (a -> Bool) -> Keymap k a -> Keymap k a
This function narrows a keymap down to those values that satisfy a given predicate.
• tolist :: Eq k => Keymap k a -> [(k,a)]
This function exports the keymap as a list.
• fromList :: Eq k => [(k,a)] -> Keymap k a
This function builds a keymap from a list.
Now that we know what KeymapList is like, we can start working on Tutorial8.hs. Just below
the top, you will find the declarations:
import KeymapList
type Barcode = String
type Product = String
type Unit = String
type Item = (Product,Unit)
type Catalogue = Keymap Barcode Item
Firstly, we are importing the KeymapList module. Next, there are the type aliases Barcode, Product
and Unit, whose values are strings, and Item which is a pair (Product,Unit). Finally, we are using
the type alias Catalogue whose values are keymaps that associate a Barcode with an Item.
Note: Each barcode has a unique value.
Below that, you will find a little test database.
Exercise 1
Before we can work on the database, we need some way of viewing it. After you have loaded
the Tutorial8.hs file; if you try testDB or show testDB on the GHCi prompt, you will find
that it looks rather cluttered to print. Let’s try to improve that:
(a) Write a function longestProductLen that finds the length of the longest product name
in a list of (Barcode,Item)-pairs.
(b) Write a function formatLine that, given a number (the desired length of the product
name) returns the barcode, product and unit information, separated by dots, as a single
line. For example:
*Tutorial8> formatLine 7 ("0001",("product","unit"))
"0001...product...unit"
*Tutorial8> formatLine 7 ("0002",("thing","unknown"))
"0002...thing.....unknown"
You may assume that the product name is never longer than the desired length for it.
(c) Write a function showCatalogue that pretty-prints a Catalogue. You will need to use
toList (from the KeymapList module). Test your function by writing at the prompt:
*Tutorial8> putStr (showCatalogue testDB)
Exercise 2
Next, we will start using the get function.
Firstly, try the following at the interpreter:
3
*Tutorial8> :t get
You will see that the result type is Maybe a. This data-type is defined as follows:
data Maybe a = Nothing
| Just a
A value of type Maybe a is either the value Nothing, or it is a value of the form Just x. In
this way, values of type Maybe a can be used to represent values that may be absent. The
type is just like the type a, but it contains the extra value Nothing meaning “there is no
value.”
So by saying that get returns a value of type Maybe a, we are saying that it will either return
a value of the form Just x if x appears in the database, or otherwise will return Nothing.
Now try the following expressions at the interpreter:
*Tutorial8> get "9780201342758" testDB
*Tutorial8> get "000" testDB
What did you get?
(a) When you apply the function get with a certain key to the test database, what is the
type it returns? What are the possible values (hint: there are five)?
(b) Write a function maybeToList :: Maybe a -> [a] that returns the empty list if the
input is Nothing, and returns a singleton list otherwise.
(c) Write another function listToMaybe :: [a] -> Maybe a. You can think of this func￾tion as a safe version of head. It should return Nothing if the input is the empty list,
and return just the head otherwise.
(d) Write the function catMaybes :: [Maybe a] -> [a]. This function should drop all
elements of the form Nothing, and strip the Just constructor from all the other elements.
Exercise 3
(a) Using the functions from the previous exercise, write a function getItems that, given a
list of Barcodes and a Catalogue, returns a list of Items. Test your code for errors by
typing:
*Tutorial8> getItems ["0001","9780201342758","0003"] testDB
It should return a list containing only the item for the textbook.
1.1 The real database
We will see how fast our implementation of keymaps in KeymapList is. First, we need to turn on
the timekeeping feature of GHCi. Type this at the prompt:
*Tutorial8> :set +s
GHCi will now give you time (and memory use) information for each expression you ask it to
evaluate.
Your file Tutorial8.hs contains a few functions that we haven’t shown yet. First of all, it can read
in the database file database.csv. You can do this by writing:
*Tutorial8> theDB <- readDB
Done
(1.16 secs, 874,752,088 bytes)
4
The database is now loaded and assigned to the variable theDB, and will remain in the computer’s
memory until you reload your file.
The database is pretty large, so it’s not a good idea to try to print it on the screen. But you can
ask for the size:
*Tutorial8> size theDB
104651
(0.02 secs, 66,144 bytes)
Another thing that is provided is the function samples. This takes an integer, and provides the
given number of random barcodes from the database.
*Tutorial8> keys <- samples 3 theDB
(0.00 secs, 71,520 bytes)
*Tutorial8> keys
["0073999020083","0038793018971","0323900007253"]
(0.08 secs, 158,528 bytes)
Due to lazy evaluation, the work of finding the sample keys does not occur until you print the answer.
You can then use getItems to look up the items corresponding to the keys.
*Tutorial8> getItems keys theDB
[("The Beatles","Paperback"),
("SIDARI SPINACH LINGUINE","12 oz"),
("VICKS NYQUIL LQ CAP COLD/FLU","40.00 CT")]
(0.19 secs, 99,626,368 bytes)
Exercise 4
(a) Reload your file and load up the database again. Take a note of how much time it took.
(b) Take at least one hundred samples from the database, and record the average time it
takes to find an item with get. (Just record the time to find the item, not the time to
take a sample.)
(c) How many items does the get function from KeymapList look at before it finds the right
item, if it happens to be the last one? If the database was two times bigger, how much
longer would it take (on average) to find an item?
1.2 Keymaps as trees
In this part of the exercise we will build a different implementation of keymaps, based on trees rather
than lists. In the file KeymapTree.hs you will find a different declaration of the Keymap data type,
as well as the skeletons of the functions as in KeymapList.hs.
In KeymapTree we will implement the same functions and data type as we had in KeymapList, so
from the outside they will look the same. However, internally they will be very different, and so will
their performance.
The idea behind the tree implementation is explained in section 16.7 (page 395) of Thompson or
pages 135-137 of Lipovaca. Basically, the data is stored in the nodes of a tree. The left branch of a
node only stores data that is smaller than the data at the node itself, while the right branch stores
data that is larger.
First, look at the data type for Keymap. It is a lot more complicated than before:
data Ord k => Keymap k a = Leaf
| Node k a (Keymap k a) (Keymap k a)
5
The data type again defines a keymap storing keys of type k and values of type a. To sort the keys
into larger and smaller ones, we need the constraint Ord k. This means that the keys used in a
keymap can be ordered; in practice, that means we can always use the functions (==), (>=) and
(<=) on keys.
The constructors for Keymaps then are Leaf and Node. The value of Leaf is just a leaf. It stores no
data, like the empty list []. The second one does all the work. It carries (in order):
• a key of type k • the associated value of type a • a subtree on the left, which is a tree of type Keymap k a
• a subtree on the right, also a tree of type Keymap k a
When building a keymap in the shape of a tree, we want to make sure that the tree remains sorted.
That is, for any node with a certain key, the keys in the left subtree should all be smaller than that
key, and the keys in the right subtree should all be larger. To ensure this, we make sure a user of
these keymaps can only access them through functions that are safe.
Exercise 5
In Tutorial8.hs change the line:
import KeymapList
to
import KeymapTree
and load Tutorial8.hs up in GHCi. Think of what the following expression should return:
size ( Node "0001" "just some item" Leaf Leaf )
If you try it out, what does it say?
Note: What happens is that by not exporting the constructors Node and Leaf themselves, we
prevent people from writing recursive functions on our trees—at least outside of KeymapTree.hs.
Exercise 6
Now, we will complete the functions in KeymapTree.hs.
(a) Look at the function size. How does it work, and how can we recurse over trees?
(b) Define the function depth, which takes a tree and returns its depth, i.e. the length of
the longest path from its root to any of its leaves. A leaf has depth 0.
(c) Load up KeymapTree.hs into GHCi and try the functions size and depth on the little
test tree testTree (it should have size 4 and depth 3).
Exercise 7
Define the function toList, which takes a tree and returns the corresponding list of (key,
value) pairs. Try it on testTree. Can you make it so that the returned list is sorted by key?
Exercise 8
(a) Take a look at the function set. The function defines a helper function go to do the
recursion, to avoid repeating the variables key and value too often in the definition.
(b) Explain what the function go does when it encounters a leaf.
(c) Explain what the function go does when it looks at a node and it encounters the key it
was looking for? Complete the definition of this function. Hint: the last two cases will
need to recurse down an appropriate branch.
6
Exercise 9
(a) Complete the function get. Remember that you should return a Maybe-value. When
should it return Nothing, and when should it return Just a value?
(b) Test your function on testTree first, and then use QuickCheck to verify prop_set_get.
Exercise 10
(a) Write a function fromList to turn a list into a tree. You should use the function set
to add each element to the tree. Think about what the tree is that you should start out
with. For this question you can use recursion over the input list, but you could also try
to use foldr and uncurry.
(b) Use the test property prop_toList_fromList to test your solutions. If you managed to
return sorted lists with toList, you can also test with prop_toList_fromList_sorted.
Exercise 11
In this question we will evaluate the performance of KeymapTree that you have augmented in
section 1.2. Make sure that you have saved the KeymapTree.hs file and open up Tutorial8.hs.
We will redo the steps we took in Section 1.1, replacing the list representation of key maps
by the tree representation.
(a) Load up the database again. This time, it will be constructed as a tree. How much time
did it take?
(b) Try on at least one hundred examples to find how fast your get function is now.
(c) How many barcodes does our get function inspect, at most, when searching the database?
(d) Compare your answers with the ones you have for Exercise 4.
7
2 Optional material
Please note that optional exercices do contribute to the final mark. If you don’t do the
optional work and get the rest mostly right you will get a mark of 3/4. To get a mark
of 4/4, you must get almost all of the tutorial right, including the optional questions.
Exercise 12
Define two functions filterLT and filterGT, such that filterLT k t is the tree that results
from retaining all elements in t whose key is less than k. For example:
*Tutorial8> filterLT "0900000000000" testDB
[("0042400212509",("Universal deep-frying pan","pc"))
,("0265090316581",("The Macannihav'nmor Highland Single Malt","75ml bottle"))]
*Tutorial8> filterLT "0" testDB
[]
The function filterGT k t is the tree that results from retaining all elements in t whose
key is greater than k. So:
*Tutorial8> filterGT "0900000000000" testDB
[("0903900739533",("Bagpipes of Glory","6-CD Box"))
,("9780201342758",
("Thompson - \"Haskell: The Craft of Functional Programming\"","Book"))]
*Tutorial8> filterGT "0" testDB
[("0042400212509",("Universal deep-frying pan","pc"))
,("0265090316581",("The Macannihav'nmor Highland Single Malt","75ml bottle"))
,("0903900739533",("Bagpipes of Glory","6-CD Box"))
,("9780201342758",
("Thompson - \"Haskell: The Craft of Functional Programming\"","Book"))]
We will need these functions for the next part of the exercise.
Exercise 13
Define the function merge, which takes two trees and produces a single tree of all their
elements. Write a suitable quickCheck test for your function.
Exercise 14
Define the function del, which takes a key and a tree, and returns a tree identical to its
argument except with any entry for the given key deleted. You will need the function merge
here.
Exercise 15
Define the function select, which takes a predicate and a tree, and returns a new tree that
contains only entries where the value satisfies the predicate.
 
Contact Us - Email:99515681@qq.com    WeChat:codinghelp
Programming Assignment Help!