Week 14: Exercises

1. Infinite Lists

The built-in function repeat produces an infinite list of identical elements:

> repeat 33
[33, 33, ...]

The built-in function iterate produces an infinite list by repeated applying a function to a value:

> iterate (*2) 1
[1, 2, 4, 8, ...]

Write these two functions.

2. Infinite Diagonal Matrix

Construct an infinite diagonal matrix as an infinite list of lists:

[[1, 0, 0, 0, ...],
[0, 1, 0, 0, ...],
[0, 0, 1, 0, ...],
.
.
.
]

3. Pascal's Triangle

Recall that Pascal's triangle looks like this:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
. . .

Construct Pascal's triangle as an infinite list of lists:

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], ...]

4. Printing Pascal's Triangle

Write a function printTriangle :: Int -> IO () that takes an integer N and prints the first N rows of Pascal's triangle as illustrated in the previous exercise.

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

6. From A to B

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

7. Cycle

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

8. Knight's Tour

Write a function that takes an integer N and generates a knight's tour on an N x N chessboard. This is a sequence of moves that a knight can make, starting in the upper-left corner of the board, that visits every square exactly once and ends back at the starting square.