Exercises.hs
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).
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 |
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> |
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).
Here are two useful standard functions:
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
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.
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> |
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:
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.