Tutorial 6: Lists and Tuples

1 Tutorial 6: Lists and Tuples

Reading: Simon Thompson, Chapter 5 (skip 5.3). This exercise follows the example in Chapter 5.7 of Simon Thompson’s book.

We are going to design a simple system to record books borrowed from a library. To do this, we will need both tuples and lists. If you want to, you may use algebraic data types, but if you have enough on your plate already, don’t think about algebraic data types until next week.

Primarily, we need a data structure to record loans. A loan in this context is the fact that a given person has borrowed a particular book. Thus we also need to be able to represent books and persons.

1.1 Getting started

You need to create a new Haskell module (file) with all the definitions in this tutorial.

It is useful to run ghci in a window beside your editor, and reload the file after every amendment and test functions. Only reloading the file will tell you if it is syntactically correct.

1.2 Books and Persons

Books and persons may be represented in different ways in terms of data types. Think through the following:

1.: What information should be included for each book?
2.: What information should be included for each person?
3.: What data types are appropriate for books and persons?

1.3 The Loan Database

1.: Define data types for a Person (borrower) and a book. For instance, as follows: type Person = String type Book = String
These are simple (and crude) definitions. A book is represented only by its title, and a person by his name.
2.: Define a data type Loan to represent a loan, recording the borrower (a person) and the book borrowed. E.g. type Loan = (Book,Person)
3.: Finally we need a data type Database which records the set of outstanding loans. What data types can be used to represent a set in Haskell?
We can use a list, as follows:
type Database = [Loan]

1.4 Test Objects

Let’s define a couple of objects for the sake of testing.

1.

Define the following constants of type Loan in your module:

a): loan1 representing the fact that "John" has borrowed "Huckleberry Finn" I.e. loan1 = ("Huckleberry Finn", "John")
b): loan2 representing the fact that "John" has borrowed "Tom Sawyer"
c): loan3 representing the fact that "Jane" has borrowed "Tom Sawyer"

2.

Define a database db1 containing each of the three loans loan1, loan2, and loan3. I.e.

db1 = [loan1,loan2,loan3]

3.

Check your definitions by evaluating them in ghci. I.e. loan1 db1

4.

Also evaluate loan2 and loan3 to check that they are correct.

1.5 Retrieval functions

A database is nothing without functions to access it. Add the declarations and definitions to you module file as you work through the steps below.

1.: Define a function to get all the books borrowed by a particular person. We can declare it as follows: books :: Database −> Person −> [Book]
We can define the books function using list comprehension:
books db person = [ b | (b,p) <− db, p == person ]
2.: Similar to the above, we define a function to return all people who have borrowed a particular book, i.e. borrowers :: Database −> Book −> [Person]
Write a definition for the borrowers function.
3.: Test both functions in ghci: books db1 "John" books db1 "Jane" borrowers db1 "Huckleberry Finn" borrowers db1 "Tom Sawyer"
4.: What output do you expect? What output do you get? Compare the two.

1.6 More retrieval

The retrieval functions above return lists. Let’s look at a couple of other useful retrievel functions.

The first function says whether the given book is borrowed or not. The second function gives the number of books borrowed by the given person.

1.: We want to know if a particular book has been borrowed. I.e. borrowed :: Database −> Book −> Bool
We can implement this using the borrowers function, and see if the result is empty or not, e.g.
borrowed db book = length (borrowers db book) > 0
2.: We want to know how many books a given individual has borrowed. I.e. numBorrowed :: Database −> Person −> Int
Write a definition using the books and length functions.
3.: Test both functions in ghci: numBorrowed db1 "John" numBorrowed db1 "Jane" borrowed db1 "Huckleberry Finn" borrowed db1 "Tom Sawyer"
What output do you expect? What output do you get? Compare the two.

1.7 Modifiers

We are able to retrieve data, but we also want to update the database. Since Haskell does not have variables, we cannot really change anything. We need functions which take the old database as input and returns a modified database as output.

1.: Add a function to add a loan. I.e. makeLoan :: Database −> Person −> Book −> Database makeLoan db person book = newloan : db where newloan = (book, person) :: Loan
2.: Add a function to remove a loan. I.e. returnLoan :: Database −> Person −> Book −> Database returnLoan db person book = [ loan | loan <−db, loan /= (book, person) ]
3.: Test both functions in ghci: makeLoan db1 "John" "Oliver Twist" returnLoan db1 "John" "Huckleberry Finn" returnLoan db1 "Jane" "Huckleberry Finn"
What output do you expect? What output do you get? Compare the two.

1.8 Discussion

1.

What happens if you add duplicate loans? E.g. add the following definitions in your module:

db2 = makeLoan db1 "John" "Tom Sawyer" 
db3 = returnLoan db2 "John" "Tom Sawyer"

Note that db2 has John borrowing Tom Sawyer added twice, as it was already in db1. In db3 this duplicate loan has been removed.

How many loans are in db3? Decide what you expect before you move on.

2.

Start GHCi and evaluate the two new databases:

db2 
db3

Do the results match your expectation?

3.

Discuss the following:

Should duplicate loans be allowed?
How should duplicate loans be handled? Remember that even if it is not allowed, a good program has to handle it as errors and prevent human error from messing up the database.
Do you think your/our implementation is satisfactory on this point?

1.9 Tip: Debugging output

Debugging a pure functional program can often feel like fumbling in the dark. If you have programmed imperatively, you are hopefully used to adding extra output instruction, to see what happens when the program runs.

Why don’t we just add such output lines in functional programs?

The answer is of course that I/O is side effects, and we don’t like side effects. We are going to learn how to do proper I/O tomorrow, but even so it is often desirable to keep core functions pure and without I/O.

However, for debugging purposes, it is possible to cheat, with the Debyg.Trace module. It provides a couple of functions which pretend to be pure, but which still produces output. This is good for debugging, but should otherwise be avoided. Feel free to look it up.

[next] [front] [up]