DM22, Spring 2007 - Weekly Note 7

Lecture March 12

More on Trees. Tupling. Modules. Handout of first project.

Reading

Sections 6.2, 7.4.1-2, 7.4.4, and 8.2 in Bird. Slides (trees.hs). Section 15.1 in Thompson (handout).

Lecture March 19 (Expected Contents)

Haskell evaluation details. Cyclic structures. The undefined value. Strict and non-strict functions. Proofs of properties of code.

Reading

Sections 7.1, 7.5, and 9.4 in Bird. Chapters 1 and 2 in Bird again, now with a focus on the undefined value, and on proofs.

Exercises March 21

Exam of winther 2001 (pdf), exercise 3.

The following exercises, where the object is to make (several versions of) a module Array which implements the functionality of arrays from imperative languages. This functionality is given by a type Array a and following three operations:

makeArray :: Int -> Array a


readArray :: Array a -> Int -> a


updateArray :: Array a -> Int -> a -> Array a

The value returned by these functions should be the following, respectively:

A new array with the size given as argument, and with all entries set to the value undefined from the standard prelude.

The array entry at the index given as second argument in the array given as first argument.

An array which is identical to the array given as first argument, except that for the index given as second argument, the array entry is the value given as third argument.

Exercises:

1. Make a module Array1, which exports a type Array and the three operations above. The underlying implementation should be a list. The type should be exported without any visible constructors (i.e. it should be an abstract data type), and hence be defined using keywords data or newtype.

2. Make a module Array2 which does exactly the same, except that the implementation should be based on binary search trees. The tree for an array should be balanced, should have the indices 0 to n-1 as the search keys, and should have the stored array elements as the tree elements stored with the keys. The shape of the tree is fixed, i.e., updates only changes the elements stored in the nodes, and do not insert or delete nodes, so rebalancing is not an issue.

3. Test the efficiency of the modules by:

   Creating a function which takes a size n and an array of size n, and returns the array resulting from inserting, using updateArray, a value (say, zero) at each index from n-1 to 0.

   Creating a function which takes a size n and an array of size n, and returns the sum of the values, read using readArray, at each index from n-1 to 0.

   Creating the actual test function, which takes a size n, creates an array using makeArray, and then calls the two functions above (updates first, then reads).

   Checking the efficiency of your two Array implementations, running the test function with different values of n. Note that you should not need to change the test code, just change the import Array1 statement to import Array2 in your test program.

   Comments:

   If you start Hugs with the command line option +s, you will after each evaluation get a summary of the number of reductions made (a measure of time) and cells used (a measure of space used in total).

   Depending on your Hugs setup, you may want to increase the heap size in Hugs (if "Garbage collection fails to reclaim sufficient space" appears), in order for the larger test to run. This is done using the command line option -hXXXk, where XXX is the number of cells (measured in thousands, due to the k) available to Hugs.

   For large tests, Hugs may also crash ("Segmentation fault") due to exhaustion of the C stack in the Hugs binary. Expanding this requires recompilation of Hugs, I believe.

   Since our array types are created using data and newtype keywords (as opposed to type), there is from the outset no class memberships. In particular, there is no show function for them. This is fine, since it prevents the user from seeing the implementation used. However, it may be annoying during development no to be able to see the arrays created. One solution is to start Hugs with the command line parameter -u, which substitutes a built-in printing mechanism in Hugs for the use of show.

4. Make a module Array2D for two-dimensional arrays. It should export a type Array2D a and three functions makeArray2D, readArray2D, and updateArray2D, the functionality and types of which are exactly as for the corresponding functions above, except that Int is changed into (Int,Int) for the index type and array size.

   Several implementation methods suggests themselves:

   • An array of arrays (using the modules already made), either using list-based or tree-based (one-dimensional) arrays.

   • Mapping a two-dimensional index (i,j) into a one-dimensional array (either list-based or tree-based) using the calculation i*n + j for a two-dimensional array where the size in one dimension is n.

   • Directly using a search tree implementation (as for one-dimensional arrays), now with search keys of the form (Int,Int).

   Implement module Array2D in at least two of these ways.