CSCC24 2024 Summer Assignment 2

In this assignment, you will work with an application of lazy infinite lists.

As usual, you should also aim for reasonably efficient algorithms and reasonably organized, comprehensible code.

Code correctness (mostly auto-testing) is worth 90% of the marks; code quality is worth 10%.

Ordered Lists for Sets

In this assignment, we use lists to represent sets. Element types are instances of Ord; each list has elements in strictly increasing order. A list may be infinite, representing an infinite set. E.g., the set of even natural numbers is represented by

0 : 2 : 4 : 6 : 8 : 10 : ...

We can still perform some set operations meaningfully on infinite lists because the elements are in strictly increasing order.

Question 1: Union (2 marks, automarking only)

Implement unioning of two sets. Since the inputs are sorted lists, this is like the merge stage in mergesort, except: If an element occurs in both input lists, “set union” means you want only one occurrence in the output list.

union :: Ord a => [a] -> [a] -> [a]

Question 2: (5 marks)

In this question, you will implement a function setBinOp that generates this set in our list representation:

setBinOp :: (Ord a, Ord b, Ord c) => (a -> b -> c) -> [a] -> [b] -> [c]
setBinOp f xs ys = {f u v ∣ u ∈ xs, v ∈ ys}

To be sure, this would be very difficult or impossible for infinite sets if f is arbitrary. But it is very doable (even efficient) if f is strictly monotonic; more precisely:

• If x < x′, then f x y < f x′ y
• If y < y′, then f x y < f x y′

The following idea suggests an algorithm. I leave the base cases (when xs or ys is empty) to you. But if

• xs has least element x (the 1st element in the list), and the remaining elements are xt
• ys has least element y, and the remaining elements are yt

then this decomposition is helpful:

{f u v ∣ u ∈ xs, v ∈ ys} = {f x y} ∪ {f x v ∣ v ∈ yt} ∪ {f u v ∣ u ∈ xt, v ∈ ys}

Note:

• f x y is the least element of the output set, so you already know that it must be the 1st element of the output list.

• The 3rd component can be done by a recursive call.

• Although the formula uses ∪ twice, it is not a good idea to use union for both! (You can try and run into a problem. You can sketch out the lazy evaluation to see why). What is the first bullet point suggesting?

Example: If we have the powers of 2 and the powers of 3 in increasing order:

powers2 = iterate (* 2) 1
powers3 = iterate (* 3) 1

Then setBinOp (*) powers2 powers3 is the list of all numbers of the form 2ⁱ × 3^j in increasing order.

Question 3 (1 mark, automarking only)

We now set up a binary tree type that stores tree sizes. This will be used in the next question in which we generate the list of all trees ordered by sizes.

Here are the definitions of the tree type and a wrapper type that stores a tree and its size. We use the number of leaf nodes (L) as size.

data BinaryTree = L | B BinaryTree BinaryTree  deriving (Eq, Ord, Show)
data SizedTree = S Integer BinaryTree   deriving (Eq, Ord, Show)

Implement:

• leaf :: SizedTree

  (a leaf and its size (1)).

• branch :: SizedTree -> SizedTree -> SizedTree

  builds a new tree using the two input trees as children (left child is 1st argument), and computes and stores the new size.

Question 4 (2 marks, automarking only)

Notice that SizedTree derives Ord; the auto-generated order compares by size first (simply because that’s the 1st field).

We note that the set S of all sized trees satisfies this recursive equation:

S = {leaf} ∪ {branch t₁ t₂ ∣ t₁ ∈ S, t₂ ∈ S}

Moreoever, it is true that leaf is the least element, and branch is strictly monotonic.

Implement S as allSizedTrees :: [SizedTree] by the recursive equation.

(Not marked, but recommended: Apply the method of successive approximations to see why your code works or doesn’t work.)

End of questions.