Exercise 4 – Writing Functions
Hao Tian April 2019
1 Exercises
1.1 Writing functions for tree structure
Using the tree data structure we defined in class (see attached), writing the following functions:
1. WriteafunctiontoBalancetoconvertabinarytreeintobalancedbinary tree. (Hint: you may write rotate functions, see ‘Tree Rotation’ on wiki, and any functions we had defined are ready to use)
2. Write a higher order function binTreeMap to do any type of manipu- lation for each nodes.
toBalance :: BinTree a − > BinTree a
Example: BinTree (Node Empty 0 (Node Empty 1 (Node Empty 2 Empty))) = Node (Node Empty 0 Empty) 1 (Node Empty 2 Empty)
binTreeMap:: (a−>b)−>BinTreea−>BinTreeb
Example: binTreeMap (+1) (Node Empty 0 (Node Empty 1 (Node Empty 2 Empty))) = (Node Empty 1 (Node Empty 2 (Node Empty 3 Empty)))
1.2 Writing function for matrix
Using the Matrix defined on Sudoku solver, writing a function of matrix mul- tipliction. (Hint: use cols for transpose)
multiMatrix :: Num a => Matrix a − > Matrix a − > Matrix a Example: multiMatrix [[1,2],[3,4]] [[1,2],[3,4]] = [[7,10],[15,22]]
2 Solutions
1
1.
data BinTree a = Empty
| Node ( BinTree a ) a ( BinTree a ) deriving (Eq , Show)
rotateL :: BinTree a -> BinTree a
rotateL Empty = Empty
rotateL (Node left a Empty) = error “Cannot rotate”
rotateL (Node left a (Node subl b subr)) = (Node (Node left a subl) b subr)
rotateR :: BinTree a -> BinTree a
rotateR Empty = Empty
rotateR (Node Empty a right) = error “Cannot rotate”
rotateR (Node (Node subl b subr) a right) = (Node subl b (Node subr a right))
toBalance :: BinTree a -> BinTree a
toBalance Empty = Empty toBalance (Node left a right)
|(height left – height right) > 1 = toBalance (rotateR (Node left a right)) |(height left – height right) < -1 = toBalance (rotateL (Node left a right)) |otherwise = Node (toBalance left) a (toBalance right)
binTreeMap :: (a -> b) -> BinTree a -> BinTree b
binTreeMap f Empty = Empty
binTreeMap f (Node left a right) = Node (binTreeMap f left) (f a) (binTreeMap f right)
2.
type Matrix a = [Row a] type Row a = [a]
multiMatrix :: Num a => Matrix a -> Matrix a -> Matrix a
multiMatrix a b = [ [ sum (zipWith (*) ar bc) | bc <- (cols b) ] | ar <- a ]
CIS 623 Exercises on trees Trees
Suppose we declare a type BInTree for binary trees using the follow- ing data declarations:
data BinTree a = Empty
| Node (BinTree a) a (BinTree a)
deriving (Eq, Show) Write the following functions in Haskell:
1. noOfNodes:
This function will take a binary tree T as input, return the no. of
nodes of the T. 2. height:
This function will take a binary tree T as input, return the height of the tree T.
3. preorder:
This function will take a binary tree T as input, return an pre-
ordering listing of items (of type a) stored in the nodes of T. 4. balanced:
This function will take a binary tree T as input, return True if T is height balanced. Otherwise, it will return False. Note that a binary tree T is said to be height balanced if, at each node n in T, the height of the left subtree (rooted at n) and the height of the right subtree (rooted at n) is either 0, 1, or −1.
Solution outline
For background, see Ch.6 of the text: Open data structures available at http://opendatastructures.org/ods-java.pdf.
data BinTree a = Empty
| Node (BinTree a) a (BinTree a)
noOfNodes noOfNodes Empty noOfNodes (Node
deriving (Eq , Show)
:: BinTree a −> Int = 0
l f t n rght ) =
1 + noOfNodes l f t
+ noOfNodes rght
height :: BinTree a −> Int height Empty = −1
height (Node lft n rght) =
1 + maximum [ height lft , height rght ]
preorder preorder preorder
:: BinTree a −> [a] Empty = []
(Node lft n rght)
= n : ((preorder lft) ++ (preorder rght))
balanced balanced balanced
:: BinTree a −> Bool Empty = True
(Node lft n rght) = (balanced lft ) &&
( balanced rght ) &&
abs (height lft − height rght) <= 1
cis 623 exercises on trees 2
1 A Simple Sudoku Solver
2 27th September, 2007
3 In Chapter 05
4 _________________________________________________________
5 0. Basic data types
6
7 > type Matrix a
8 >typeRowa
9
10 > type Grid
11 > type Digit
12
13 > digits ::
14 > digits =
15
= [Row a] = [a]
= Matrix Digit = Char
[Digit] [‘1’..’9′]
16 > blank ::
17 > blank =
18
19 1. Specification 20
21 >
22 >
23
24 > 25
26 >
27 >
28 >
29 >
30
31 >
32 >
33
34 >
35 >
36 >
37
38 >
39 >
40 >
41 >
42
43 >
44 >
45 >
46
47 >
48 >
49
50 >
51 >
52 >
53
54 >
55 >
56 >
57
58 >
59 >
60 >
61
solve1 :: Grid -> [Grid]
solve1 = filter valid . expand . choices
type Choices = [Digit]
choices :: Grid -> Matrix Choices choices = map (map choice)
where choice d | blank d = digits | otherwise = [d]
expand :: Matrix Choices -> [Grid]
expand = cp
cp :: [[a]] cp []
cp (xs:xss)
. map cp
-> [[a]]
= [[]]
= [x:ys | x <- xs, ys <- cp xss]
valid :: valid g =
Grid -> Bool
nodups
nodups
nodups
=> [a]
-> Bool
xs && nodups xs
rows rows
cols
cols
cols
boxs boxs
:: Matrix a -> [Row a]
[]
Digit -> Bool
(== ‘0’)
all nodups
all nodups
all nodups
::Eqa = True
(rows g) &&
(cols g) &&
(boxs g)
(x:xs) = x `notElem`
=id
[xs] =[[x]|x<- xs]
:: Matrix a -> [Row a] (xs:xss) = zipWith (:) xs (cols xss)
:: Matrix a -> [Row a]
= map ungroup . ungroup . map cols .
group . map group
ungroup = concat
group [] = []
group (x:y:z:xs) = [x,y,z]:group xs
62 2. Pruning
63
64 > prune :: Matrix Choices -> Matrix Choices
65 >
66 >
67 >
68
69 >
70 >
71 >
72
73 >
74 >
75 >
76
prune =
pruneBy boxs . pruneBy cols . pruneBy rows where pruneBy f = f . map pruneRow . f
pruneRow :: Row Choices -> Row Choices pruneRow row = map (remove ones) row
where ones = [d | [d] <- row]
remove :: Choices -> Choices -> Choices remove xs [d] = [d]
remove xs ds = filter (`notElem` xs) ds
77 3. Single-cell expansion 78
79 >
80 >
81 >
82 >
83 >
84 >
85 >
86 >
87
88 >
89
90 4. Final algorithm 91
92 >
93 >
94
95 >
96 >
97 >
98 >
99 >
100 >
101
102 >
103 >
104
105 >
106 >
107
108 >
109 >
110 >
111 >
112 113 >
expand1 :: Matrix Choices -> [Matrix Choices] expand1 rows =
[rows1 ++ [row1 ++ [c]:row2] ++ rows2 | c <- cs] where
(rows1,row:rows2)
(row1,cs:row2)
smallest cs
n
= break (any smallest) rows = break smallest row
= length cs == n
= minimum (counts rows)
counts = filter (/=1) . map length . concat
solve2 :: solve2 =
Grid -> [Grid]
. choices
Choices -> [Grid]
= []
= [map (map head) pm]
= (concat . map search . expand1) pm
single [_] = True single _ = False
safe :: Matrix Choices -> Bool safe cm = all ok (rows cm) && all ok (cols cm) &&
all ok (boxs cm)
ok row = nodups [d | [d] <- row]
search :: search cm
Matrix
|not (safe pm) |complete pm |otherwise where pm =
search
prune cm
Matrix Choices -> Bool
complete ::
complete = all (all single)