10.36/4.51	YES
12.77/5.17	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
12.77/5.17	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.77/5.17	
12.77/5.17	
12.77/5.17	H-Termination with start terms of the given HASKELL could be proven:
12.77/5.17	
12.77/5.17	(0) HASKELL
12.77/5.17	(1) LR [EQUIVALENT, 0 ms]
12.77/5.17	(2) HASKELL
12.77/5.17	(3) CR [EQUIVALENT, 0 ms]
12.77/5.17	(4) HASKELL
12.77/5.17	(5) BR [EQUIVALENT, 0 ms]
12.77/5.17	(6) HASKELL
12.77/5.17	(7) COR [EQUIVALENT, 19 ms]
12.77/5.17	(8) HASKELL
12.77/5.17	(9) LetRed [EQUIVALENT, 0 ms]
12.77/5.17	(10) HASKELL
12.77/5.17	(11) NumRed [SOUND, 0 ms]
12.77/5.17	(12) HASKELL
12.77/5.17	(13) Narrow [SOUND, 0 ms]
12.77/5.17	(14) QDP
12.77/5.17	(15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
12.77/5.17	(16) YES
12.77/5.17	
12.77/5.17	
12.77/5.17	----------------------------------------
12.77/5.17	
12.77/5.17	(0)
12.77/5.17	Obligation:
12.77/5.17	mainModule Main 
12.77/5.17	module FiniteMap where {
12.77/5.17	import qualified Main;
12.77/5.17	import qualified Maybe;
12.77/5.17	import qualified Prelude;
12.77/5.17	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
12.77/5.17	
12.77/5.17	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
12.77/5.17	}
12.77/5.17	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
12.77/5.17	addListToFM fm key_elt_pairs = addListToFM_C (\old new ->new) fm key_elt_pairs;
12.77/5.17	
12.77/5.17	addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
12.77/5.17	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
12.77/5.17	add fmap (key,elt) = addToFM_C combiner fmap key elt;
12.77/5.17	 };
12.77/5.17	
12.77/5.17	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
12.77/5.17	addToFM_C combiner EmptyFM key elt = unitFM key elt;
12.77/5.17	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
12.77/5.17	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
12.77/5.17	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
12.77/5.17	
12.77/5.17	emptyFM :: FiniteMap a b;
12.77/5.17	emptyFM = EmptyFM;
12.77/5.17	
12.77/5.17	findMax :: FiniteMap a b  ->  (a,b);
12.77/5.17	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
12.77/5.17	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
12.77/5.17	
12.77/5.17	findMin :: FiniteMap b a  ->  (b,a);
12.77/5.17	findMin (Branch key elt _ EmptyFM _) = (key,elt);
12.77/5.17	findMin (Branch key elt _ fm_l _) = findMin fm_l;
12.77/5.17	
12.77/5.17	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
12.77/5.17	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
12.77/5.17	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
12.77/5.17	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
12.77/5.17	 | otherwise -> double_L fm_L fm_R; 
12.77/5.17	 } 
12.77/5.17	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
12.77/5.17	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
12.77/5.17	 | otherwise -> double_R fm_L fm_R; 
12.77/5.17	 } 
12.77/5.17	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
12.77/5.17	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);
12.77/5.17	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);
12.77/5.17	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;
12.77/5.18	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);
12.77/5.18	size_l = sizeFM fm_L;
12.77/5.18	size_r = sizeFM fm_R;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
12.77/5.18	mkBranch which key elt fm_l fm_r = let { 
12.77/5.18	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
12.77/5.18	} in result where { 
12.77/5.18	balance_ok = True;
12.77/5.18	left_ok = case fm_l of { 
12.77/5.18	EmptyFM-> True; 
12.77/5.18	Branch left_key _ _ _ _-> let { 
12.77/5.18	biggest_left_key = fst (findMax fm_l);
12.77/5.18	} in biggest_left_key < key; 
12.77/5.18	 } ;
12.77/5.18	left_size = sizeFM fm_l;
12.77/5.18	right_ok = case fm_r of { 
12.77/5.18	EmptyFM-> True; 
12.77/5.18	Branch right_key _ _ _ _-> let { 
12.77/5.18	smallest_right_key = fst (findMin fm_r);
12.77/5.18	} in key < smallest_right_key; 
12.77/5.18	 } ;
12.77/5.18	right_size = sizeFM fm_r;
12.77/5.18	unbox :: Int  ->  Int;
12.77/5.18	unbox x = x;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	sIZE_RATIO :: Int;
12.77/5.18	sIZE_RATIO = 5;
12.77/5.18	
12.77/5.18	sizeFM :: FiniteMap a b  ->  Int;
12.77/5.18	sizeFM EmptyFM = 0;
12.77/5.18	sizeFM (Branch _ _ size _ _) = size;
12.77/5.18	
12.77/5.18	unitFM :: b  ->  a  ->  FiniteMap b a;
12.77/5.18	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
12.77/5.18	
12.77/5.18	}
12.77/5.18	module Maybe where {
12.77/5.18	import qualified FiniteMap;
12.77/5.18	import qualified Main;
12.77/5.18	import qualified Prelude;
12.77/5.18	}
12.77/5.18	module Main where {
12.77/5.18	import qualified FiniteMap;
12.77/5.18	import qualified Maybe;
12.77/5.18	import qualified Prelude;
12.77/5.18	}
12.77/5.18	
12.77/5.18	----------------------------------------
12.77/5.18	
12.77/5.18	(1) LR (EQUIVALENT)
12.77/5.18	Lambda Reductions:
12.77/5.18	The following Lambda expression
12.77/5.18	"\oldnew->new"
12.77/5.18	is transformed to
12.77/5.18	"addListToFM0 old new = new;
12.77/5.18	"
12.77/5.18	
12.77/5.18	----------------------------------------
12.77/5.18	
12.77/5.18	(2)
12.77/5.18	Obligation:
12.77/5.18	mainModule Main 
12.77/5.18	module FiniteMap where {
12.77/5.18	import qualified Main;
12.77/5.18	import qualified Maybe;
12.77/5.18	import qualified Prelude;
12.77/5.18	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
12.77/5.18	
12.77/5.18	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
12.77/5.18	}
12.77/5.18	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
12.77/5.18	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
12.77/5.18	
12.77/5.18	addListToFM0 old new = new;
12.77/5.18	
12.77/5.18	addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
12.77/5.18	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
12.77/5.18	add fmap (key,elt) = addToFM_C combiner fmap key elt;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
12.77/5.18	addToFM_C combiner EmptyFM key elt = unitFM key elt;
12.77/5.18	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
12.77/5.18	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
12.77/5.18	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
12.77/5.18	
12.77/5.18	emptyFM :: FiniteMap a b;
12.77/5.18	emptyFM = EmptyFM;
12.77/5.18	
12.77/5.18	findMax :: FiniteMap b a  ->  (b,a);
12.77/5.18	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
12.77/5.18	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
12.77/5.18	
12.77/5.18	findMin :: FiniteMap a b  ->  (a,b);
12.77/5.18	findMin (Branch key elt _ EmptyFM _) = (key,elt);
12.77/5.18	findMin (Branch key elt _ fm_l _) = findMin fm_l;
12.77/5.18	
12.77/5.18	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
12.77/5.18	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
12.77/5.18	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
12.77/5.18	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
12.77/5.18	 | otherwise -> double_L fm_L fm_R; 
12.77/5.18	 } 
12.77/5.18	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
12.77/5.18	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
12.77/5.18	 | otherwise -> double_R fm_L fm_R; 
12.77/5.18	 } 
12.77/5.18	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
12.77/5.18	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);
12.77/5.18	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);
12.77/5.18	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;
12.77/5.18	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);
12.77/5.18	size_l = sizeFM fm_L;
12.77/5.18	size_r = sizeFM fm_R;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
12.77/5.18	mkBranch which key elt fm_l fm_r = let { 
12.77/5.18	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
12.77/5.18	} in result where { 
12.77/5.18	balance_ok = True;
12.77/5.18	left_ok = case fm_l of { 
12.77/5.18	EmptyFM-> True; 
12.77/5.18	Branch left_key _ _ _ _-> let { 
12.77/5.18	biggest_left_key = fst (findMax fm_l);
12.77/5.18	} in biggest_left_key < key; 
12.77/5.18	 } ;
12.77/5.18	left_size = sizeFM fm_l;
12.77/5.18	right_ok = case fm_r of { 
12.77/5.18	EmptyFM-> True; 
12.77/5.18	Branch right_key _ _ _ _-> let { 
12.77/5.18	smallest_right_key = fst (findMin fm_r);
12.77/5.18	} in key < smallest_right_key; 
12.77/5.18	 } ;
12.77/5.18	right_size = sizeFM fm_r;
12.77/5.18	unbox :: Int  ->  Int;
12.77/5.18	unbox x = x;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	sIZE_RATIO :: Int;
12.77/5.18	sIZE_RATIO = 5;
12.77/5.18	
12.77/5.18	sizeFM :: FiniteMap b a  ->  Int;
12.77/5.18	sizeFM EmptyFM = 0;
12.77/5.18	sizeFM (Branch _ _ size _ _) = size;
12.77/5.18	
12.77/5.18	unitFM :: a  ->  b  ->  FiniteMap a b;
12.77/5.18	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
12.77/5.18	
12.77/5.18	}
12.77/5.18	module Maybe where {
12.77/5.18	import qualified FiniteMap;
12.77/5.18	import qualified Main;
12.77/5.18	import qualified Prelude;
12.77/5.18	}
12.77/5.18	module Main where {
12.77/5.18	import qualified FiniteMap;
12.77/5.18	import qualified Maybe;
12.77/5.18	import qualified Prelude;
12.77/5.18	}
12.77/5.18	
12.77/5.18	----------------------------------------
12.77/5.18	
12.77/5.18	(3) CR (EQUIVALENT)
12.77/5.18	Case Reductions:
12.77/5.18	The following Case expression
12.77/5.18	"case fm_r of {
12.77/5.18	EmptyFM  -> True;
12.77/5.18	Branch right_key _ _ _ _  -> let {
12.77/5.18	smallest_right_key  = fst (findMin fm_r);
12.77/5.18	} in key < smallest_right_key}
12.77/5.18	"
12.77/5.18	is transformed to
12.77/5.18	"right_ok0 fm_r key EmptyFM = True;
12.77/5.18	right_ok0 fm_r key (Branch right_key _ _ _ _) = let {
12.77/5.18	smallest_right_key  = fst (findMin fm_r);
12.77/5.18	} in key < smallest_right_key;
12.77/5.18	"
12.77/5.18	The following Case expression
12.77/5.18	"case fm_l of {
12.77/5.18	EmptyFM  -> True;
12.77/5.18	Branch left_key _ _ _ _  -> let {
12.77/5.18	biggest_left_key  = fst (findMax fm_l);
12.77/5.18	} in biggest_left_key < key}
12.77/5.18	"
12.77/5.18	is transformed to
12.77/5.18	"left_ok0 fm_l key EmptyFM = True;
12.77/5.18	left_ok0 fm_l key (Branch left_key _ _ _ _) = let {
12.77/5.18	biggest_left_key  = fst (findMax fm_l);
12.77/5.18	} in biggest_left_key < key;
12.77/5.18	"
12.77/5.18	The following Case expression
12.77/5.18	"case fm_R of {
12.77/5.18	Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R}
12.77/5.18	"
12.77/5.18	is transformed to
12.77/5.18	"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;
12.77/5.18	"
12.77/5.18	The following Case expression
12.77/5.18	"case fm_L of {
12.77/5.18	Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R}
12.77/5.18	"
12.77/5.18	is transformed to
12.77/5.18	"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;
12.77/5.18	"
12.77/5.18	
12.77/5.18	----------------------------------------
12.77/5.18	
12.77/5.18	(4)
12.77/5.18	Obligation:
12.77/5.18	mainModule Main 
12.77/5.18	module FiniteMap where {
12.77/5.18	import qualified Main;
12.77/5.18	import qualified Maybe;
12.77/5.18	import qualified Prelude;
12.77/5.18	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
12.77/5.18	
12.77/5.18	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
12.77/5.18	}
12.77/5.18	addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
12.77/5.18	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
12.77/5.18	
12.77/5.18	addListToFM0 old new = new;
12.77/5.18	
12.77/5.18	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
12.77/5.18	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
12.77/5.18	add fmap (key,elt) = addToFM_C combiner fmap key elt;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
12.77/5.18	addToFM_C combiner EmptyFM key elt = unitFM key elt;
12.77/5.18	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
12.77/5.18	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
12.77/5.18	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
12.77/5.18	
12.77/5.18	emptyFM :: FiniteMap a b;
12.77/5.18	emptyFM = EmptyFM;
12.77/5.18	
12.77/5.18	findMax :: FiniteMap a b  ->  (a,b);
12.77/5.18	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
12.77/5.18	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
12.77/5.18	
12.77/5.18	findMin :: FiniteMap a b  ->  (a,b);
12.77/5.18	findMin (Branch key elt _ EmptyFM _) = (key,elt);
12.77/5.18	findMin (Branch key elt _ fm_l _) = findMin fm_l;
12.77/5.18	
12.77/5.18	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
12.77/5.18	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
12.77/5.18	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
12.77/5.18	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
12.77/5.18	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
12.77/5.18	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);
12.77/5.18	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);
12.77/5.18	mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
12.77/5.18	 | otherwise = double_L fm_L fm_R;
12.77/5.18	mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
12.77/5.18	 | otherwise = double_R fm_L fm_R;
12.77/5.18	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;
12.77/5.18	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);
12.77/5.18	size_l = sizeFM fm_L;
12.77/5.18	size_r = sizeFM fm_R;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
12.77/5.18	mkBranch which key elt fm_l fm_r = let { 
12.77/5.18	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
12.77/5.18	} in result where { 
12.77/5.18	balance_ok = True;
12.77/5.18	left_ok = left_ok0 fm_l key fm_l;
12.77/5.18	left_ok0 fm_l key EmptyFM = True;
12.77/5.18	left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
12.77/5.18	biggest_left_key = fst (findMax fm_l);
12.77/5.18	} in biggest_left_key < key;
12.77/5.18	left_size = sizeFM fm_l;
12.77/5.18	right_ok = right_ok0 fm_r key fm_r;
12.77/5.18	right_ok0 fm_r key EmptyFM = True;
12.77/5.18	right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
12.77/5.18	smallest_right_key = fst (findMin fm_r);
12.77/5.18	} in key < smallest_right_key;
12.77/5.18	right_size = sizeFM fm_r;
12.77/5.18	unbox :: Int  ->  Int;
12.77/5.18	unbox x = x;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	sIZE_RATIO :: Int;
12.77/5.18	sIZE_RATIO = 5;
12.77/5.18	
12.77/5.18	sizeFM :: FiniteMap b a  ->  Int;
12.77/5.18	sizeFM EmptyFM = 0;
12.77/5.18	sizeFM (Branch _ _ size _ _) = size;
12.77/5.18	
12.77/5.18	unitFM :: a  ->  b  ->  FiniteMap a b;
12.77/5.18	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
12.77/5.18	
12.77/5.18	}
12.77/5.18	module Maybe where {
12.77/5.18	import qualified FiniteMap;
12.77/5.18	import qualified Main;
12.77/5.18	import qualified Prelude;
12.77/5.18	}
12.77/5.18	module Main where {
12.77/5.18	import qualified FiniteMap;
12.77/5.18	import qualified Maybe;
12.77/5.18	import qualified Prelude;
12.77/5.18	}
12.77/5.18	
12.77/5.18	----------------------------------------
12.77/5.18	
12.77/5.18	(5) BR (EQUIVALENT)
12.77/5.18	Replaced joker patterns by fresh variables and removed binding patterns.
12.77/5.18	----------------------------------------
12.77/5.18	
12.77/5.18	(6)
12.77/5.18	Obligation:
12.77/5.18	mainModule Main 
12.77/5.18	module FiniteMap where {
12.77/5.18	import qualified Main;
12.77/5.18	import qualified Maybe;
12.77/5.18	import qualified Prelude;
12.77/5.18	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
12.77/5.18	
12.77/5.18	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
12.77/5.18	}
12.77/5.18	addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
12.77/5.18	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
12.77/5.18	
12.77/5.18	addListToFM0 old new = new;
12.77/5.18	
12.77/5.18	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
12.77/5.18	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
12.77/5.18	add fmap (key,elt) = addToFM_C combiner fmap key elt;
12.77/5.18	 };
12.77/5.18	
12.77/5.18	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
12.77/5.18	addToFM_C combiner EmptyFM key elt = unitFM key elt;
12.77/5.18	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
12.77/5.18	 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
12.77/5.18	 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;
12.77/5.18	
12.77/5.18	emptyFM :: FiniteMap a b;
12.77/5.18	emptyFM = EmptyFM;
12.77/5.18	
12.77/5.18	findMax :: FiniteMap a b  ->  (a,b);
12.77/5.18	findMax (Branch key elt yx yy EmptyFM) = (key,elt);
12.77/5.18	findMax (Branch key elt yz zu fm_r) = findMax fm_r;
12.77/5.18	
12.77/5.18	findMin :: FiniteMap b a  ->  (b,a);
12.77/5.18	findMin (Branch key elt wx EmptyFM wy) = (key,elt);
12.77/5.18	findMin (Branch key elt wz fm_l xu) = findMin fm_l;
12.77/5.18	
12.77/5.18	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
12.77/5.18	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
12.77/5.18	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
12.77/5.18	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
12.77/5.18	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
12.77/5.18	double_L fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
12.77/5.18	double_R (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
12.77/5.18	mkBalBranch0 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
12.77/5.18	 | otherwise = double_L fm_L fm_R;
12.77/5.18	mkBalBranch1 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
12.77/5.18	 | otherwise = double_R fm_L fm_R;
12.77/5.18	single_L fm_l (Branch key_r elt_r vvu fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
12.77/5.18	single_R (Branch key_l elt_l zv fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
13.17/5.32	size_l = sizeFM fm_L;
13.17/5.32	size_r = sizeFM fm_R;
13.17/5.32	 };
13.17/5.32	
13.17/5.32	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
13.17/5.32	mkBranch which key elt fm_l fm_r = let { 
13.17/5.32	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
13.17/5.32	} in result where { 
13.17/5.32	balance_ok = True;
13.17/5.32	left_ok = left_ok0 fm_l key fm_l;
13.17/5.32	left_ok0 fm_l key EmptyFM = True;
13.17/5.32	left_ok0 fm_l key (Branch left_key xv xw xx xy) = let { 
13.17/5.32	biggest_left_key = fst (findMax fm_l);
13.17/5.32	} in biggest_left_key < key;
13.17/5.32	left_size = sizeFM fm_l;
13.17/5.32	right_ok = right_ok0 fm_r key fm_r;
13.17/5.32	right_ok0 fm_r key EmptyFM = True;
13.17/5.32	right_ok0 fm_r key (Branch right_key xz yu yv yw) = let { 
13.17/5.32	smallest_right_key = fst (findMin fm_r);
13.17/5.32	} in key < smallest_right_key;
13.17/5.32	right_size = sizeFM fm_r;
13.17/5.32	unbox :: Int  ->  Int;
13.17/5.32	unbox x = x;
13.17/5.32	 };
13.17/5.32	
13.17/5.32	sIZE_RATIO :: Int;
13.17/5.32	sIZE_RATIO = 5;
13.17/5.32	
13.17/5.32	sizeFM :: FiniteMap b a  ->  Int;
13.17/5.32	sizeFM EmptyFM = 0;
13.17/5.32	sizeFM (Branch vz wu size wv ww) = size;
13.17/5.32	
13.17/5.32	unitFM :: a  ->  b  ->  FiniteMap a b;
13.17/5.32	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
13.17/5.32	
13.17/5.32	}
13.17/5.32	module Maybe where {
13.17/5.32	import qualified FiniteMap;
13.17/5.32	import qualified Main;
13.17/5.32	import qualified Prelude;
13.17/5.32	}
13.17/5.32	module Main where {
13.17/5.32	import qualified FiniteMap;
13.17/5.32	import qualified Maybe;
13.17/5.32	import qualified Prelude;
13.17/5.32	}
13.17/5.32	
13.17/5.32	----------------------------------------
13.17/5.32	
13.17/5.32	(7) COR (EQUIVALENT)
13.17/5.32	Cond Reductions:
13.17/5.32	The following Function with conditions
13.17/5.32	"undefined |Falseundefined;
13.17/5.32	"
13.17/5.32	is transformed to
13.17/5.32	"undefined  = undefined1;
13.17/5.32	"
13.17/5.32	"undefined0 True = undefined;
13.17/5.32	"
13.17/5.32	"undefined1  = undefined0 False;
13.17/5.32	"
13.17/5.32	The following Function with conditions
13.17/5.32	"addToFM_C combiner EmptyFM key elt = unitFM key elt;
13.17/5.32	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;
13.17/5.32	"
13.17/5.32	is transformed to
13.17/5.32	"addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
13.17/5.32	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;
13.17/5.32	"
13.17/5.32	"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;
13.17/5.32	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);
13.17/5.32	"
13.17/5.32	"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;
13.17/5.32	"
13.17/5.32	"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);
13.17/5.32	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;
13.17/5.32	"
13.17/5.32	"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);
13.17/5.32	"
13.17/5.32	"addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
13.17/5.32	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
13.17/5.32	"
13.17/5.32	The following Function with conditions
13.17/5.32	"mkBalBranch1 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
13.17/5.32	"
13.17/5.32	is transformed to
13.17/5.32	"mkBalBranch1 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr);
13.17/5.32	"
13.17/5.32	"mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr True = single_R fm_L fm_R;
13.17/5.32	mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr False = mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr otherwise;
13.17/5.32	"
13.17/5.32	"mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr True = double_R fm_L fm_R;
13.17/5.32	"
13.17/5.32	"mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
13.17/5.32	"
13.17/5.32	The following Function with conditions
13.17/5.32	"mkBalBranch0 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
13.17/5.32	"
13.17/5.32	is transformed to
13.17/5.32	"mkBalBranch0 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr);
13.17/5.32	"
13.17/5.32	"mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr True = single_L fm_L fm_R;
13.17/5.32	mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr otherwise;
13.17/5.32	"
13.17/5.32	"mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr True = double_L fm_L fm_R;
13.17/5.32	"
13.17/5.32	"mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
13.17/5.32	"
13.17/5.32	The following Function with conditions
13.17/5.32	"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 {
13.17/5.32	double_L fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
13.17/5.32	;
13.17/5.32	double_R (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
13.17/5.32	;
13.17/5.32	mkBalBranch0 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
13.17/5.32	;
13.17/5.32	mkBalBranch1 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
13.17/5.32	;
13.17/5.32	single_L fm_l (Branch key_r elt_r vvu fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
13.17/5.32	;
13.17/5.32	single_R (Branch key_l elt_l zv fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
13.17/5.32	;
13.17/5.32	size_l  = sizeFM fm_L;
13.17/5.32	;
13.17/5.32	size_r  = sizeFM fm_R;
13.17/5.32	} 
13.17/5.32	;
13.17/5.32	"
13.17/5.32	is transformed to
13.17/5.32	"mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
13.17/5.32	"
13.17/5.32	"mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
13.17/5.32	double_L fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
13.17/5.32	;
13.17/5.32	double_R (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
13.17/5.32	;
13.17/5.32	mkBalBranch0 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr);
13.17/5.32	;
13.17/5.32	mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr True = double_L fm_L fm_R;
13.17/5.32	;
13.17/5.32	mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr True = single_L fm_L fm_R;
13.17/5.32	mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr otherwise;
13.17/5.32	;
13.17/5.32	mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
13.17/5.32	;
13.17/5.32	mkBalBranch1 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr);
13.17/5.32	;
13.17/5.32	mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr True = double_R fm_L fm_R;
13.17/5.32	;
13.17/5.32	mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr True = single_R fm_L fm_R;
13.17/5.32	mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr False = mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr otherwise;
13.17/5.32	;
13.17/5.32	mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
13.17/5.32	;
13.17/5.32	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
13.17/5.32	;
13.17/5.32	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
13.17/5.32	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
13.17/5.32	;
13.17/5.32	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
13.17/5.32	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
13.17/5.32	;
13.17/5.32	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
13.17/5.32	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
13.17/5.32	;
13.17/5.32	single_L fm_l (Branch key_r elt_r vvu fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
13.17/5.32	;
13.17/5.32	single_R (Branch key_l elt_l zv fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
13.17/5.32	;
13.17/5.32	size_l  = sizeFM fm_L;
13.17/5.32	;
13.17/5.32	size_r  = sizeFM fm_R;
13.71/5.43	} 
13.71/5.43	;
13.71/5.43	"
13.71/5.43	
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(8)
13.71/5.43	Obligation:
13.71/5.43	mainModule Main 
13.71/5.43	module FiniteMap where {
13.71/5.43	import qualified Main;
13.71/5.43	import qualified Maybe;
13.71/5.43	import qualified Prelude;
13.71/5.43	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
13.71/5.43	
13.71/5.43	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
13.71/5.43	}
13.71/5.43	addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
13.71/5.43	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
13.71/5.43	
13.71/5.43	addListToFM0 old new = new;
13.71/5.43	
13.71/5.43	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
13.71/5.43	addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
13.71/5.43	add fmap (key,elt) = addToFM_C combiner fmap key elt;
13.71/5.43	 };
13.71/5.43	
13.71/5.43	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
13.71/5.43	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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);
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	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);
13.71/5.43	
13.71/5.43	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);
13.71/5.43	
13.71/5.43	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
13.71/5.43	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
13.71/5.43	
13.71/5.43	emptyFM :: FiniteMap a b;
13.71/5.43	emptyFM = EmptyFM;
13.71/5.43	
13.71/5.43	findMax :: FiniteMap b a  ->  (b,a);
13.71/5.43	findMax (Branch key elt yx yy EmptyFM) = (key,elt);
13.71/5.43	findMax (Branch key elt yz zu fm_r) = findMax fm_r;
13.71/5.43	
13.71/5.43	findMin :: FiniteMap b a  ->  (b,a);
13.71/5.43	findMin (Branch key elt wx EmptyFM wy) = (key,elt);
13.71/5.43	findMin (Branch key elt wz fm_l xu) = findMin fm_l;
13.71/5.43	
13.71/5.43	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
13.71/5.43	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 
13.71/5.43	double_L fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
13.71/5.43	double_R (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
13.71/5.43	mkBalBranch0 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr);
13.71/5.43	mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr True = double_L fm_L fm_R;
13.71/5.43	mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr True = single_L fm_L fm_R;
13.71/5.43	mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr otherwise;
13.71/5.43	mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
13.71/5.43	mkBalBranch1 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr);
13.71/5.43	mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr True = double_R fm_L fm_R;
13.71/5.43	mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr True = single_R fm_L fm_R;
13.71/5.43	mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr False = mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr otherwise;
13.71/5.43	mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
13.71/5.43	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
13.71/5.43	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
13.71/5.43	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
13.71/5.43	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
13.71/5.43	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
13.71/5.43	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
13.71/5.43	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
13.71/5.43	single_L fm_l (Branch key_r elt_r vvu fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
13.71/5.43	single_R (Branch key_l elt_l zv fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
13.71/5.43	size_l = sizeFM fm_L;
13.71/5.43	size_r = sizeFM fm_R;
13.71/5.43	 };
13.71/5.43	
13.71/5.43	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
13.71/5.43	mkBranch which key elt fm_l fm_r = let { 
13.71/5.43	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
13.71/5.43	} in result where { 
13.71/5.43	balance_ok = True;
13.71/5.43	left_ok = left_ok0 fm_l key fm_l;
13.71/5.43	left_ok0 fm_l key EmptyFM = True;
13.71/5.43	left_ok0 fm_l key (Branch left_key xv xw xx xy) = let { 
13.71/5.43	biggest_left_key = fst (findMax fm_l);
13.71/5.43	} in biggest_left_key < key;
13.71/5.43	left_size = sizeFM fm_l;
13.71/5.43	right_ok = right_ok0 fm_r key fm_r;
13.71/5.43	right_ok0 fm_r key EmptyFM = True;
13.71/5.43	right_ok0 fm_r key (Branch right_key xz yu yv yw) = let { 
13.71/5.43	smallest_right_key = fst (findMin fm_r);
13.71/5.43	} in key < smallest_right_key;
13.71/5.43	right_size = sizeFM fm_r;
13.71/5.43	unbox :: Int  ->  Int;
13.71/5.43	unbox x = x;
13.71/5.43	 };
13.71/5.43	
13.71/5.43	sIZE_RATIO :: Int;
13.71/5.43	sIZE_RATIO = 5;
13.71/5.43	
13.71/5.43	sizeFM :: FiniteMap a b  ->  Int;
13.71/5.43	sizeFM EmptyFM = 0;
13.71/5.43	sizeFM (Branch vz wu size wv ww) = size;
13.71/5.43	
13.71/5.43	unitFM :: a  ->  b  ->  FiniteMap a b;
13.71/5.43	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
13.71/5.43	
13.71/5.43	}
13.71/5.43	module Maybe where {
13.71/5.43	import qualified FiniteMap;
13.71/5.43	import qualified Main;
13.71/5.43	import qualified Prelude;
13.71/5.43	}
13.71/5.43	module Main where {
13.71/5.43	import qualified FiniteMap;
13.71/5.43	import qualified Maybe;
13.71/5.43	import qualified Prelude;
13.71/5.43	}
13.71/5.43	
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(9) LetRed (EQUIVALENT)
13.71/5.43	Let/Where Reductions:
13.71/5.43	The bindings of the following Let/Where expression
13.71/5.43	"mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
13.71/5.43	double_L fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
13.71/5.43	;
13.71/5.43	double_R (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
13.71/5.43	;
13.71/5.43	mkBalBranch0 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr);
13.71/5.43	;
13.71/5.43	mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr True = double_L fm_L fm_R;
13.71/5.43	;
13.71/5.43	mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr True = single_L fm_L fm_R;
13.71/5.43	mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vux vuy vuz fm_rl fm_rr otherwise;
13.71/5.43	;
13.71/5.43	mkBalBranch02 fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vux vuy vuz fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
13.71/5.43	;
13.71/5.43	mkBalBranch1 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr);
13.71/5.43	;
13.71/5.43	mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr True = double_R fm_L fm_R;
13.71/5.43	;
13.71/5.43	mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr True = single_R fm_L fm_R;
13.71/5.43	mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr False = mkBalBranch10 fm_L fm_R zy zz vuu fm_ll fm_lr otherwise;
13.71/5.43	;
13.71/5.43	mkBalBranch12 fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch11 fm_L fm_R zy zz vuu fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
13.71/5.43	;
13.71/5.43	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
13.71/5.43	;
13.71/5.43	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
13.71/5.43	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
13.71/5.43	;
13.71/5.43	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
13.71/5.43	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
13.71/5.43	;
13.71/5.43	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
13.71/5.43	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
13.71/5.43	;
13.71/5.43	single_L fm_l (Branch key_r elt_r vvu fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
13.71/5.43	;
13.71/5.43	single_R (Branch key_l elt_l zv fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
13.71/5.43	;
13.71/5.43	size_l  = sizeFM fm_L;
13.71/5.43	;
13.71/5.43	size_r  = sizeFM fm_R;
13.71/5.43	} 
13.71/5.43	"
13.71/5.43	are unpacked to the following functions on top level
13.71/5.43	"mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r vvu fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwx vwy fm_l fm_rl) fm_rr;
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
13.71/5.43	"
13.71/5.43	"mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwz;
13.71/5.43	"
13.71/5.43	"mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr);
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr);
13.71/5.43	"
13.71/5.43	"mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vxu;
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr otherwise;
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
13.71/5.43	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);
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	"
13.71/5.43	"mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l zv fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwx vwy fm_lr fm_r);
13.71/5.43	"
13.71/5.43	"mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
13.71/5.43	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
13.71/5.43	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);
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr otherwise;
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
13.71/5.43	"
13.71/5.43	"mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
13.71/5.43	"
13.71/5.43	The bindings of the following Let/Where expression
13.71/5.43	"foldl add fm key_elt_pairs where {
13.71/5.43	add fmap (key,elt) = addToFM_C combiner fmap key elt;
13.71/5.43	} 
13.71/5.43	"
13.71/5.43	are unpacked to the following functions on top level
13.71/5.43	"addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;
13.71/5.43	"
13.71/5.43	The bindings of the following Let/Where expression
13.71/5.43	"let {
13.71/5.43	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
13.71/5.43	} in result where {
13.71/5.43	balance_ok  = True;
13.71/5.43	;
13.71/5.43	left_ok  = left_ok0 fm_l key fm_l;
13.71/5.43	;
13.71/5.43	left_ok0 fm_l key EmptyFM = True;
13.71/5.43	left_ok0 fm_l key (Branch left_key xv xw xx xy) = let {
13.71/5.43	biggest_left_key  = fst (findMax fm_l);
13.71/5.43	} in biggest_left_key < key;
13.71/5.43	;
13.71/5.43	left_size  = sizeFM fm_l;
13.71/5.43	;
13.71/5.43	right_ok  = right_ok0 fm_r key fm_r;
13.71/5.43	;
13.71/5.43	right_ok0 fm_r key EmptyFM = True;
13.71/5.43	right_ok0 fm_r key (Branch right_key xz yu yv yw) = let {
13.71/5.43	smallest_right_key  = fst (findMin fm_r);
13.71/5.43	} in key < smallest_right_key;
13.71/5.43	;
13.71/5.43	right_size  = sizeFM fm_r;
13.71/5.43	;
13.71/5.43	unbox x = x;
13.71/5.43	} 
13.71/5.43	"
13.71/5.43	are unpacked to the following functions on top level
13.71/5.43	"mkBranchLeft_size vxw vxx vxy = sizeFM vxw;
13.71/5.43	"
13.71/5.43	"mkBranchRight_size vxw vxx vxy = sizeFM vxx;
13.71/5.43	"
13.71/5.43	"mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
13.71/5.43	mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key xv xw xx xy) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
13.71/5.43	"
13.71/5.43	"mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
13.71/5.43	mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key xz yu yv yw) = key < mkBranchRight_ok0Smallest_right_key fm_r;
13.71/5.43	"
13.71/5.43	"mkBranchUnbox vxw vxx vxy x = x;
13.71/5.43	"
13.71/5.43	"mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxy vxw;
13.71/5.43	"
13.71/5.43	"mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxx vxy vxx;
13.71/5.43	"
13.71/5.43	"mkBranchBalance_ok vxw vxx vxy = True;
13.71/5.43	"
13.71/5.43	The bindings of the following Let/Where expression
13.71/5.43	"let {
13.71/5.43	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
13.71/5.43	} in result"
13.71/5.43	are unpacked to the following functions on top level
13.71/5.43	"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;
13.71/5.43	"
13.71/5.43	The bindings of the following Let/Where expression
13.71/5.43	"let {
13.71/5.43	biggest_left_key  = fst (findMax fm_l);
13.71/5.43	} in biggest_left_key < key"
13.71/5.43	are unpacked to the following functions on top level
13.71/5.43	"mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);
13.71/5.43	"
13.71/5.43	The bindings of the following Let/Where expression
13.71/5.43	"let {
13.71/5.43	smallest_right_key  = fst (findMin fm_r);
13.71/5.43	} in key < smallest_right_key"
13.71/5.43	are unpacked to the following functions on top level
13.71/5.43	"mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);
13.71/5.43	"
13.71/5.43	
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(10)
13.71/5.43	Obligation:
13.71/5.43	mainModule Main 
13.71/5.43	module FiniteMap where {
13.71/5.43	import qualified Main;
13.71/5.43	import qualified Maybe;
13.71/5.43	import qualified Prelude;
13.71/5.43	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
13.71/5.43	
13.71/5.43	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
13.71/5.43	}
13.71/5.43	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
13.71/5.43	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
13.71/5.43	
13.71/5.43	addListToFM0 old new = new;
13.71/5.43	
13.71/5.43	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
13.71/5.43	addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs;
13.71/5.43	
13.71/5.43	addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;
13.71/5.43	
13.71/5.43	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
13.71/5.43	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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);
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	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);
13.71/5.43	
13.71/5.43	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);
13.71/5.43	
13.71/5.43	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
13.71/5.43	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
13.71/5.43	
13.71/5.43	emptyFM :: FiniteMap a b;
13.71/5.43	emptyFM = EmptyFM;
13.71/5.43	
13.71/5.43	findMax :: FiniteMap a b  ->  (a,b);
13.71/5.43	findMax (Branch key elt yx yy EmptyFM) = (key,elt);
13.71/5.43	findMax (Branch key elt yz zu fm_r) = findMax fm_r;
13.71/5.43	
13.71/5.43	findMin :: FiniteMap b a  ->  (b,a);
13.71/5.43	findMin (Branch key elt wx EmptyFM wy) = (key,elt);
13.71/5.43	findMin (Branch key elt wz fm_l xu) = findMin fm_l;
13.71/5.43	
13.71/5.43	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
13.71/5.43	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_L fm_R key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_L fm_R + mkBalBranch6Size_r key elt fm_L fm_R < 2);
13.71/5.43	
13.71/5.43	mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
13.71/5.43	
13.71/5.43	mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr otherwise;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr otherwise;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
13.71/5.43	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
13.71/5.43	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);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
13.71/5.43	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);
13.71/5.43	
13.71/5.43	mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r vvu fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwx vwy fm_l fm_rl) fm_rr;
13.71/5.43	
13.71/5.43	mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l zv fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwx vwy fm_lr fm_r);
13.71/5.43	
13.71/5.43	mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwz;
13.71/5.43	
13.71/5.43	mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vxu;
13.71/5.43	
13.71/5.43	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
13.71/5.43	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
13.71/5.43	
13.71/5.43	mkBranchBalance_ok vxw vxx vxy = True;
13.71/5.43	
13.71/5.43	mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxy vxw;
13.71/5.43	
13.71/5.43	mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
13.71/5.43	mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key xv xw xx xy) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
13.71/5.43	
13.71/5.43	mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);
13.71/5.43	
13.71/5.43	mkBranchLeft_size vxw vxx vxy = sizeFM vxw;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	
13.71/5.43	mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxx vxy vxx;
13.71/5.43	
13.71/5.43	mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
13.71/5.43	mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key xz yu yv yw) = key < mkBranchRight_ok0Smallest_right_key fm_r;
13.71/5.43	
13.71/5.43	mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);
13.71/5.43	
13.71/5.43	mkBranchRight_size vxw vxx vxy = sizeFM vxx;
13.71/5.43	
13.71/5.43	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
13.71/5.43	mkBranchUnbox vxw vxx vxy x = x;
13.71/5.43	
13.71/5.43	sIZE_RATIO :: Int;
13.71/5.43	sIZE_RATIO = 5;
13.71/5.43	
13.71/5.43	sizeFM :: FiniteMap a b  ->  Int;
13.71/5.43	sizeFM EmptyFM = 0;
13.71/5.43	sizeFM (Branch vz wu size wv ww) = size;
13.71/5.43	
13.71/5.43	unitFM :: b  ->  a  ->  FiniteMap b a;
13.71/5.43	unitFM key elt = Branch key elt 1 emptyFM emptyFM;
13.71/5.43	
13.71/5.43	}
13.71/5.43	module Maybe where {
13.71/5.43	import qualified FiniteMap;
13.71/5.43	import qualified Main;
13.71/5.43	import qualified Prelude;
13.71/5.43	}
13.71/5.43	module Main where {
13.71/5.43	import qualified FiniteMap;
13.71/5.43	import qualified Maybe;
13.71/5.43	import qualified Prelude;
13.71/5.43	}
13.71/5.43	
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(11) NumRed (SOUND)
13.71/5.43	Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(12)
13.71/5.43	Obligation:
13.71/5.43	mainModule Main 
13.71/5.43	module FiniteMap where {
13.71/5.43	import qualified Main;
13.71/5.43	import qualified Maybe;
13.71/5.43	import qualified Prelude;
13.71/5.43	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
13.71/5.43	
13.71/5.43	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
13.71/5.43	}
13.71/5.43	addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
13.71/5.43	addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;
13.71/5.43	
13.71/5.43	addListToFM0 old new = new;
13.71/5.43	
13.71/5.43	addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
13.71/5.43	addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs;
13.71/5.43	
13.71/5.43	addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;
13.71/5.43	
13.71/5.43	addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
13.71/5.43	addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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);
13.71/5.43	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;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	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);
13.71/5.43	
13.71/5.43	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);
13.71/5.43	
13.71/5.43	addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
13.71/5.43	addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
13.71/5.43	
13.71/5.43	emptyFM :: FiniteMap a b;
13.71/5.43	emptyFM = EmptyFM;
13.71/5.43	
13.71/5.43	findMax :: FiniteMap b a  ->  (b,a);
13.71/5.43	findMax (Branch key elt yx yy EmptyFM) = (key,elt);
13.71/5.43	findMax (Branch key elt yz zu fm_r) = findMax fm_r;
13.71/5.43	
13.71/5.43	findMin :: FiniteMap a b  ->  (a,b);
13.71/5.43	findMin (Branch key elt wx EmptyFM wy) = (key,elt);
13.71/5.43	findMin (Branch key elt wz fm_l xu) = findMin fm_l;
13.71/5.43	
13.71/5.43	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
13.71/5.43	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_L fm_R key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_L fm_R + mkBalBranch6Size_r key elt fm_L fm_R < Pos (Succ (Succ Zero)));
13.71/5.43	
13.71/5.43	mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r vuv (Branch key_rl elt_rl vuw 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);
13.71/5.43	
13.71/5.43	mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l zw fm_ll (Branch key_lr elt_lr zx 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);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr otherwise;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch vux vuy vuz fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R vux vuy vuz fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
13.71/5.43	mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr otherwise;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch zy zz vuu fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R zy zz vuu fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
13.71/5.43	mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
13.71/5.43	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);
13.71/5.43	
13.71/5.43	mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
13.71/5.43	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);
13.71/5.43	
13.71/5.43	mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r vvu 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;
13.71/5.43	
13.71/5.43	mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l zv 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);
13.71/5.43	
13.71/5.43	mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwz;
13.71/5.43	
13.71/5.43	mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vxu;
13.71/5.43	
13.71/5.43	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
13.71/5.43	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;
13.71/5.43	
13.71/5.43	mkBranchBalance_ok vxw vxx vxy = True;
13.71/5.43	
13.71/5.43	mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxy vxw;
13.71/5.43	
13.71/5.43	mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
13.71/5.43	mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key xv xw xx xy) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
13.71/5.43	
13.71/5.43	mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);
13.71/5.43	
13.71/5.43	mkBranchLeft_size vxw vxx vxy = sizeFM vxw;
13.71/5.43	
13.71/5.43	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;
13.71/5.43	
13.71/5.43	mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxx vxy vxx;
13.71/5.43	
13.71/5.43	mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
13.71/5.43	mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key xz yu yv yw) = key < mkBranchRight_ok0Smallest_right_key fm_r;
13.71/5.43	
13.71/5.43	mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);
13.71/5.43	
13.71/5.43	mkBranchRight_size vxw vxx vxy = sizeFM vxx;
13.71/5.43	
13.71/5.43	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
13.71/5.43	mkBranchUnbox vxw vxx vxy x = x;
13.71/5.43	
13.71/5.43	sIZE_RATIO :: Int;
13.71/5.43	sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero)))));
13.71/5.43	
13.71/5.43	sizeFM :: FiniteMap a b  ->  Int;
13.71/5.43	sizeFM EmptyFM = Pos Zero;
13.71/5.43	sizeFM (Branch vz wu size wv ww) = size;
13.71/5.43	
13.71/5.43	unitFM :: a  ->  b  ->  FiniteMap a b;
13.71/5.43	unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM;
13.71/5.43	
13.71/5.43	}
13.71/5.43	module Maybe where {
13.71/5.43	import qualified FiniteMap;
13.71/5.43	import qualified Main;
13.71/5.43	import qualified Prelude;
13.71/5.43	}
13.71/5.43	module Main where {
13.71/5.43	import qualified FiniteMap;
13.71/5.43	import qualified Maybe;
13.71/5.43	import qualified Prelude;
13.71/5.43	}
13.71/5.43	
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(13) Narrow (SOUND)
13.71/5.43	Haskell To QDPs
13.71/5.43	
13.71/5.43	digraph dp_graph {
13.71/5.43	node [outthreshold=100, inthreshold=100];1[label="FiniteMap.addListToFM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
13.71/5.43	3[label="FiniteMap.addListToFM vyz3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
13.71/5.43	4[label="FiniteMap.addListToFM vyz3 vyz4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3];
13.71/5.43	5[label="FiniteMap.addListToFM_C FiniteMap.addListToFM0 vyz3 vyz4",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3];
13.71/5.43	6[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz3 vyz4",fontsize=16,color="burlywood",shape="triangle"];39[label="vyz4/vyz40 : vyz41",fontsize=10,color="white",style="solid",shape="box"];6 -> 39[label="",style="solid", color="burlywood", weight=9];
13.71/5.43	39 -> 7[label="",style="solid", color="burlywood", weight=3];
13.71/5.43	40[label="vyz4/[]",fontsize=10,color="white",style="solid",shape="box"];6 -> 40[label="",style="solid", color="burlywood", weight=9];
13.71/5.43	40 -> 8[label="",style="solid", color="burlywood", weight=3];
13.71/5.43	7[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz3 (vyz40 : vyz41)",fontsize=16,color="black",shape="box"];7 -> 9[label="",style="solid", color="black", weight=3];
13.71/5.43	8[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz3 []",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3];
13.71/5.43	9 -> 6[label="",style="dashed", color="red", weight=0];
13.71/5.43	9[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz3 vyz40) vyz41",fontsize=16,color="magenta"];9 -> 11[label="",style="dashed", color="magenta", weight=3];
13.71/5.43	9 -> 12[label="",style="dashed", color="magenta", weight=3];
13.71/5.43	10[label="vyz3",fontsize=16,color="green",shape="box"];11[label="FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz3 vyz40",fontsize=16,color="burlywood",shape="box"];41[label="vyz40/(vyz400,vyz401)",fontsize=10,color="white",style="solid",shape="box"];11 -> 41[label="",style="solid", color="burlywood", weight=9];
13.71/5.43	41 -> 13[label="",style="solid", color="burlywood", weight=3];
13.71/5.43	12[label="vyz41",fontsize=16,color="green",shape="box"];13[label="FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz3 (vyz400,vyz401)",fontsize=16,color="black",shape="box"];13 -> 14[label="",style="solid", color="black", weight=3];
13.71/5.43	14[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 vyz3 vyz400 vyz401",fontsize=16,color="burlywood",shape="box"];42[label="vyz3/FiniteMap.EmptyFM",fontsize=10,color="white",style="solid",shape="box"];14 -> 42[label="",style="solid", color="burlywood", weight=9];
13.71/5.43	42 -> 15[label="",style="solid", color="burlywood", weight=3];
13.71/5.43	43[label="vyz3/FiniteMap.Branch vyz30 vyz31 vyz32 vyz33 vyz34",fontsize=10,color="white",style="solid",shape="box"];14 -> 43[label="",style="solid", color="burlywood", weight=9];
13.71/5.43	43 -> 16[label="",style="solid", color="burlywood", weight=3];
13.71/5.43	15[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 FiniteMap.EmptyFM vyz400 vyz401",fontsize=16,color="black",shape="box"];15 -> 17[label="",style="solid", color="black", weight=3];
13.71/5.43	16[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 (FiniteMap.Branch vyz30 vyz31 vyz32 vyz33 vyz34) vyz400 vyz401",fontsize=16,color="black",shape="box"];16 -> 18[label="",style="solid", color="black", weight=3];
13.71/5.43	17[label="FiniteMap.addToFM_C4 FiniteMap.addListToFM0 FiniteMap.EmptyFM vyz400 vyz401",fontsize=16,color="black",shape="box"];17 -> 19[label="",style="solid", color="black", weight=3];
13.71/5.43	18[label="FiniteMap.addToFM_C3 FiniteMap.addListToFM0 (FiniteMap.Branch vyz30 vyz31 vyz32 vyz33 vyz34) vyz400 vyz401",fontsize=16,color="black",shape="box"];18 -> 20[label="",style="solid", color="black", weight=3];
13.71/5.43	19[label="FiniteMap.unitFM vyz400 vyz401",fontsize=16,color="black",shape="box"];19 -> 21[label="",style="solid", color="black", weight=3];
13.71/5.43	20[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz30 vyz31 vyz32 vyz33 vyz34 vyz400 vyz401 (vyz400 < vyz30)",fontsize=16,color="black",shape="box"];20 -> 22[label="",style="solid", color="black", weight=3];
13.71/5.43	21[label="FiniteMap.Branch vyz400 vyz401 (Pos (Succ Zero)) FiniteMap.emptyFM FiniteMap.emptyFM",fontsize=16,color="green",shape="box"];21 -> 23[label="",style="dashed", color="green", weight=3];
13.71/5.43	21 -> 24[label="",style="dashed", color="green", weight=3];
13.71/5.43	22[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz30 vyz31 vyz32 vyz33 vyz34 vyz400 vyz401 (compare vyz400 vyz30 == LT)",fontsize=16,color="burlywood",shape="box"];44[label="vyz400/()",fontsize=10,color="white",style="solid",shape="box"];22 -> 44[label="",style="solid", color="burlywood", weight=9];
13.71/5.43	44 -> 25[label="",style="solid", color="burlywood", weight=3];
13.71/5.43	23[label="FiniteMap.emptyFM",fontsize=16,color="black",shape="triangle"];23 -> 26[label="",style="solid", color="black", weight=3];
13.71/5.43	24 -> 23[label="",style="dashed", color="red", weight=0];
13.71/5.43	24[label="FiniteMap.emptyFM",fontsize=16,color="magenta"];25[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz30 vyz31 vyz32 vyz33 vyz34 () vyz401 (compare () vyz30 == LT)",fontsize=16,color="burlywood",shape="box"];45[label="vyz30/()",fontsize=10,color="white",style="solid",shape="box"];25 -> 45[label="",style="solid", color="burlywood", weight=9];
13.71/5.43	45 -> 27[label="",style="solid", color="burlywood", weight=3];
13.71/5.43	26[label="FiniteMap.EmptyFM",fontsize=16,color="green",shape="box"];27[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 (compare () () == LT)",fontsize=16,color="black",shape="box"];27 -> 28[label="",style="solid", color="black", weight=3];
13.71/5.43	28[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 (EQ == LT)",fontsize=16,color="black",shape="box"];28 -> 29[label="",style="solid", color="black", weight=3];
13.71/5.43	29[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 False",fontsize=16,color="black",shape="box"];29 -> 30[label="",style="solid", color="black", weight=3];
13.71/5.43	30[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 (() > ())",fontsize=16,color="black",shape="box"];30 -> 31[label="",style="solid", color="black", weight=3];
13.71/5.43	31[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 (compare () () == GT)",fontsize=16,color="black",shape="box"];31 -> 32[label="",style="solid", color="black", weight=3];
13.71/5.43	32[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 (EQ == GT)",fontsize=16,color="black",shape="box"];32 -> 33[label="",style="solid", color="black", weight=3];
13.71/5.43	33[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 False",fontsize=16,color="black",shape="box"];33 -> 34[label="",style="solid", color="black", weight=3];
13.71/5.43	34[label="FiniteMap.addToFM_C0 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 otherwise",fontsize=16,color="black",shape="box"];34 -> 35[label="",style="solid", color="black", weight=3];
13.71/5.43	35[label="FiniteMap.addToFM_C0 FiniteMap.addListToFM0 () vyz31 vyz32 vyz33 vyz34 () vyz401 True",fontsize=16,color="black",shape="box"];35 -> 36[label="",style="solid", color="black", weight=3];
13.71/5.43	36[label="FiniteMap.Branch () (FiniteMap.addListToFM0 vyz31 vyz401) vyz32 vyz33 vyz34",fontsize=16,color="green",shape="box"];36 -> 37[label="",style="dashed", color="green", weight=3];
13.71/5.43	37[label="FiniteMap.addListToFM0 vyz31 vyz401",fontsize=16,color="black",shape="box"];37 -> 38[label="",style="solid", color="black", weight=3];
13.71/5.43	38[label="vyz401",fontsize=16,color="green",shape="box"];}
13.71/5.43	
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(14)
13.71/5.43	Obligation:
13.71/5.43	Q DP problem:
13.71/5.43	The TRS P consists of the following rules:
13.71/5.43	
13.71/5.43	   new_foldl(vyz3, :(vyz40, vyz41), h) -> new_foldl(new_addListToFM_CAdd(vyz3, vyz40, h), vyz41, h)
13.71/5.43	
13.71/5.43	The TRS R consists of the following rules:
13.71/5.43	
13.71/5.43	   new_addListToFM_CAdd(Branch(@0, vyz31, vyz32, vyz33, vyz34), @2(@0, vyz401), h) -> Branch(@0, vyz401, vyz32, vyz33, vyz34)
13.71/5.43	   new_addListToFM_CAdd(EmptyFM, @2(vyz400, vyz401), h) -> Branch(vyz400, vyz401, Pos(Succ(Zero)), new_emptyFM(h), new_emptyFM(h))
13.71/5.43	   new_emptyFM(h) -> EmptyFM
13.71/5.43	
13.71/5.43	The set Q consists of the following terms:
13.71/5.43	
13.71/5.43	   new_addListToFM_CAdd(Branch(@0, x0, x1, x2, x3), @2(@0, x4), x5)
13.71/5.43	   new_addListToFM_CAdd(EmptyFM, @2(x0, x1), x2)
13.71/5.43	   new_emptyFM(x0)
13.71/5.43	
13.71/5.43	We have to consider all minimal (P,Q,R)-chains.
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(15) QDPSizeChangeProof (EQUIVALENT)
13.71/5.43	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
13.71/5.43	
13.71/5.43	From the DPs we obtained the following set of size-change graphs:
13.71/5.43	*new_foldl(vyz3, :(vyz40, vyz41), h) -> new_foldl(new_addListToFM_CAdd(vyz3, vyz40, h), vyz41, h)
13.71/5.43	The graph contains the following edges 2 > 2, 3 >= 3
13.71/5.43	
13.71/5.43	
13.71/5.43	----------------------------------------
13.71/5.43	
13.71/5.43	(16)
13.71/5.43	YES
13.86/5.47	EOF