Week 13: 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. Mappable

The built-in map function maps a function over a list:

> map succ [1, 2, 3]
[2,3,4]

We might want to map functions over other sorts of data structures such as binary trees.

1. Write a type class Mappable representing any such structure, including a function gmap (general map).

2. Declare that the built-in types [] and Maybe are instances of Mappable.

3. Declare that the type

   data Tree t = Nil | Node t (Tree t) t

   is an instance of Mappable.

6. Depth-First Search

Recall that we can represent a graph in Haskell as a list of adjacency lists:

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

Write a function dfs that takes a Graph and a starting vertex V. The function should return a list of all vertices reachable from V in an order in which they could be visited by a depth-first search.

7. Connected Graph

Write a function that determines whether an undirected graph is connected.

8. Breadth-First Search

Write a function bfs that takes a Graph and a starting vertex V. The function should return a list of all vertices reachable from V in an order in which they could be visited by a breadth-first search.

9. All Spanning Trees

Write a function that takes an undirected graph and returns a list of all of its possible spanning trees.

10. Minimal Spanning Tree

Write a function that takes a graph and returns a minimal spanning tree.

11. N Queens Revisited

In a previous assignment, we wrote a function to test whether a list of integers represents a solution to the N-queens problem.

Now write a function that can generate a list of all solutions for a given N.

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

13. Square Root

Write a Haskell function that takes an integer n and computes its approximate square root as a Double. The approximation must be within 0.001 of the actual square root. What is your function's running time as a function of n?