Functional Programming and Intelligent Algorithms

Overview

• Reading: Simon Thompson, Chapter 5-6 (skip 5.3)

In this tutorial we shall investigate the two most fundamental composite data types, namely lists and tuples.

Problem 1: Library database

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. 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.

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?

3. The Loan Database

For the sake of simplicity, we use the following types to represent books and people:

In other words, we use just the name and the title to represent a person and a book.

1. Define a data type Loan to represent a loan.

   Note that the loan needs to record both the book borrowed and the person borrowing. What data type(s) is/are appropriate?

   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?

2. Define a data type Database to represent the set of all loans.

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:

   1. loan1 representing the fact that "John" has borrowed "Huckleberry Finn"
   2. loan2 representing the fact that "John" has borrowed "Tom Sawyer"
   3. 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.

3. Check your definitions by evaluating them in ghci.

5. Retrieval functions

A database is nothing without functions to access it. We start with two retrieval functions.

books :: Database -> Person -> [Book] borrowers :: Database -> Book -> [Person]

The first function returns a list of books borrowed by the given person. The second function returns a list of person borrowing copies of the given book.

1. Implement the two retrieval functions.

2. Test both functions in ghci:

   books db1 "John" books db1 "Jane" borrowers db1 "Huckleberry Finn" borrowers db1 "Tom Sawyer"

3. What output do you expect? What output do you get? Compare the two.

6. More retrieval

We want two more retrieval 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. Implement the two new retrieval functions.

2. Note that you can use books and borrowers as helpers for the two new 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.

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. We shall implement the following to functions:

1. The first function adds a loan to the database, and the second one removes a loan.

2. Implement the two modifier functions.

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.

8. Discussion

What happens if you add duplicate loans? Decide what you expect first, and try it out afterwards:

Answer the following:

1. Should duplicate loans be allowed?
2. 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.
3. Do you think your/our implementation is satisfactory on this point?

Tips: 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.

Problem 2: Implementation of Picture

See Thompson Chapter 6.4