finish v6

7 files changed, 109 insertions, 0 deletions

diff --git a/54a-60/54a.hs b/54a-60/54a.hs
new file mode 100644
index 0000000..9b39576
--- /dev/null
+++ b/54a-60/54a.hs
@@ -0,0 +1,3 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+-- Haskell is type-safe, so there is no solution.
diff --git a/54a-60/55.hs b/54a-60/55.hs
new file mode 100644
index 0000000..5cc7b91
--- /dev/null
+++ b/54a-60/55.hs
@@ -0,0 +1,13 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+cbalTree :: Int -> [Tree Char]
+
+cbalTree 0 = [Empty]
+cbalTree x
+  | even n = [Branch 'x' lt rt | let st = cbalTree ln, lt <- st, rt <- st]
+  | otherwise = let st1 = cbalTree ln
+                    st2 = cbalTree (n - ln) in
+                    [Branch 'x' lt rt | lt <- st1, rt <- st2] ++
+                    [Branch 'x' lt rt | lt <- st2, rt <- st1]
+    where ln = n `div` 2
+          n = x - 1
diff --git a/54a-60/56.hs b/54a-60/56.hs
new file mode 100644
index 0000000..7bdc5dd
--- /dev/null
+++ b/54a-60/56.hs
@@ -0,0 +1,11 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+symmetric :: (Eq a) => Tree a -> Bool
+mirror :: (Eq a) => Tree a -> Tree a -> Bool
+
+mirror Empty Empty = True
+mirror (Branch _ a b) (Branch _ l r) = mirror a r && mirror b l
+mirror _ _ = False
+
+symmetric Empty = True
+symmetric (Branch _ l r) = mirror l r
diff --git a/54a-60/57.hs b/54a-60/57.hs
new file mode 100644
index 0000000..efe8588
--- /dev/null
+++ b/54a-60/57.hs
@@ -0,0 +1,23 @@
+import Data.List (foldl')
+
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+symmetric :: (Eq a) => Tree a -> Bool
+mirror :: (Eq a) => Tree a -> Tree a -> Bool
+
+mirror Empty Empty = True
+mirror (Branch _ a b) (Branch _ l r) = mirror a r && mirror b l
+mirror _ _ = False
+
+symmetric Empty = True
+symmetric (Branch _ l r) = mirror l r
+
+construct :: [Int] -> Tree Int
+addNode :: Tree Int -> Int -> Tree Int
+
+addNode Empty n = Branch n Empty Empty -- create node
+addNode (Branch x l r) n
+  | n <= x = Branch x (addNode l n) r
+  | otherwise = Branch x l (addNode r n)
+
+construct l = foldl' (\acc n -> addNode acc n) Empty l
diff --git a/54a-60/58.hs b/54a-60/58.hs
new file mode 100644
index 0000000..896889f
--- /dev/null
+++ b/54a-60/58.hs
@@ -0,0 +1,23 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+cbalTree :: Int -> [Tree Char]
+
+cbalTree 0 = [Empty]
+cbalTree x
+  | even n = [Branch 'x' lt rt | let st = cbalTree ln, lt <- st, rt <- st]
+  | otherwise = let st1 = cbalTree ln
+                    st2 = cbalTree (n - ln) in
+                    [Branch 'x' lt rt | lt <- st1, rt <- st2] ++
+                    [Branch 'x' lt rt | lt <- st2, rt <- st1]
+    where ln = n `div` 2
+          n = x - 1
+
+symCbalTrees :: Int -> [Tree Char]
+
+symCbalTrees x
+  | even n = [Branch 'x' st $ reverseTree st | st <- cbalTree ln]
+  | otherwise = []
+  where ln = n `div` 2
+        n = x - 1
+        reverseTree Empty = Empty
+        reverseTree (Branch x l r) = Branch x (reverseTree r) (reverseTree l)
diff --git a/54a-60/59.hs b/54a-60/59.hs
new file mode 100644
index 0000000..0faecd6
--- /dev/null
+++ b/54a-60/59.hs
@@ -0,0 +1,11 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+hbalTree :: a -> Int -> [Tree a]
+
+hbalTree x 0 = [Empty]
+hbalTree x 1 = [Branch x Empty Empty]
+hbalTree x h =
+    [Branch x lt rt
+      | (h1, h2) <- [(h-2, h-1), (h-1, h-2), (h-1, h-1)]
+      , lt <- hbalTree x h1
+      , rt <- hbalTree x h2]
diff --git a/54a-60/60.hs b/54a-60/60.hs
new file mode 100644
index 0000000..3facc1f
--- /dev/null
+++ b/54a-60/60.hs
@@ -0,0 +1,25 @@
+data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
+
+hbalTreeNodes :: a -> Int -> [Tree a]
+
+fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
+
+-- The minimum height for a balanced tree
+minHeight n = ceiling $ logBase 2 $ fromIntegral (n + 1)
+
+-- The minimum node for a height
+minNode h = fibs !! (h + 2) - 1
+
+maxNode h = 2 ^ h - 1
+maxHeight n = (length $ takeWhile (<= n + 1) fibs) - 3
+
+
+hbalTreeNodes x n = [t | h' <- [minHeight n..maxHeight n], t <- build n h']
+    where build _ 0 = [Empty]
+          build _ 1 = [Branch x Empty Empty]
+          build n h = let n' = n - 1 in
+                  [Branch x lt rt | (h1, h2) <- [(h-2, h-1), (h-1, h-2), (h-1, h-1)]
+                                  , n1 <- [max (n' - maxNode h2) $ minNode h1..
+                                           min (n' - minNode h2) $ maxNode h1]
+                                  , lt <- build n1 h1
+                                  , rt <- build (n' - n1) h2]