blob: 854deee7eb18cf70b1a11873d2d0f339007414b9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
module BinaryTree where
data BinaryTree a = Leaf
| Node (BinaryTree a) a (BinaryTree a)
deriving (Eq, Ord, Show)
insert' :: Ord a => a -> BinaryTree a -> BinaryTree a
insert' b Leaf = Node Leaf b Leaf
insert' b (Node left a right)
| b == a = Node left a right
| b < a = Node (insert' b left) a right
| b > a = Node left a (insert' b right)
mapTree :: (a -> b) -> BinaryTree a -> BinaryTree b
mapTree _ Leaf = Leaf
mapTree f (Node left v right) =
Node (mapTree f left) (f v) (mapTree f right)
preorder :: BinaryTree a -> [a]
preorder Leaf = []
preorder (Node left v right) =
v : ((preorder left) ++ (preorder right))
inorder :: BinaryTree a -> [a]
inorder Leaf = []
inorder (Node left v right) =
(inorder left) ++ [v] ++ (inorder right)
postorder :: BinaryTree a -> [a]
postorder Leaf = []
postorder (Node left v right) =
((postorder left) ++ (postorder right)) ++ [v]
foldTree :: (a -> b -> b)
-> b
-> BinaryTree a
-> b
foldTree _ acc Leaf = acc
foldTree f acc (Node left v right) = foldTree f r left
where r = foldTree f (f v acc) right
testTree :: BinaryTree Integer
testTree =
Node (Node Leaf 1 Leaf)
2
(Node Leaf 3 Leaf)
testPreorder :: IO ()
testPreorder =
if preorder testTree == [2, 1, 3]
then putStrLn "Preorder fine!"
else putStrLn "Bad news bears."
testInorder :: IO ()
testInorder =
if inorder testTree == [1, 2, 3]
then putStrLn "Inorder fine!"
else putStrLn "Bad news bears."
testPostorder :: IO ()
testPostorder =
if postorder testTree == [1, 3, 2]
then putStrLn "Postorder fine!"
else putStrLn "postorder failed check"
main :: IO ()
main = do
testPreorder
testInorder
testPostorder
testTree' :: BinaryTree Integer
testTree' =
Node (Node Leaf 3 Leaf)
1
(Node Leaf 4 Leaf)
mapExpected =
Node (Node Leaf 4 Leaf)
2
(Node Leaf 5 Leaf)
-- acceptance test for mapTree
mapOkay =
if mapTree (+1) testTree' == mapExpected
then print "yup okay!"
else error "test failed!"
|
