Assignment 2

Haskell (due Tuesday 19 Sep)

References

More information about Haskell is available at

haskell.org, extensive web site with all kinds of resources.
The Haskell 98 report (for the brave, except for the index of standard functions).
A "cheat sheet" briefly explaining the most important standard functions.
The Haskell 98 library report, very useful documentation of the standard libraries.
A collection of important papers on the language, including the "Gentle Introduction".
The ghc libraries

1. Binary Trees

Binary trees with information at every node can be defined using the following declaration followed by a few test cases:

data Tree a = 
   Leaf a 
 | Branch a (Tree a) (Tree a)

t1 = Leaf 1
t2 = Leaf 2
t3 = Branch 3 t1 t2
t4 = Branch 4 t3 t3

t5 = Leaf "one"
t6 = Leaf "two"
t7 = Branch "three" t5 t6
t8 = Branch "four" t7 t7

Write three functions which traverse a tree in preorder, inorder, and postorder, and produce a list of the information found at every node.

Exercises> :i preorder
preorder :: Tree a -> [a]

Exercises> :i inorder
inorder :: Tree a -> [a]

Exercises> :i postorder
postorder :: Tree a -> [a]

Exercises> preorder t4
[4,3,1,2,3,1,2]
Exercises> inorder t4
[1,3,2,4,1,3,2]
Exercises> postorder t4
[1,2,3,1,2,3,4]
Exercises>

2. Reversing a List

Define a function rev to reverse a list:

Exercises> :i rev
rev :: [a] -> [a]

Exercises> rev [1..10]
[10,9,8,7,6,5,4,3,2,1]
Exercises>

Use the operator ++, which concatenates two lists, in your definition.

(There is a standard function to reverse a list, of course: it's called reverse).

3. Mirroring Operations: A Higher Order Function

Here are two useful standard functions:

take :: Int -> [a] -> [a]
take n xs returns the first n elements of xs
drop :: Int -> [a] -> [a]
drop n xs returns all but the first n elements of xs

They both operate at the beginning of a list. But there are no corresponding standard functions which operate at the end of a list. We could define takeRight and dropRight separately, of course, but let us instead define a higher-order function

mirror :: ([a] -> [b]) -> [a] -> [b]

such that mirror f xs applies any function f (of the right type) at the end, rather than the beginning, of a list. We will then be able to define

takeRight n xs = mirror (take n) xs
dropRight n xs = mirror (drop n) xs

4. More Higher-Order Functions

Write a function generate which takes a function f :: Int -> Int and which produces an infinite list of pairs. The first components of all the pairs are the natural numbers 0... The second component of each pair is the result of applying the given function to the first component of the pair.

Exercises> take 6 (generate factorial)
[(0,1),(1,1),(2,2),(3,6),(4,24),(5,120)]
Exercises> take 10 (generate (\n -> n + 1))
[(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,9),(9,10)]
Exercises>

5. In-place List Reversal

This exercise introduces Haskell references, and programming with do. Your task is to reverse a list in place, using no extra space.

Place the code below into your file:

module Exercises where
import Data.IORef

data RList a = Nil | Cons a (IORef (RList a))

insertRList :: Ord a => a -> IORef (RList a) -> IO ()
insertRList x xs =
  do cell <- readIORef xs
     case cell of
        Nil -> do new <- newIORef Nil
                  writeIORef xs (Cons x new)
        Cons y xs'
          | x <= y -> do new <- newIORef cell
                         writeIORef xs (Cons x new)
          | x > y  -> insertRList x xs'

readRList :: IORef (RList a) -> IO [a]
readRList xs =
  do cell <- readIORef xs
     case cell of
        Nil -> return []
        Cons x xs' ->
           do ys <- readRList xs'
              return (x:ys)

test = do xs <- newIORef Nil
          insertRList 8 xs
          insertRList 9 xs
          insertRList 10 xs
          insertRList 1 xs
          insertRList 2 xs
          insertRList 3 xs
          insertRList 4 xs
          insertRList 5 xs
          insertRList 6 xs
          insertRList 7 xs
          ys <- readRList xs
          xs' <- revR xs
          zs <- readRList xs'
          return (ys,zs)

Notes:

We import module Data.IORef, which defines the type IORef and the operations on it.
We define the type RList, of lists with a reference in the tail.
We define the function insertRList for adding elements to a list.
We define readRList, which "follows pointers" to extract the (pure) list of elements from an RList.
We define test, which creates a list, reads it, calls revR to reverse it in place, reads the result, and then returns the contents of the list before and after reversal.

Running test should produce the following output:

Exercises> test
([1,2,3,4,5,6,7,8,9,10],[10,9,8,7,6,5,4,3,2,1])
Exercises>

But the definition of revR is missing. Complete the program so that the test works as above.