代写 data structure algorithm Haskell Java Exercise 4 – Writing Functions

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)