Assignment 1

Introduction to Haskell (due 1/23)

To do

When you are finished please email me the file Exercises.hs

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

1. Running Haskell

We'll be using the Hugs interpreter. Hugs users usually use two windows: an editor, viewing the current module, and a window running the Hugs interpreter. Start your editor, and create a file Exercises.hs containing

module Exercises where
factorial n = product [1..n]

Start Hugs in -98 mode: On a CS Unix machine, use the command "/l/hugs/bin/hugs -98". You will see the following:

//dogfish.cs.indiana.edu/u/sabry > /l/hugs/bin/hugs -98
__   __ __  __  ____   ___      _________________________________________
||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
||___|| ||__|| ||__||  __||     Copyright (c) 1994-2001
||---||         ___||           World Wide Web: http://haskell.org/hugs
||   ||                         Report bugs to: hugs-bugs@haskell.org
||   || Version: February 2001  _________________________________________

Hugs mode: Restart with command line option +98 for Haskell 98 mode

Reading file "/l/hugs/share/hugs/lib/Prelude.hs":
                   
Hugs session for:
/l/hugs/share/hugs/lib/Prelude.hs
Type :? for help
Prelude>

(The flag -98 enables extensions, which we need, that go beyond the Haskell 98 standard).

Now load module Exercises into the interpreter, and test the definition of factorial.

Prelude> :l Exercises
Reading file "Exercises.hs":
                   
Hugs session for:
/l/hugs/share/hugs/lib/Prelude.hs
Exercises.hs
Exercises> factorial 6
720
Exercises>

To reload the module, use the command ":r". Once this works, you can experiment with small function definitions. A useful command to know is ":i", which displays information about any name.

Exercises> :i factorial
factorial :: (Num a, Enum a) => a -> a

Exercises>

(In this case, we discover that factorial is overloaded, and can be used at any type which is both numeric and enumerable, the latter because we used an enumeration [1..n] in its definition).

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

3. 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).

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

Hint: use reverse in the definition of mirror. If you have trouble with this, try defining takeRight in terms of reverse and take (without using any higher-order function), and then see if you can generalise the definition by parameterising it on a function.

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

6. 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 IOExts

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 IOExts, 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. This example requires that hugs was invoked with the -98 flag.

Hint: Use an auxiliary recursive function to implement the loop over the list.