1 files changed, 38 insertions, 0 deletions
diff --git a/tree.hs b/tree.hs
new file mode 100644
index 0000000..50f4774
--- /dev/null
+++ b/tree.hs
@@ -0,0 +1,38 @@
+import Data.Monoid
+import qualified Data.Foldable as F
+
+data Tree a = Empty | Node a (Tree a) (Tree a)
+    deriving (Show)
+
+instance F.Foldable Tree where
+    foldMap f Empty = mempty
+    foldMap f (Node x l r) = F.foldMap f l `mappend`
+                             f x `mappend`
+                             F.foldMap f r
+
+singleton :: a -> Tree a
+singleton x = Node x Empty Empty
+
+treeInsert :: (Ord a) => a -> Tree a -> Tree a
+treeInsert x Empty = singleton x
+treeInsert x (Node a left right)
+    | x == a = Node x left right
+    | x < a  = Node a (treeInsert x left) right
+    | x > a  = Node a left (treeInsert x right)
+
+treeElem :: (Ord a) => a -> Tree a -> Bool
+treeElem x Empty = False
+treeElem x (Node a left right)
+    | x == a = True
+    | x < a  = treeElem x left
+    | x > a  = treeElem x right
+
+testTree = Node 6
+            (Node 3
+                (Node 1 Empty Empty)
+                (Node 5 Empty Empty)
+            )
+            (Node 9
+                (Node 8 Empty Empty)
+                (Node 10 Empty Empty)
+            )