Week 12: Exercises

1. Infinite Random String

Write a function babble :: RandomGen g => g -> String that produces an infinite string in which random consonants alternate with random vowels. For example, the string might begin "xotafepi..."

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

3. Applicative Functors

Here is a definition of the Applicative type class:

class Functor f => Applicative f where
  pure :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

Write a definition that declares that Maybe and [] are instances of this type class.

4. Lifted Arithmetic

a) Write operators .+ and .* that can add or multiply values held in a Maybe. If either value is Nothing, the result should be Nothing:

> Just 3 .+ Just 4
Just 7
> Just 3 .+ Nothing
Nothing

b) If you wrote the operators from part (a) to work only with a Maybe, generalize them to work with any Applicative type.

c) What happens if you use the generalized operators to do arithmetic with lists? For example:

> ([2, 3] .+ [4]) .* ([5, 6] .+ [7])

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

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

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.

6. Leftist Heap

In the lecture we learned about a data structure known as a leftist heap, which can be used to implement a priority queue. Implement a leftist heap in Haskell. Provide a type LHeap a that holds values of type a, along with the following functions:

empty :: LHeap a
add :: Ord a => LHeap a -> a -> LHeap a
remove :: Ord a => LHeap a -> (a, LHeap a)
merge :: Ord a => LHeap a -> LHeap a -> LHeap a

7. Heap Comparison

Continuing the previous exercise, write code that compares the performance of an LHeap with a heap implemented using Haskell's built-in Set type. To do this, insert and remove 1,000,000 random numbers into a heap of each type, and compare the running times.