tree.hs

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

emptyNode :: a -> Tree a
emptyNode x = Node x EmptyTree EmptyTree

insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = emptyNode x
insert x (Node a left right)
  | x == a = Node x left right
  | x < a  = Node a (insert x left) right
  | x > a  = Node a left (insert x right)

find :: (Ord a) => a -> Tree a -> Bool
find x EmptyTree = False
find x (Node a left right)
  | x == a = True
  | x < a  = find x left
  | x > a  = find x right

instance Functor Tree where
  fmap f EmptyTree = EmptyTree
  fmap f (Node x left right) = Node (f x) (fmap f left) (fmap f right)

main = 
  let 
    nums = [ 8, 6, 4, 1, 7, 3, 5 ]
    numsTree = foldr insert EmptyTree nums
  in
    print $ 8 `find` fmap (*3) numsTree