data BinTree a = Empty
               | Node a (BinTree a) (BinTree a)
               deriving ( Show, Read )

instance Eq a => Eq (BinTree a) where
    Empty == Empty = True
    (Node v1 l1 r1) == (Node v2 l2 r2) = v1 == v2 && l1 == l2
                                                  && r1 == r2
    _ == _ = False

tree :: BinTree Integer
tree = Node 1 (Node 2 (Node 4 Empty Empty)
                      (Node 5 Empty Empty)
              )
              (Node 3 (Node 6 Empty Empty)
                      (Node 7 Empty Empty)
              )

-- preorder tree ~> [1,2,4,5,3,6,7]
preorder :: BinTree a -> [a]
preorder = undefined

-- inorder tree ~> [4,2,5,1,6,3,7]
inorder :: BinTree a -> [a]
inorder = undefined

-- postorder tree ~> [4,5,2,6,7,3,1]
postorder :: BinTree a -> [a]
postorder = undefined

findInList :: Eq k => [(k,a)] -> k -> Maybe a
findInList [] _ = Nothing
findInList ( (k, v) : xs) k1 = if k == k1 then Just v
                                          else findInList xs k1
--  findInList [("ahoj", 1), ("aa", 2)] "" ~> if "ahoj" == "" then Just 1 else findInList [("aa",2)] "" ~> findInList [("aa",2)] "" ~> if "aa" == "" then Just 2 else findInList [] "" ~> findInList [] "" ~> Nothing

assocList :: [ (String, Integer) ]
assocList = [ ("ahoj", 1), ("aa", 2) ]

{-
:t findInList assocList 1
   ^^^^^^^^^^              ::  Eq k => [(k,a)] -> k -> Maybe a
              ^^^^^^^^^    :: [(String, Integer)]
                        ^  :: Num b => b
   ^^^^^^^^^^^^^^^^^^^^    :: k = String
                              a = Integer
                           :: String -> Maybe Integer
                              typová chyba Num b => b a String
                              nelze substituovat
                              -}
findInList :: Eq k => [(k,a)] -> k -> Maybe a
findInList [] _ = Nothing
findInList ( (k, v) : xs) k1 = if k == k1 then Just v
                                          else findInList xs k1



insertTree :: Ord k => k -> v -> BinTree (k,v) -> BinTree (k,v)
insertTree key val Empty = Node (key, val) Empty Empty
insertTree key val (Node (k0,v0) l r) =
  if key == k0 then Node (k0, val) l r
     else if key < k0 then Node (k0, v0) (insertTree key val l) r
                      else Node (k0, v0) l (insertTree key val r)


findTree :: Ord k => BinTree (k,v) -> k -> Maybe v
findTree = undefined

searchTree :: BinTree (Integer, Integer)
searchTree = Node (10,2) (Node (5, 1) Empty Empty)
                         (Node (20, 4) (Node (15, 3) Empty Empty)
                                       (Node (30, 7) Empty Empty)
                         )

{-
:t uncurry insertTree
   ^^^^^^^             :: (a -> b -> c) -> (a, b) -> c
           ^^^^^^^^^^  :: Ord k => k -> v ->
                                    (BinTree (k,v) -> BinTree (k,v))
                          a = k
                          b = v
                          c = BinTree (k,v) -> BinTree (k,v)
  (k, v) -> (BinTree (k,v) -> BinTree (k,v))
  (k, v) -> BinTree (k,v) -> BinTree (k,v)
-}
toSearchTree :: Ord k => [(k, v)] -> BinTree (k, v)
toSearchTree list = foldr (uncurry insertTree) Empty list