Week 13: Exercises

1. Random Walk

Write a program that simulates a random walk in two dimensions. The program should take an integer N on the command line, and simulate N random steps starting from the origin (0, 0). Each step should move randomly left, right, up, or down. The program should print the position after each random step. At the end, it should print the number of times that the walk visited the origin, and also the furthest Manhattan distance (|x| + |y|) that was reached from the origin. For example:

$ runghc walk 10
0 0
0 1
1 1
1 2
0 2
0 1
1 1
1 0
0 0
0 1
0 2
visits to origin: 2
furthest distance: 3

2. 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, Int) a that converts a list of lists to a 2-dimensional array with integer indices, indexed from 0.

3. Integer Map

Define a type IMap a that is a map from a fixed range of integers (indexed from 0) to values of type a. Provide the following functions:

makeIMap :: [a] -> IMap a
iget :: IMap a -> Int -> a
iset :: IMap a -> Int -> a -> IMap a

makeIMap can assume that the given list is non-empty. The iget and iset functions should run in O(log N), where N is the number of elements in the map.

Also declare that IMap is an instance of Functor.