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