108.25/75.12	MAYBE
110.83/75.83	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
110.83/75.83	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
110.83/75.83	
110.83/75.83	
110.83/75.83	H-Termination with start terms of the given HASKELL could not be shown:
110.83/75.83	
110.83/75.83	(0) HASKELL
110.83/75.83	(1) LR [EQUIVALENT, 0 ms]
110.83/75.83	(2) HASKELL
110.83/75.83	(3) CR [EQUIVALENT, 0 ms]
110.83/75.83	(4) HASKELL
110.83/75.83	(5) BR [EQUIVALENT, 0 ms]
110.83/75.83	(6) HASKELL
110.83/75.83	(7) COR [EQUIVALENT, 17 ms]
110.83/75.83	(8) HASKELL
110.83/75.83	(9) LetRed [EQUIVALENT, 0 ms]
110.83/75.83	(10) HASKELL
110.83/75.83	(11) NumRed [SOUND, 0 ms]
110.83/75.83	(12) HASKELL
110.83/75.83	
110.83/75.83	
110.83/75.83	----------------------------------------
110.83/75.83	
110.83/75.83	(0)
110.83/75.83	Obligation:
110.83/75.83	mainModule Main 
110.83/75.83	module FiniteMap where {
110.83/75.83	import qualified Main;
110.83/75.83	import qualified Maybe;
110.83/75.83	import qualified Prelude;
110.83/75.83	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
110.83/75.83	
110.83/75.83	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
110.83/75.83	}
110.83/75.83	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
110.83/75.83	addListToFM fm key_elt_pairs = addListToFM_C (\old new ->new) fm key_elt_pairs;
110.83/75.83	
110.83/75.83	addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
110.83/75.83	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
110.83/75.83	add fmap (key,elt) = addToFM_C combiner fmap key elt;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
110.83/75.83	addToFM_C combiner EmptyFM key elt = unitFM key elt;
110.83/75.83	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
110.83/75.83	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
110.83/75.83	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
110.83/75.83	
110.83/75.83	emptyFM :: FiniteMap b a;
110.83/75.83	emptyFM = EmptyFM;
110.83/75.83	
110.83/75.83	findMax :: FiniteMap a b  ->  (a,b);
110.83/75.83	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
110.83/75.83	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
110.83/75.83	
110.83/75.83	findMin :: FiniteMap a b  ->  (a,b);
110.83/75.83	findMin (Branch key elt _ EmptyFM _) = (key,elt);
110.83/75.83	findMin (Branch key elt _ fm_l _) = findMin fm_l;
110.83/75.83	
110.83/75.83	listToFM :: Ord a => [(a,b)]  ->  FiniteMap a b;
110.83/75.83	listToFM = addListToFM emptyFM;
110.83/75.83	
110.83/75.83	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
110.83/75.83	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
110.83/75.83	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
110.83/75.83	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
110.83/75.83	 | otherwise -> double_L fm_L fm_R; 
110.83/75.83	 } 
110.83/75.83	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
110.83/75.83	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
110.83/75.83	 | otherwise -> double_R fm_L fm_R; 
110.83/75.83	 } 
110.83/75.83	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
110.83/75.83	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
110.83/75.83	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
110.83/75.83	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
110.83/75.83	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
110.83/75.83	size_l = sizeFM fm_L;
110.83/75.83	size_r = sizeFM fm_R;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
110.83/75.83	mkBranch which key elt fm_l fm_r = let { 
110.83/75.83	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
110.83/75.83	} in result where { 
110.83/75.83	balance_ok = True;
110.83/75.83	left_ok = case fm_l of { 
110.83/75.83	EmptyFM-> True; 
110.83/75.83	Branch left_key _ _ _ _-> let { 
110.83/75.83	biggest_left_key = fst (findMax fm_l);
110.83/75.83	} in biggest_left_key < key; 
110.83/75.83	 } ;
110.83/75.83	left_size = sizeFM fm_l;
110.83/75.83	right_ok = case fm_r of { 
110.83/75.83	EmptyFM-> True; 
110.83/75.83	Branch right_key _ _ _ _-> let { 
110.83/75.83	smallest_right_key = fst (findMin fm_r);
110.83/75.83	} in key < smallest_right_key; 
110.83/75.83	 } ;
110.83/75.83	right_size = sizeFM fm_r;
110.83/75.83	unbox :: Int  ->  Int;
110.83/75.83	unbox x = x;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	sIZE_RATIO :: Int;
110.83/75.83	sIZE_RATIO = 5;
110.83/75.83	
110.83/75.83	sizeFM :: FiniteMap b a  ->  Int;
110.83/75.83	sizeFM EmptyFM = 0;
110.83/75.83	sizeFM (Branch _ _ size _ _) = size;
110.83/75.83	
110.83/75.83	unitFM :: a  ->  b  ->  FiniteMap a b;
110.83/75.83	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
110.83/75.83	
110.83/75.83	}
110.83/75.83	module Maybe where {
110.83/75.83	import qualified FiniteMap;
110.83/75.83	import qualified Main;
110.83/75.83	import qualified Prelude;
110.83/75.83	}
110.83/75.83	module Main where {
110.83/75.83	import qualified FiniteMap;
110.83/75.83	import qualified Maybe;
110.83/75.83	import qualified Prelude;
110.83/75.83	}
110.83/75.83	
110.83/75.83	----------------------------------------
110.83/75.83	
110.83/75.83	(1) LR (EQUIVALENT)
110.83/75.83	Lambda Reductions:
110.83/75.83	The following Lambda expression
110.83/75.83	"\oldnew->new"
110.83/75.83	is transformed to
110.83/75.83	"addListToFM0 old new = new;
110.83/75.83	"
110.83/75.83	
110.83/75.83	----------------------------------------
110.83/75.83	
110.83/75.83	(2)
110.83/75.83	Obligation:
110.83/75.83	mainModule Main 
110.83/75.83	module FiniteMap where {
110.83/75.83	import qualified Main;
110.83/75.83	import qualified Maybe;
110.83/75.83	import qualified Prelude;
110.83/75.83	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
110.83/75.83	
110.83/75.83	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
110.83/75.83	}
110.83/75.83	addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
110.83/75.83	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
110.83/75.83	
110.83/75.83	addListToFM0 old new = new;
110.83/75.83	
110.83/75.83	addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
110.83/75.83	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
110.83/75.83	add fmap (key,elt) = addToFM_C combiner fmap key elt;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
110.83/75.83	addToFM_C combiner EmptyFM key elt = unitFM key elt;
110.83/75.83	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
110.83/75.83	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
110.83/75.83	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
110.83/75.83	
110.83/75.83	emptyFM :: FiniteMap b a;
110.83/75.83	emptyFM = EmptyFM;
110.83/75.83	
110.83/75.83	findMax :: FiniteMap b a  ->  (b,a);
110.83/75.83	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
110.83/75.83	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
110.83/75.83	
110.83/75.83	findMin :: FiniteMap a b  ->  (a,b);
110.83/75.83	findMin (Branch key elt _ EmptyFM _) = (key,elt);
110.83/75.83	findMin (Branch key elt _ fm_l _) = findMin fm_l;
110.83/75.83	
110.83/75.83	listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
110.83/75.83	listToFM = addListToFM emptyFM;
110.83/75.83	
110.83/75.83	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
110.83/75.83	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
110.83/75.83	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
110.83/75.83	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
110.83/75.83	 | otherwise -> double_L fm_L fm_R; 
110.83/75.83	 } 
110.83/75.83	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
110.83/75.83	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
110.83/75.83	 | otherwise -> double_R fm_L fm_R; 
110.83/75.83	 } 
110.83/75.83	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
110.83/75.83	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
110.83/75.83	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
110.83/75.83	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
110.83/75.83	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
110.83/75.83	size_l = sizeFM fm_L;
110.83/75.83	size_r = sizeFM fm_R;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
110.83/75.83	mkBranch which key elt fm_l fm_r = let { 
110.83/75.83	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
110.83/75.83	} in result where { 
110.83/75.83	balance_ok = True;
110.83/75.83	left_ok = case fm_l of { 
110.83/75.83	EmptyFM-> True; 
110.83/75.83	Branch left_key _ _ _ _-> let { 
110.83/75.83	biggest_left_key = fst (findMax fm_l);
110.83/75.83	} in biggest_left_key < key; 
110.83/75.83	 } ;
110.83/75.83	left_size = sizeFM fm_l;
110.83/75.83	right_ok = case fm_r of { 
110.83/75.83	EmptyFM-> True; 
110.83/75.83	Branch right_key _ _ _ _-> let { 
110.83/75.83	smallest_right_key = fst (findMin fm_r);
110.83/75.83	} in key < smallest_right_key; 
110.83/75.83	 } ;
110.83/75.83	right_size = sizeFM fm_r;
110.83/75.83	unbox :: Int  ->  Int;
110.83/75.83	unbox x = x;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	sIZE_RATIO :: Int;
110.83/75.83	sIZE_RATIO = 5;
110.83/75.83	
110.83/75.83	sizeFM :: FiniteMap b a  ->  Int;
110.83/75.83	sizeFM EmptyFM = 0;
110.83/75.83	sizeFM (Branch _ _ size _ _) = size;
110.83/75.83	
110.83/75.83	unitFM :: a  ->  b  ->  FiniteMap a b;
110.83/75.83	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
110.83/75.83	
110.83/75.83	}
110.83/75.83	module Maybe where {
110.83/75.83	import qualified FiniteMap;
110.83/75.83	import qualified Main;
110.83/75.83	import qualified Prelude;
110.83/75.83	}
110.83/75.83	module Main where {
110.83/75.83	import qualified FiniteMap;
110.83/75.83	import qualified Maybe;
110.83/75.83	import qualified Prelude;
110.83/75.83	}
110.83/75.83	
110.83/75.83	----------------------------------------
110.83/75.83	
110.83/75.83	(3) CR (EQUIVALENT)
110.83/75.83	Case Reductions:
110.83/75.83	The following Case expression
110.83/75.83	"case fm_r of {
110.83/75.83	EmptyFM  -> True;
110.83/75.83	Branch right_key _ _ _ _  -> let {
110.83/75.83	smallest_right_key  = fst (findMin fm_r);
110.83/75.83	} in key < smallest_right_key}
110.83/75.83	"
110.83/75.83	is transformed to
110.83/75.83	"right_ok0 fm_r key EmptyFM = True;
110.83/75.83	right_ok0 fm_r key (Branch right_key _ _ _ _) = let {
110.83/75.83	smallest_right_key  = fst (findMin fm_r);
110.83/75.83	} in key < smallest_right_key;
110.83/75.83	"
110.83/75.83	The following Case expression
110.83/75.83	"case fm_l of {
110.83/75.83	EmptyFM  -> True;
110.83/75.83	Branch left_key _ _ _ _  -> let {
110.83/75.83	biggest_left_key  = fst (findMax fm_l);
110.83/75.83	} in biggest_left_key < key}
110.83/75.83	"
110.83/75.83	is transformed to
110.83/75.83	"left_ok0 fm_l key EmptyFM = True;
110.83/75.83	left_ok0 fm_l key (Branch left_key _ _ _ _) = let {
110.83/75.83	biggest_left_key  = fst (findMax fm_l);
110.83/75.83	} in biggest_left_key < key;
110.83/75.83	"
110.83/75.83	The following Case expression
110.83/75.83	"case fm_R of {
110.83/75.83	Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R}
110.83/75.83	"
110.83/75.83	is transformed to
110.83/75.83	"mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
110.83/75.83	"
110.83/75.83	The following Case expression
110.83/75.83	"case fm_L of {
110.83/75.83	Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R}
110.83/75.83	"
110.83/75.83	is transformed to
110.83/75.83	"mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
110.83/75.83	"
110.83/75.83	
110.83/75.83	----------------------------------------
110.83/75.83	
110.83/75.83	(4)
110.83/75.83	Obligation:
110.83/75.83	mainModule Main 
110.83/75.83	module FiniteMap where {
110.83/75.83	import qualified Main;
110.83/75.83	import qualified Maybe;
110.83/75.83	import qualified Prelude;
110.83/75.83	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
110.83/75.83	
110.83/75.83	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
110.83/75.83	}
110.83/75.83	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
110.83/75.83	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
110.83/75.83	
110.83/75.83	addListToFM0 old new = new;
110.83/75.83	
110.83/75.83	addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
110.83/75.83	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
110.83/75.83	add fmap (key,elt) = addToFM_C combiner fmap key elt;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
110.83/75.83	addToFM_C combiner EmptyFM key elt = unitFM key elt;
110.83/75.83	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
110.83/75.83	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
110.83/75.83	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
110.83/75.83	
110.83/75.83	emptyFM :: FiniteMap a b;
110.83/75.83	emptyFM = EmptyFM;
110.83/75.83	
110.83/75.83	findMax :: FiniteMap b a  ->  (b,a);
110.83/75.83	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
110.83/75.83	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
110.83/75.83	
110.83/75.83	findMin :: FiniteMap b a  ->  (b,a);
110.83/75.83	findMin (Branch key elt _ EmptyFM _) = (key,elt);
110.83/75.83	findMin (Branch key elt _ fm_l _) = findMin fm_l;
110.83/75.83	
110.83/75.83	listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
110.83/75.83	listToFM = addListToFM emptyFM;
110.83/75.83	
110.83/75.83	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
110.83/75.83	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
110.83/75.83	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
110.83/75.83	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
110.83/75.83	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
110.83/75.83	double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
110.83/75.83	double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
110.83/75.83	mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
110.83/75.83	 | otherwise = double_L fm_L fm_R;
110.83/75.83	mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
110.83/75.83	 | otherwise = double_R fm_L fm_R;
110.83/75.83	single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
110.83/75.83	single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
110.83/75.83	size_l = sizeFM fm_L;
110.83/75.83	size_r = sizeFM fm_R;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
110.83/75.83	mkBranch which key elt fm_l fm_r = let { 
110.83/75.83	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
110.83/75.83	} in result where { 
110.83/75.83	balance_ok = True;
110.83/75.83	left_ok = left_ok0 fm_l key fm_l;
110.83/75.83	left_ok0 fm_l key EmptyFM = True;
110.83/75.83	left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
110.83/75.83	biggest_left_key = fst (findMax fm_l);
110.83/75.83	} in biggest_left_key < key;
110.83/75.83	left_size = sizeFM fm_l;
110.83/75.83	right_ok = right_ok0 fm_r key fm_r;
110.83/75.83	right_ok0 fm_r key EmptyFM = True;
110.83/75.83	right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
110.83/75.83	smallest_right_key = fst (findMin fm_r);
110.83/75.83	} in key < smallest_right_key;
110.83/75.83	right_size = sizeFM fm_r;
110.83/75.83	unbox :: Int  ->  Int;
110.83/75.83	unbox x = x;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	sIZE_RATIO :: Int;
110.83/75.83	sIZE_RATIO = 5;
110.83/75.83	
110.83/75.83	sizeFM :: FiniteMap a b  ->  Int;
110.83/75.83	sizeFM EmptyFM = 0;
110.83/75.83	sizeFM (Branch _ _ size _ _) = size;
110.83/75.83	
110.83/75.83	unitFM :: a  ->  b  ->  FiniteMap a b;
110.83/75.83	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
110.83/75.83	
110.83/75.83	}
110.83/75.83	module Maybe where {
110.83/75.83	import qualified FiniteMap;
110.83/75.83	import qualified Main;
110.83/75.83	import qualified Prelude;
110.83/75.83	}
110.83/75.83	module Main where {
110.83/75.83	import qualified FiniteMap;
110.83/75.83	import qualified Maybe;
110.83/75.83	import qualified Prelude;
110.83/75.83	}
110.83/75.83	
110.83/75.83	----------------------------------------
110.83/75.83	
110.83/75.83	(5) BR (EQUIVALENT)
110.83/75.83	Replaced joker patterns by fresh variables and removed binding patterns.
110.83/75.83	----------------------------------------
110.83/75.83	
110.83/75.83	(6)
110.83/75.83	Obligation:
110.83/75.83	mainModule Main 
110.83/75.83	module FiniteMap where {
110.83/75.83	import qualified Main;
110.83/75.83	import qualified Maybe;
110.83/75.83	import qualified Prelude;
110.83/75.83	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
110.83/75.83	
110.83/75.83	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
110.83/75.83	}
110.83/75.83	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
110.83/75.83	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
110.83/75.83	
110.83/75.83	addListToFM0 old new = new;
110.83/75.83	
110.83/75.83	addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
110.83/75.83	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
110.83/75.83	add fmap (key,elt) = addToFM_C combiner fmap key elt;
110.83/75.83	 };
110.83/75.83	
110.83/75.83	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
110.83/75.83	addToFM_C combiner EmptyFM key elt = unitFM key elt;
110.83/75.83	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt  | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r
110.83/75.83	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
110.83/75.83	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
110.83/75.83	
110.83/75.83	emptyFM :: FiniteMap a b;
110.83/75.83	emptyFM = EmptyFM;
110.83/75.83	
110.83/75.83	findMax :: FiniteMap a b  ->  (a,b);
110.83/75.83	findMax (Branch key elt xv xw EmptyFM) = (key,elt);
110.83/75.83	findMax (Branch key elt xx xy fm_r) = findMax fm_r;
110.83/75.83	
110.83/75.83	findMin :: FiniteMap b a  ->  (b,a);
110.83/75.83	findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
110.83/75.83	findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;
110.83/75.83	
110.83/75.83	listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
110.83/75.83	listToFM = addListToFM emptyFM;
110.83/75.83	
110.83/75.83	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
110.83/75.83	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
110.83/75.83	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
110.83/75.83	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
110.83/75.83	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
110.83/75.83	double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
110.83/75.83	double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
110.83/75.83	mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
110.83/75.83	 | otherwise = double_L fm_L fm_R;
110.83/75.83	mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
111.13/75.94	 | otherwise = double_R fm_L fm_R;
111.13/75.94	single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
111.13/75.94	single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
111.13/75.94	size_l = sizeFM fm_L;
111.13/75.94	size_r = sizeFM fm_R;
111.13/75.94	 };
111.13/75.94	
111.13/75.94	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
111.13/75.94	mkBranch which key elt fm_l fm_r = let { 
111.13/75.94	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
111.13/75.94	} in result where { 
111.13/75.94	balance_ok = True;
111.13/75.94	left_ok = left_ok0 fm_l key fm_l;
111.13/75.94	left_ok0 fm_l key EmptyFM = True;
111.13/75.94	left_ok0 fm_l key (Branch left_key vz wu wv ww) = let { 
111.13/75.94	biggest_left_key = fst (findMax fm_l);
111.13/75.94	} in biggest_left_key < key;
111.13/75.94	left_size = sizeFM fm_l;
111.13/75.94	right_ok = right_ok0 fm_r key fm_r;
111.13/75.94	right_ok0 fm_r key EmptyFM = True;
111.13/75.94	right_ok0 fm_r key (Branch right_key wx wy wz xu) = let { 
111.13/75.94	smallest_right_key = fst (findMin fm_r);
111.13/75.94	} in key < smallest_right_key;
111.13/75.94	right_size = sizeFM fm_r;
111.13/75.94	unbox :: Int  ->  Int;
111.13/75.94	unbox x = x;
111.13/75.94	 };
111.13/75.94	
111.13/75.94	sIZE_RATIO :: Int;
111.13/75.94	sIZE_RATIO = 5;
111.13/75.94	
111.13/75.94	sizeFM :: FiniteMap b a  ->  Int;
111.13/75.94	sizeFM EmptyFM = 0;
111.13/75.94	sizeFM (Branch zz vuu size vuv vuw) = size;
111.13/75.94	
111.13/75.94	unitFM :: a  ->  b  ->  FiniteMap a b;
111.13/75.94	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
111.13/75.94	
111.13/75.94	}
111.13/75.94	module Maybe where {
111.13/75.94	import qualified FiniteMap;
111.13/75.94	import qualified Main;
111.13/75.94	import qualified Prelude;
111.13/75.94	}
111.13/75.94	module Main where {
111.13/75.94	import qualified FiniteMap;
111.13/75.94	import qualified Maybe;
111.13/75.94	import qualified Prelude;
111.13/75.94	}
111.13/75.94	
111.13/75.94	----------------------------------------
111.13/75.94	
111.13/75.94	(7) COR (EQUIVALENT)
111.13/75.94	Cond Reductions:
111.13/75.94	The following Function with conditions
111.13/75.94	"compare x y|x == yEQ|x <= yLT|otherwiseGT;
111.13/75.94	"
111.13/75.94	is transformed to
111.13/75.94	"compare x y = compare3 x y;
111.13/75.94	"
111.13/75.94	"compare2 x y True = EQ;
111.13/75.94	compare2 x y False = compare1 x y (x <= y);
111.13/75.94	"
111.13/75.94	"compare1 x y True = LT;
111.13/75.94	compare1 x y False = compare0 x y otherwise;
111.13/75.94	"
111.13/75.94	"compare0 x y True = GT;
111.13/75.94	"
111.13/75.94	"compare3 x y = compare2 x y (x == y);
111.13/75.94	"
111.13/75.94	The following Function with conditions
111.13/75.94	"undefined |Falseundefined;
111.13/75.94	"
111.13/75.94	is transformed to
111.13/75.94	"undefined  = undefined1;
111.13/75.94	"
111.13/75.94	"undefined0 True = undefined;
111.13/75.94	"
111.13/75.94	"undefined1  = undefined0 False;
111.13/75.94	"
111.13/75.94	The following Function with conditions
111.13/75.94	"addToFM_C combiner EmptyFM key elt = unitFM key elt;
111.13/75.94	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt|new_key < keymkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r|new_key > keymkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)|otherwiseBranch new_key (combiner elt new_elt) size fm_l fm_r;
111.13/75.94	"
111.13/75.94	is transformed to
111.13/75.94	"addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
111.13/75.94	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
111.13/75.94	"
111.13/75.94	"addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
111.13/75.94	"
111.13/75.94	"addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
111.13/75.94	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
111.13/75.94	"
111.13/75.94	"addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
111.13/75.94	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
111.13/75.94	"
111.13/75.94	"addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
111.13/75.94	"
111.13/75.94	"addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
111.13/75.94	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
111.13/75.94	"
111.13/75.94	The following Function with conditions
111.13/75.94	"mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
111.13/75.94	"
111.13/75.94	is transformed to
111.13/75.94	"mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
111.13/75.94	"
111.13/75.94	"mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
111.13/75.94	mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
111.13/75.94	"
111.13/75.94	"mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
111.13/75.94	"
111.13/75.94	"mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
111.13/75.94	"
111.13/75.94	The following Function with conditions
111.13/75.94	"mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
111.13/75.94	"
111.13/75.94	is transformed to
111.13/75.94	"mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
111.13/75.94	"
111.13/75.94	"mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
111.13/75.94	mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
111.13/75.94	"
111.13/75.94	"mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
111.13/75.94	"
111.13/75.94	"mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
111.13/75.94	"
111.13/75.94	The following Function with conditions
111.13/75.94	"mkBalBranch key elt fm_L fm_R|size_l + size_r < 2mkBranch 1 key elt fm_L fm_R|size_r > sIZE_RATIO * size_lmkBalBranch0 fm_L fm_R fm_R|size_l > sIZE_RATIO * size_rmkBalBranch1 fm_L fm_R fm_L|otherwisemkBranch 2 key elt fm_L fm_R where {
111.13/75.94	double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
111.13/75.94	;
111.13/75.94	double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
111.13/75.94	;
111.13/75.94	mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
111.13/75.94	;
111.13/75.94	mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
111.13/75.94	;
111.13/75.94	single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
111.13/75.94	;
111.13/75.94	single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
111.13/75.94	;
111.13/75.94	size_l  = sizeFM fm_L;
111.13/75.94	;
111.13/75.94	size_r  = sizeFM fm_R;
111.13/75.94	} 
111.13/75.94	;
111.13/75.94	"
111.13/75.94	is transformed to
111.13/75.94	"mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
111.13/75.94	"
111.13/75.94	"mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
111.13/75.94	double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
111.13/75.94	;
111.13/75.94	double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
111.13/75.94	;
111.13/75.94	mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
111.13/75.94	;
111.13/75.94	mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
111.13/75.94	;
111.13/75.94	mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
111.13/75.94	mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
111.13/75.94	;
111.13/75.94	mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
111.13/75.94	;
111.13/75.94	mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
111.13/75.94	;
111.13/75.94	mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
111.13/75.94	;
111.13/75.94	mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
111.13/75.94	mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
111.13/75.94	;
111.13/75.94	mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
111.13/75.94	;
111.13/75.94	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
111.13/75.94	;
111.13/75.94	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
111.13/75.94	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
111.13/75.94	;
111.13/75.94	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
111.13/75.94	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
111.13/75.94	;
111.13/75.94	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
111.13/75.94	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
111.13/75.94	;
111.13/75.94	single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
111.13/75.94	;
111.13/75.94	single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
111.13/75.94	;
111.13/75.94	size_l  = sizeFM fm_L;
111.13/75.94	;
111.13/75.94	size_r  = sizeFM fm_R;
111.13/75.94	} 
111.13/75.94	;
111.13/75.94	"
111.13/75.94	
111.13/75.94	----------------------------------------
111.13/75.94	
111.13/75.94	(8)
111.13/75.94	Obligation:
111.13/75.94	mainModule Main 
111.13/75.94	module FiniteMap where {
111.13/75.94	import qualified Main;
111.13/75.94	import qualified Maybe;
111.13/75.94	import qualified Prelude;
111.13/75.94	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
111.13/75.94	
111.13/75.94	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
111.13/75.94	}
111.13/75.94	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
111.13/75.94	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
111.13/75.94	
111.13/75.94	addListToFM0 old new = new;
111.13/75.94	
111.13/75.94	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
111.13/75.94	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
111.13/75.94	add fmap (key,elt) = addToFM_C combiner fmap key elt;
111.13/75.94	 };
111.13/75.94	
111.13/75.94	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
111.13/75.94	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
111.13/75.94	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
111.13/75.94	
111.13/75.94	addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
111.13/75.94	
111.13/75.94	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
111.13/75.94	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
111.13/75.94	
111.13/75.94	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
111.13/75.94	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
111.13/75.94	
111.13/75.94	addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
111.13/75.94	
111.13/75.94	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
111.13/75.94	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
111.13/75.94	
111.13/75.94	emptyFM :: FiniteMap a b;
111.13/75.94	emptyFM = EmptyFM;
111.13/75.94	
111.13/75.94	findMax :: FiniteMap b a  ->  (b,a);
111.13/75.94	findMax (Branch key elt xv xw EmptyFM) = (key,elt);
111.13/75.94	findMax (Branch key elt xx xy fm_r) = findMax fm_r;
111.13/75.94	
111.13/75.94	findMin :: FiniteMap b a  ->  (b,a);
111.13/75.94	findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
111.13/75.94	findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;
111.13/75.94	
111.13/75.94	listToFM :: Ord a => [(a,b)]  ->  FiniteMap a b;
111.13/75.94	listToFM = addListToFM emptyFM;
111.13/75.94	
111.13/75.94	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
111.13/75.94	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
111.13/75.94	
111.13/75.94	mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 
111.13/75.94	double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
111.13/75.94	double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
111.13/75.94	mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
111.13/75.94	mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
111.13/75.94	mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
111.13/75.94	mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
111.13/75.94	mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
111.13/75.94	mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
111.13/75.94	mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
111.13/75.94	mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
111.13/75.94	mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
111.13/75.94	mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
111.13/75.94	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
111.13/75.94	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
111.13/75.94	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
111.13/75.94	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
111.13/75.94	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
111.13/75.94	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
111.13/75.94	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
111.13/75.94	single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
111.13/75.94	single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
111.13/75.94	size_l = sizeFM fm_L;
111.13/75.94	size_r = sizeFM fm_R;
111.13/75.94	 };
111.13/75.94	
111.13/75.94	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
111.13/75.94	mkBranch which key elt fm_l fm_r = let { 
111.13/75.94	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
111.13/75.94	} in result where { 
111.13/75.94	balance_ok = True;
111.13/75.94	left_ok = left_ok0 fm_l key fm_l;
111.13/75.94	left_ok0 fm_l key EmptyFM = True;
111.13/75.94	left_ok0 fm_l key (Branch left_key vz wu wv ww) = let { 
111.13/75.94	biggest_left_key = fst (findMax fm_l);
111.13/75.94	} in biggest_left_key < key;
111.13/75.94	left_size = sizeFM fm_l;
111.13/75.94	right_ok = right_ok0 fm_r key fm_r;
111.13/75.94	right_ok0 fm_r key EmptyFM = True;
111.13/75.94	right_ok0 fm_r key (Branch right_key wx wy wz xu) = let { 
111.13/75.94	smallest_right_key = fst (findMin fm_r);
111.13/75.94	} in key < smallest_right_key;
111.13/75.94	right_size = sizeFM fm_r;
111.13/75.94	unbox :: Int  ->  Int;
111.13/75.94	unbox x = x;
111.13/75.94	 };
111.13/75.94	
111.13/75.94	sIZE_RATIO :: Int;
111.13/75.94	sIZE_RATIO = 5;
111.13/75.94	
111.13/75.94	sizeFM :: FiniteMap a b  ->  Int;
111.13/75.94	sizeFM EmptyFM = 0;
111.13/75.94	sizeFM (Branch zz vuu size vuv vuw) = size;
111.13/75.94	
111.13/75.94	unitFM :: a  ->  b  ->  FiniteMap a b;
111.13/75.94	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
111.13/75.94	
111.13/75.94	}
111.13/75.94	module Maybe where {
111.13/75.94	import qualified FiniteMap;
111.13/75.94	import qualified Main;
111.13/75.94	import qualified Prelude;
111.13/75.94	}
111.13/75.94	module Main where {
111.13/75.94	import qualified FiniteMap;
111.13/75.94	import qualified Maybe;
111.13/75.94	import qualified Prelude;
111.13/75.94	}
111.13/75.94	
111.13/75.94	----------------------------------------
111.13/75.94	
111.13/75.94	(9) LetRed (EQUIVALENT)
111.13/75.94	Let/Where Reductions:
111.13/75.94	The bindings of the following Let/Where expression
111.13/75.94	"mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
111.13/75.94	double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
111.13/75.94	;
111.13/75.94	double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
111.13/75.94	;
111.13/75.94	mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
111.13/75.94	;
111.13/75.94	mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
111.13/75.94	;
111.13/75.94	mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
111.13/75.94	mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
111.13/75.94	;
111.13/75.94	mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
111.13/75.94	;
111.13/75.94	mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
111.13/75.94	;
111.13/75.94	mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
111.13/75.94	;
111.13/75.94	mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
111.13/75.94	mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
111.13/75.94	;
111.13/75.94	mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
111.13/75.94	;
111.13/75.94	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
111.13/75.94	;
111.13/75.94	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
111.41/75.99	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
111.41/75.99	;
111.41/75.99	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
111.41/75.99	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
111.41/75.99	;
111.41/75.99	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
111.41/75.99	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
111.41/75.99	;
111.41/75.99	single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
111.41/75.99	;
111.41/75.99	single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
111.41/75.99	;
111.41/75.99	size_l  = sizeFM fm_L;
111.41/75.99	;
111.41/75.99	size_r  = sizeFM fm_R;
111.41/75.99	} 
111.41/75.99	"
111.41/75.99	are unpacked to the following functions on top level
111.41/75.99	"mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
111.41/75.99	"
111.41/75.99	"mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwx vwy fm_lr fm_r);
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
111.41/75.99	"
111.41/75.99	"mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vwx vwy fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
111.41/75.99	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;
111.41/75.99	"
111.41/75.99	"mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vwz;
111.41/75.99	"
111.41/75.99	"mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vxu;
111.41/75.99	"
111.41/75.99	"mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vwx vwy fm_lrr fm_r);
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu);
111.41/75.99	"
111.41/75.99	"mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
111.41/75.99	mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu);
111.41/75.99	"
111.41/75.99	"mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwx vwy fm_l fm_rl) fm_rr;
111.41/75.99	"
111.41/75.99	The bindings of the following Let/Where expression
111.41/75.99	"foldl add fm key_elt_pairs where {
111.41/75.99	add fmap (key,elt) = addToFM_C combiner fmap key elt;
111.41/75.99	} 
111.41/75.99	"
111.41/75.99	are unpacked to the following functions on top level
111.41/75.99	"addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;
111.41/75.99	"
111.41/75.99	The bindings of the following Let/Where expression
111.41/75.99	"let {
111.41/75.99	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
111.41/75.99	} in result where {
111.41/75.99	balance_ok  = True;
111.41/75.99	;
111.41/75.99	left_ok  = left_ok0 fm_l key fm_l;
111.41/75.99	;
111.41/75.99	left_ok0 fm_l key EmptyFM = True;
111.41/75.99	left_ok0 fm_l key (Branch left_key vz wu wv ww) = let {
111.41/75.99	biggest_left_key  = fst (findMax fm_l);
111.41/75.99	} in biggest_left_key < key;
111.41/75.99	;
111.41/75.99	left_size  = sizeFM fm_l;
111.41/75.99	;
111.41/75.99	right_ok  = right_ok0 fm_r key fm_r;
111.41/75.99	;
111.41/75.99	right_ok0 fm_r key EmptyFM = True;
111.41/75.99	right_ok0 fm_r key (Branch right_key wx wy wz xu) = let {
111.41/75.99	smallest_right_key  = fst (findMin fm_r);
111.41/75.99	} in key < smallest_right_key;
111.41/75.99	;
111.41/75.99	right_size  = sizeFM fm_r;
111.41/75.99	;
111.41/75.99	unbox x = x;
111.41/75.99	} 
111.41/75.99	"
111.41/75.99	are unpacked to the following functions on top level
111.41/75.99	"mkBranchLeft_size vxw vxx vxy = sizeFM vxw;
111.41/75.99	"
111.41/75.99	"mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
111.41/75.99	mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
111.41/75.99	"
111.41/75.99	"mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxx vxy vxx;
111.41/75.99	"
111.41/75.99	"mkBranchBalance_ok vxw vxx vxy = True;
111.41/75.99	"
111.41/75.99	"mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxy vxw;
111.41/75.99	"
111.41/75.99	"mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
111.41/75.99	mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r;
111.41/75.99	"
111.41/75.99	"mkBranchUnbox vxw vxx vxy x = x;
111.41/75.99	"
111.41/75.99	"mkBranchRight_size vxw vxx vxy = sizeFM vxx;
111.41/75.99	"
111.41/75.99	The bindings of the following Let/Where expression
111.41/75.99	"let {
111.41/75.99	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
111.41/75.99	} in result"
111.41/75.99	are unpacked to the following functions on top level
111.41/75.99	"mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vyw vxz (1 + mkBranchLeft_size vyv vyw vxz + mkBranchRight_size vyv vyw vxz)) vyv vyw;
111.41/75.99	"
111.41/75.99	The bindings of the following Let/Where expression
111.41/75.99	"let {
111.41/75.99	biggest_left_key  = fst (findMax fm_l);
111.41/75.99	} in biggest_left_key < key"
111.41/75.99	are unpacked to the following functions on top level
111.41/75.99	"mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);
111.41/75.99	"
111.41/75.99	The bindings of the following Let/Where expression
111.41/75.99	"let {
111.41/75.99	smallest_right_key  = fst (findMin fm_r);
111.41/75.99	} in key < smallest_right_key"
111.41/75.99	are unpacked to the following functions on top level
111.41/75.99	"mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);
111.41/75.99	"
111.41/75.99	
111.41/75.99	----------------------------------------
111.41/75.99	
111.41/75.99	(10)
111.41/75.99	Obligation:
111.41/75.99	mainModule Main 
111.41/75.99	module FiniteMap where {
111.41/75.99	import qualified Main;
111.41/75.99	import qualified Maybe;
111.41/75.99	import qualified Prelude;
111.41/75.99	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
111.41/75.99	
111.41/75.99	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
111.41/75.99	}
111.41/75.99	addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
111.41/75.99	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
111.41/75.99	
111.41/75.99	addListToFM0 old new = new;
111.41/75.99	
111.41/75.99	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
111.41/75.99	addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs;
111.41/75.99	
111.41/75.99	addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;
111.41/75.99	
111.41/75.99	addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
111.41/75.99	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
111.41/75.99	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
111.41/75.99	
111.41/75.99	addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
111.41/75.99	
111.41/75.99	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
111.41/75.99	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
111.41/75.99	
111.41/75.99	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
111.41/75.99	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
111.41/75.99	
111.41/75.99	addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
111.41/75.99	
111.41/75.99	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
111.41/75.99	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
111.41/75.99	
111.41/75.99	emptyFM :: FiniteMap b a;
111.41/75.99	emptyFM = EmptyFM;
111.41/75.99	
111.41/75.99	findMax :: FiniteMap a b  ->  (a,b);
111.41/75.99	findMax (Branch key elt xv xw EmptyFM) = (key,elt);
111.41/75.99	findMax (Branch key elt xx xy fm_r) = findMax fm_r;
111.41/75.99	
111.41/75.99	findMin :: FiniteMap a b  ->  (a,b);
111.41/75.99	findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
111.41/75.99	findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;
111.41/75.99	
111.41/75.99	listToFM :: Ord a => [(a,b)]  ->  FiniteMap a b;
111.41/75.99	listToFM = addListToFM emptyFM;
111.41/75.99	
111.41/75.99	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
111.41/75.99	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < 2);
111.41/75.99	
111.41/75.99	mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vwx vwy fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
111.41/75.99	
111.41/75.99	mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vwx vwy fm_lrr fm_r);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
111.41/75.99	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
111.41/75.99	mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu);
111.41/75.99	
111.41/75.99	mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwx vwy fm_l fm_rl) fm_rr;
111.41/75.99	
111.41/75.99	mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwx vwy fm_lr fm_r);
111.41/75.99	
111.41/75.99	mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vxu;
111.41/75.99	
111.41/75.99	mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vwz;
111.41/75.99	
111.41/75.99	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
111.41/75.99	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
111.41/75.99	
111.41/75.99	mkBranchBalance_ok vxw vxx vxy = True;
111.41/75.99	
111.41/75.99	mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxy vxw;
111.41/75.99	
111.41/75.99	mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
111.41/75.99	mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
111.41/75.99	
111.41/75.99	mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);
111.41/75.99	
111.41/75.99	mkBranchLeft_size vxw vxx vxy = sizeFM vxw;
111.41/75.99	
111.41/75.99	mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vyw vxz (1 + mkBranchLeft_size vyv vyw vxz + mkBranchRight_size vyv vyw vxz)) vyv vyw;
111.41/75.99	
111.41/75.99	mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxx vxy vxx;
111.41/75.99	
111.41/75.99	mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
111.41/75.99	mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r;
111.41/75.99	
111.41/75.99	mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);
111.41/75.99	
111.41/75.99	mkBranchRight_size vxw vxx vxy = sizeFM vxx;
111.41/75.99	
111.41/75.99	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
111.41/75.99	mkBranchUnbox vxw vxx vxy x = x;
111.41/75.99	
111.41/75.99	sIZE_RATIO :: Int;
111.41/75.99	sIZE_RATIO = 5;
111.41/75.99	
111.41/75.99	sizeFM :: FiniteMap a b  ->  Int;
111.41/75.99	sizeFM EmptyFM = 0;
111.41/75.99	sizeFM (Branch zz vuu size vuv vuw) = size;
111.41/75.99	
111.41/75.99	unitFM :: b  ->  a  ->  FiniteMap b a;
111.41/75.99	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
111.41/75.99	
111.41/75.99	}
111.41/75.99	module Maybe where {
111.41/75.99	import qualified FiniteMap;
111.41/75.99	import qualified Main;
111.41/75.99	import qualified Prelude;
111.41/75.99	}
111.41/75.99	module Main where {
111.41/75.99	import qualified FiniteMap;
111.41/75.99	import qualified Maybe;
111.41/75.99	import qualified Prelude;
111.41/75.99	}
111.41/75.99	
111.41/75.99	----------------------------------------
111.41/75.99	
111.41/75.99	(11) NumRed (SOUND)
111.41/75.99	Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
111.41/75.99	----------------------------------------
111.41/75.99	
111.41/75.99	(12)
111.41/75.99	Obligation:
111.41/75.99	mainModule Main 
111.41/75.99	module FiniteMap where {
111.41/75.99	import qualified Main;
111.41/75.99	import qualified Maybe;
111.41/75.99	import qualified Prelude;
111.41/75.99	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
111.41/75.99	
111.41/75.99	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
111.41/75.99	}
111.41/75.99	addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
111.41/75.99	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
111.41/75.99	
111.41/75.99	addListToFM0 old new = new;
111.41/75.99	
111.41/75.99	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
111.41/75.99	addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs;
111.41/75.99	
111.41/75.99	addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;
111.41/75.99	
111.41/75.99	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
111.41/75.99	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
111.41/75.99	addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt;
111.41/75.99	
111.41/75.99	addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt True = Branch new_key (combiner elt new_elt) size fm_l fm_r;
111.41/75.99	
111.41/75.99	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt);
111.41/75.99	addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C0 combiner key elt size fm_l fm_r new_key new_elt otherwise;
111.41/75.99	
111.41/75.99	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt True = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r;
111.41/75.99	addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt False = addToFM_C1 combiner key elt size fm_l fm_r new_key new_elt (new_key > key);
111.41/75.99	
111.41/75.99	addToFM_C3 combiner (Branch key elt size fm_l fm_r) new_key new_elt = addToFM_C2 combiner key elt size fm_l fm_r new_key new_elt (new_key < key);
111.41/75.99	
111.41/75.99	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
111.41/75.99	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
111.41/75.99	
111.41/75.99	emptyFM :: FiniteMap a b;
111.41/75.99	emptyFM = EmptyFM;
111.41/75.99	
111.41/75.99	findMax :: FiniteMap a b  ->  (a,b);
111.41/75.99	findMax (Branch key elt xv xw EmptyFM) = (key,elt);
111.41/75.99	findMax (Branch key elt xx xy fm_r) = findMax fm_r;
111.41/75.99	
111.41/75.99	findMin :: FiniteMap b a  ->  (b,a);
111.41/75.99	findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
111.41/75.99	findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;
111.41/75.99	
111.41/75.99	listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
111.41/75.99	listToFM = addListToFM emptyFM;
111.41/75.99	
111.41/75.99	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
111.41/75.99	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < Pos (Succ (Succ Zero)));
111.41/75.99	
111.41/75.99	mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ Zero)))))) key_rl elt_rl (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))) vwx vwy fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr);
111.41/75.99	
111.41/75.99	mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))) key_lr elt_lr (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))) key_l elt_l fm_ll fm_lrl) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))))) vwx vwy fm_lrr fm_r);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
111.41/75.99	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
111.41/75.99	mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu);
111.41/75.99	
111.41/75.99	mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
111.41/75.99	mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu);
111.41/75.99	
111.41/75.99	mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) vwx vwy fm_l fm_rl) fm_rr;
111.41/75.99	
111.41/75.99	mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))) key_l elt_l fm_ll (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))) vwx vwy fm_lr fm_r);
111.41/75.99	
111.41/75.99	mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vxu;
111.41/75.99	
111.41/75.99	mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vwz;
111.41/75.99	
111.41/75.99	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
111.41/75.99	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
111.41/75.99	
111.41/75.99	mkBranchBalance_ok vxw vxx vxy = True;
111.41/75.99	
111.41/75.99	mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxy vxw;
111.41/75.99	
111.41/75.99	mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
111.41/75.99	mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
111.41/75.99	
111.41/75.99	mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);
111.41/75.99	
111.41/75.99	mkBranchLeft_size vxw vxx vxy = sizeFM vxw;
111.41/75.99	
111.41/75.99	mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vyw vxz (Pos (Succ Zero) + mkBranchLeft_size vyv vyw vxz + mkBranchRight_size vyv vyw vxz)) vyv vyw;
111.41/75.99	
111.41/75.99	mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxx vxy vxx;
111.41/75.99	
111.41/75.99	mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
111.41/75.99	mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r;
111.41/75.99	
111.41/75.99	mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);
111.41/75.99	
111.41/75.99	mkBranchRight_size vxw vxx vxy = sizeFM vxx;
111.41/75.99	
111.41/75.99	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
111.41/75.99	mkBranchUnbox vxw vxx vxy x = x;
111.41/75.99	
111.41/75.99	sIZE_RATIO :: Int;
111.41/75.99	sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero)))));
111.41/75.99	
111.41/75.99	sizeFM :: FiniteMap b a  ->  Int;
111.41/75.99	sizeFM EmptyFM = Pos Zero;
111.41/75.99	sizeFM (Branch zz vuu size vuv vuw) = size;
111.41/75.99	
111.41/75.99	unitFM :: b  ->  a  ->  FiniteMap b a;
111.41/75.99	unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM;
111.41/75.99	
111.41/75.99	}
111.41/75.99	module Maybe where {
111.41/75.99	import qualified FiniteMap;
111.41/75.99	import qualified Main;
111.41/75.99	import qualified Prelude;
111.41/75.99	}
111.41/75.99	module Main where {
111.41/75.99	import qualified FiniteMap;
111.41/75.99	import qualified Maybe;
111.41/75.99	import qualified Prelude;
111.41/75.99	}
111.41/76.04	EOF