Week 14: Exercises

1. Random-Access Tree

Build a data structure Tree a that is a random-access tree. It should support the following operations:

-- (make_tree n x) creates a Tree that can hold n values,
-- indexed from 0 .. (n - 1).  All values are initially set to x.
make_tree :: Int -> a -> Tree a

-- Fetch the value at index i.
fetch :: Tree a -> Int -> a

-- Update the value at index i.
update :: Tree a -> Int -> a -> Tree a

The functions fetch and update should run in O(log N) if the list holds N elements.

2. Random-Access List

Build a random-access list data structure that supports these operations:

-- An empty RList.
empty :: RList a

-- Prepend a value to an RList.
cons :: a -> RList a -> RList a
-- Fetch the value at index i.
fetch :: RList a -> Int -> a

-- Update the value at index i.

update :: RList a -> Int -> a -> RList a

3. Parsing Variables

Extend the expression parser we saw in the lecture so that expressions can contain variables. A variable name is any sequence of letters. Write a function eval that can evalute an expression in an environment in which every variable has a given value.

4. Parsing Statements

Extend the expression parser from the previous exercise so that it parses a series of statements, each of which assigns a value to a variable. Extend your evaluation function so that it evaluates a series of statements and returns an environment with the final values of all variables.

5. Arrays

a) Write a function toArray :: [a] -> Array Int a that converts a list to an array with integer indices, indexed from 0.

b) Write a function array2d :: [[a]] -> Array Int (Array Int a) that converts a list to a 2-dimensional array with integer indices, indexed from 0.

5. Square Submatrix

Write a function that takes a square matrix of type [[Bool]]. The function should return the offset and size of the largest square submatrix that contains only True values. Use two-dimensional dynamic programming, using immutable arrays for an efficient top-down solution.

6. State Monad

Implement the State monad using this type:

data State s a = State (s -> (a, s))

7. Writer Monad

Implement the Writer monad using this type:

data Writer w a = Writer (a, w)

8. Reader Monad

Implement the Reader monad using this type:

data Reader r a = Reader (r -> a)