BinSearchTree.icl

/*
	I decided to add 3 hulp functions to solve this. I wanted to keep track of what values the children
	should be smaller than and what values the children should be larger than. I did this by using 2 lists
	one for smaller one for larger.
	
	As such a child should either be smaller than certain parents and larger than certain parents. The lists
	keep track of what values the child should be smaller / larger than.
	
	A Leaf is always ordered, so is a node with no parents. Than there are 3 other cases:
		Left & Right child is a node
		Left child is a node right child is a leaf
		Left child is a leaf right child is a node

	The algorithm handles all three cases differently, but the basic principle is always the same. Keep track
	of the values of the parent nodes and make sure the children's values are within the limits of their parents.
*/
is_geordend :: (Tree a) -> Bool | Ord a
is_geordend Leaf				= True
is_geordend (Node _ Leaf Leaf)  = True
is_geordend (Node x l r)		= is_geordend2 (Node x l r) [] []
where
	/*
		Makes sure a given child value is smaller than all the parents to the right in the tree
	*/
	smallerThan :: a [a] -> Bool | Ord a		
	smallerThan _ [] 	 = True
	smallerThan e [x:xs]
	|e < x 				 = smallerThan e xs
	| otherwise 		 = False
	/*
		Makes sure a given child value is larger than all the parents to the left in the tree
	*/
	largerThan :: a [a] -> Bool | Ord a
	largerThan _ [] 	 = True
	largerThan e [x:xs]
	| e > x				 = largerThan e xs
	| otherwise			 = False
	/*
	 	The help function which uses two lists, one for values the node should be smaller than and one
	 	for values the nodes should be larger than.
	*/
	is_geordend2 :: (Tree a) [a] [a] -> Bool | Ord a
	is_geordend2 Leaf _ _ 															= True
	is_geordend2 (Node x Leaf Leaf) smaller larger									
	| (smallerThan x smaller) && (largerThan x larger)								= True
	| otherwise																		= False
	is_geordend2 (Node x l=:(Node y ll lr) r=:(Node z rl rr)) smaller larger
	| (x > y ) && (smallerThan x smaller) && (x < z)  && (largerThan x larger)		= (is_geordend2 l (smaller ++ [x]) larger) && (is_geordend2 r smaller (larger ++ [x]))
	| otherwise							 											= False
	is_geordend2 (Node x Leaf r=:(Node z rl rr)) smaller larger
	| (x < z)  && (largerThan x larger) && (smallerThan x smaller)					= (is_geordend2 r smaller (larger ++ [x]))
	| otherwise																		= False
	is_geordend2 (Node x l=:(Node y ll lr) Leaf) smaller larger
	| (x > y ) && (smallerThan x smaller) && (largerThan x larger)					= (is_geordend2 l (smaller ++ [x]) larger)
	| otherwise																		= False