module Exercises where
import IOExts
-- 1
factorial n = product [1..n]
-- 2
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
preorder (Leaf a) = [a]
preorder (Branch a t1 t2) = [a] ++ preorder t1 ++ preorder t2
inorder (Leaf a) = [a]
inorder (Branch a t1 t2) = inorder t1 ++ [a] ++ inorder t2
postorder (Leaf a) = [a]
postorder (Branch a t1 t2) = postorder t1 ++ postorder t2 ++ [a]
-- 3
rev [] = []
rev (x:xs) = rev xs ++ [x]
-- 4
mirror f xs =
let ys = rev xs
in rev (f ys)
takeRight n xs = mirror (take n) xs
dropRight n xs = mirror (drop n) xs
-- 5
generate f = [ (i, f i) | i <- [0..] ]
-- 6
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'
print (ys,zs)
-- return (ys,zs)
revR :: Ord a => IORef (RList a) -> IO (IORef (RList a))
revR xs = do cell <- readIORef xs
revLoop xs cell Nil
revLoop :: Ord a =>
IORef (RList a) -> RList a -> RList a -> IO (IORef (RList a))
revLoop xs cell ys =
case cell of
Nil -> do writeIORef xs ys
return xs
Cons y xs' ->
do nextcell <- readIORef xs'
writeIORef xs' ys
revLoop xs nextcell cell