1. Functional Queue

In the lecture, we saw this type class for a functional queue of integers:

class IntQueue q where
  isEmpty :: q -> Bool
  enqueue :: Int -> q -> q
  dequeue :: q -> (Int, q)

Implement an instance of IntQueue for which enqueue and dequeue run in O(1) on average. Use two stacks.

2. Functional Deque

Design a functional deque, i.e. double-ended queue.

3. Graph Representations

Suppose that the vertices of a directed or undirected graph are numbered from 1 to N. In Haskell, we can represent the graph in either of two ways:

1. as a list of vertices plus a list of edges:

   data GraphVE = GraphVE [Int] [(Int, Int)]

2. as a list of adjacency lists:

   data GraphAL = GraphAL [(Int, [Int])]

Write functions veToAL and alToVE that convert between the two representations.

4. From A to B

Write a function paths that takes a GraphAL and two vertices A and B, and returns a list of all paths from A to B. A path may not visit the same vertex twice.

5. Cycle

Write a function cycle that takes a GraphAL and a vertex A, and returns a list of all cycles from A to A.