bst.hs

module Main where

data Bst a = Nil | Node {
	elt :: a,
	l :: Bst a,
	r :: Bst a} deriving Show

insert_ntr Nil x = Node x Nil Nil
insert_ntr n x | x < elt n = n {l = insert_ntr (l n) x}
               | x > elt n = n {r = insert_ntr (r n) x} 
               | otherwise = n 

insert n x = recur n x id where
	recur Nil x fun = fun $ Node x Nil Nil
	recur n x fun | x < elt n = recur (l n) x $ fun . (\k -> n {l = k})
	              | x > elt n = recur (r n) x $ fun . (\k -> n {r = k})
	              | otherwise = n 

mkTree f = foldl f Nil 

main = do
	let l = [5,8,4,2,1,9,6,7,3,5]
	putStrLn . show . mkTree insert_ntr $ l
	putStrLn . show . mkTree insert $ l