132.04/106.38	MAYBE
134.25/107.04	proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
134.25/107.04	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
134.25/107.04	
134.25/107.04	
134.25/107.04	H-Termination with start terms of the given HASKELL could not be shown:
134.25/107.04	
134.25/107.04	(0) HASKELL
134.25/107.04	(1) LR [EQUIVALENT, 0 ms]
134.25/107.04	(2) HASKELL
134.25/107.04	(3) CR [EQUIVALENT, 0 ms]
134.25/107.04	(4) HASKELL
134.25/107.04	(5) BR [EQUIVALENT, 0 ms]
134.25/107.04	(6) HASKELL
134.25/107.04	(7) COR [EQUIVALENT, 13 ms]
134.25/107.04	(8) HASKELL
134.25/107.04	(9) LetRed [EQUIVALENT, 0 ms]
134.25/107.04	(10) HASKELL
134.25/107.04	(11) NumRed [SOUND, 16 ms]
134.25/107.04	(12) HASKELL
134.25/107.04	
134.25/107.04	
134.25/107.04	----------------------------------------
134.25/107.04	
134.25/107.04	(0)
134.25/107.04	Obligation:
134.25/107.04	mainModule Main 
134.25/107.04	module FiniteMap where {
134.25/107.04	import qualified Main;
134.25/107.04	import qualified Maybe;
134.25/107.04	import qualified Prelude;
134.25/107.04	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
134.25/107.04	
134.25/107.04	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
134.25/107.04	}
134.25/107.04	delFromFM :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
134.25/107.04	delFromFM EmptyFM del_key = emptyFM;
134.25/107.04	delFromFM (Branch key elt size fm_l fm_r) del_key  | del_key > key = mkBalBranch key elt fm_l (delFromFM fm_r del_key)
134.25/107.04	 | del_key < key = mkBalBranch key elt (delFromFM fm_l del_key) fm_r
134.25/107.04	 | key == del_key = glueBal fm_l fm_r;
134.25/107.04	
134.25/107.04	delListFromFM :: Ord a => FiniteMap a b  ->  [a]  ->  FiniteMap a b;
134.25/107.04	delListFromFM fm keys = foldl delFromFM fm keys;
134.25/107.04	
134.25/107.04	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
134.25/107.04	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
134.25/107.04	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
134.25/107.04	
134.25/107.04	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
134.25/107.04	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
134.25/107.04	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
134.25/107.04	
134.25/107.04	emptyFM :: FiniteMap b a;
134.25/107.04	emptyFM = EmptyFM;
134.25/107.04	
134.25/107.04	findMax :: FiniteMap a b  ->  (a,b);
134.25/107.04	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
134.25/107.04	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
134.25/107.04	
134.25/107.04	findMin :: FiniteMap b a  ->  (b,a);
134.25/107.04	findMin (Branch key elt _ EmptyFM _) = (key,elt);
134.25/107.04	findMin (Branch key elt _ fm_l _) = findMin fm_l;
134.25/107.04	
134.25/107.04	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
134.25/107.04	glueBal EmptyFM fm2 = fm2;
134.25/107.04	glueBal fm1 EmptyFM = fm1;
134.25/107.04	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
134.25/107.04	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
134.25/107.04	mid_elt1 = (\(_,mid_elt1) ->mid_elt1) vv2;
134.25/107.04	mid_elt2 = (\(_,mid_elt2) ->mid_elt2) vv3;
134.25/107.04	mid_key1 = (\(mid_key1,_) ->mid_key1) vv2;
134.25/107.04	mid_key2 = (\(mid_key2,_) ->mid_key2) vv3;
134.25/107.04	vv2 = findMax fm1;
134.25/107.04	vv3 = findMin fm2;
134.25/107.04	 };
134.25/107.04	
134.25/107.04	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
134.25/107.04	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
134.25/107.04	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
134.25/107.04	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
134.25/107.04	 | otherwise -> double_L fm_L fm_R; 
134.25/107.04	 } 
134.25/107.04	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
134.25/107.04	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
134.25/107.04	 | otherwise -> double_R fm_L fm_R; 
134.25/107.04	 } 
134.25/107.04	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
134.25/107.04	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);
134.25/107.04	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);
134.25/107.04	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;
134.25/107.04	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);
134.25/107.04	size_l = sizeFM fm_L;
134.25/107.04	size_r = sizeFM fm_R;
134.25/107.04	 };
134.25/107.04	
134.25/107.04	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
134.25/107.04	mkBranch which key elt fm_l fm_r = let { 
134.25/107.04	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
134.25/107.04	} in result where { 
134.25/107.04	balance_ok = True;
134.25/107.04	left_ok = case fm_l of { 
134.25/107.04	EmptyFM-> True; 
134.25/107.04	Branch left_key _ _ _ _-> let { 
134.25/107.04	biggest_left_key = fst (findMax fm_l);
134.25/107.04	} in biggest_left_key < key; 
134.25/107.04	 } ;
134.25/107.04	left_size = sizeFM fm_l;
134.25/107.04	right_ok = case fm_r of { 
134.25/107.04	EmptyFM-> True; 
134.25/107.04	Branch right_key _ _ _ _-> let { 
134.25/107.04	smallest_right_key = fst (findMin fm_r);
134.25/107.04	} in key < smallest_right_key; 
134.25/107.04	 } ;
134.25/107.04	right_size = sizeFM fm_r;
134.25/107.04	unbox :: Int  ->  Int;
134.25/107.04	unbox x = x;
134.25/107.04	 };
134.25/107.04	
134.25/107.04	sIZE_RATIO :: Int;
134.25/107.04	sIZE_RATIO = 5;
134.25/107.04	
134.25/107.04	sizeFM :: FiniteMap a b  ->  Int;
134.25/107.04	sizeFM EmptyFM = 0;
134.25/107.04	sizeFM (Branch _ _ size _ _) = size;
134.25/107.04	
134.25/107.04	}
134.25/107.04	module Maybe where {
134.25/107.04	import qualified FiniteMap;
134.25/107.04	import qualified Main;
134.25/107.04	import qualified Prelude;
134.25/107.04	}
134.25/107.04	module Main where {
134.25/107.04	import qualified FiniteMap;
134.25/107.04	import qualified Maybe;
134.25/107.04	import qualified Prelude;
134.25/107.04	}
134.25/107.04	
134.25/107.04	----------------------------------------
134.25/107.04	
134.25/107.04	(1) LR (EQUIVALENT)
134.25/107.04	Lambda Reductions:
134.25/107.04	The following Lambda expression
134.25/107.04	"\(_,mid_elt2)->mid_elt2"
134.25/107.04	is transformed to
134.25/107.04	"mid_elt20 (_,mid_elt2) = mid_elt2;
134.25/107.04	"
134.25/107.04	The following Lambda expression
134.25/107.04	"\(mid_key2,_)->mid_key2"
134.25/107.04	is transformed to
134.25/107.04	"mid_key20 (mid_key2,_) = mid_key2;
134.25/107.04	"
134.25/107.04	The following Lambda expression
134.25/107.04	"\(mid_key1,_)->mid_key1"
134.25/107.04	is transformed to
134.25/107.04	"mid_key10 (mid_key1,_) = mid_key1;
134.25/107.04	"
134.25/107.04	The following Lambda expression
134.25/107.04	"\(_,mid_elt1)->mid_elt1"
134.25/107.04	is transformed to
134.25/107.04	"mid_elt10 (_,mid_elt1) = mid_elt1;
134.25/107.04	"
134.25/107.04	
134.25/107.04	----------------------------------------
134.25/107.04	
134.25/107.04	(2)
134.25/107.04	Obligation:
134.25/107.04	mainModule Main 
134.25/107.04	module FiniteMap where {
134.25/107.04	import qualified Main;
134.25/107.04	import qualified Maybe;
134.25/107.04	import qualified Prelude;
134.25/107.04	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
134.25/107.04	
134.25/107.04	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
134.25/107.04	}
134.25/107.04	delFromFM :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
134.25/107.04	delFromFM EmptyFM del_key = emptyFM;
134.25/107.04	delFromFM (Branch key elt size fm_l fm_r) del_key  | del_key > key = mkBalBranch key elt fm_l (delFromFM fm_r del_key)
134.25/107.04	 | del_key < key = mkBalBranch key elt (delFromFM fm_l del_key) fm_r
134.25/107.04	 | key == del_key = glueBal fm_l fm_r;
134.25/107.04	
134.25/107.04	delListFromFM :: Ord a => FiniteMap a b  ->  [a]  ->  FiniteMap a b;
134.25/107.04	delListFromFM fm keys = foldl delFromFM fm keys;
134.25/107.04	
134.25/107.04	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
134.25/107.04	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
134.25/107.04	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
134.25/107.04	
134.25/107.04	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
134.25/107.05	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
134.25/107.05	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
134.25/107.05	
134.25/107.05	emptyFM :: FiniteMap b a;
134.25/107.05	emptyFM = EmptyFM;
134.25/107.05	
134.25/107.05	findMax :: FiniteMap a b  ->  (a,b);
134.25/107.05	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
134.25/107.05	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
134.25/107.05	
134.25/107.05	findMin :: FiniteMap a b  ->  (a,b);
134.25/107.05	findMin (Branch key elt _ EmptyFM _) = (key,elt);
134.25/107.05	findMin (Branch key elt _ fm_l _) = findMin fm_l;
134.25/107.05	
134.25/107.05	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
134.25/107.05	glueBal EmptyFM fm2 = fm2;
134.25/107.05	glueBal fm1 EmptyFM = fm1;
134.25/107.05	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
134.25/107.05	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
134.25/107.05	mid_elt1 = mid_elt10 vv2;
134.25/107.05	mid_elt10 (_,mid_elt1) = mid_elt1;
134.25/107.05	mid_elt2 = mid_elt20 vv3;
134.25/107.05	mid_elt20 (_,mid_elt2) = mid_elt2;
134.25/107.05	mid_key1 = mid_key10 vv2;
134.25/107.05	mid_key10 (mid_key1,_) = mid_key1;
134.25/107.05	mid_key2 = mid_key20 vv3;
134.25/107.05	mid_key20 (mid_key2,_) = mid_key2;
134.25/107.05	vv2 = findMax fm1;
134.25/107.05	vv3 = findMin fm2;
134.25/107.05	 };
134.25/107.05	
134.25/107.05	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
134.25/107.05	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
134.25/107.05	 | size_r > sIZE_RATIO * size_l = case fm_R of { 
134.25/107.05	Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
134.25/107.05	 | otherwise -> double_L fm_L fm_R; 
134.25/107.05	 } 
134.25/107.05	 | size_l > sIZE_RATIO * size_r = case fm_L of { 
134.25/107.05	Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
134.25/107.05	 | otherwise -> double_R fm_L fm_R; 
134.25/107.05	 } 
134.25/107.05	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
134.25/107.05	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);
134.25/107.05	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);
134.25/107.05	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;
134.25/107.05	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);
134.25/107.05	size_l = sizeFM fm_L;
134.25/107.05	size_r = sizeFM fm_R;
134.25/107.05	 };
134.25/107.05	
134.25/107.05	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
134.25/107.05	mkBranch which key elt fm_l fm_r = let { 
134.25/107.05	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
134.25/107.05	} in result where { 
134.25/107.05	balance_ok = True;
134.25/107.05	left_ok = case fm_l of { 
134.25/107.05	EmptyFM-> True; 
134.25/107.05	Branch left_key _ _ _ _-> let { 
134.25/107.05	biggest_left_key = fst (findMax fm_l);
134.25/107.05	} in biggest_left_key < key; 
134.25/107.05	 } ;
134.25/107.05	left_size = sizeFM fm_l;
134.25/107.05	right_ok = case fm_r of { 
134.25/107.05	EmptyFM-> True; 
134.25/107.05	Branch right_key _ _ _ _-> let { 
134.25/107.05	smallest_right_key = fst (findMin fm_r);
134.25/107.05	} in key < smallest_right_key; 
134.25/107.05	 } ;
134.25/107.05	right_size = sizeFM fm_r;
134.25/107.05	unbox :: Int  ->  Int;
134.25/107.05	unbox x = x;
134.25/107.05	 };
134.25/107.05	
134.25/107.05	sIZE_RATIO :: Int;
134.25/107.05	sIZE_RATIO = 5;
134.25/107.05	
134.25/107.05	sizeFM :: FiniteMap b a  ->  Int;
134.25/107.05	sizeFM EmptyFM = 0;
134.25/107.05	sizeFM (Branch _ _ size _ _) = size;
134.25/107.05	
134.25/107.05	}
134.25/107.05	module Maybe where {
134.25/107.05	import qualified FiniteMap;
134.25/107.05	import qualified Main;
134.25/107.05	import qualified Prelude;
134.25/107.05	}
134.25/107.05	module Main where {
134.25/107.05	import qualified FiniteMap;
134.25/107.05	import qualified Maybe;
134.25/107.05	import qualified Prelude;
134.25/107.05	}
134.25/107.05	
134.25/107.05	----------------------------------------
134.25/107.05	
134.25/107.05	(3) CR (EQUIVALENT)
134.25/107.05	Case Reductions:
134.25/107.05	The following Case expression
134.25/107.05	"case fm_r of {
134.25/107.05	EmptyFM  -> True;
134.25/107.05	Branch right_key _ _ _ _  -> let {
134.25/107.05	smallest_right_key  = fst (findMin fm_r);
134.25/107.05	} in key < smallest_right_key}
134.25/107.05	"
134.25/107.05	is transformed to
134.25/107.05	"right_ok0 fm_r key EmptyFM = True;
134.25/107.05	right_ok0 fm_r key (Branch right_key _ _ _ _) = let {
134.25/107.05	smallest_right_key  = fst (findMin fm_r);
134.25/107.05	} in key < smallest_right_key;
134.25/107.05	"
134.25/107.05	The following Case expression
134.25/107.05	"case fm_l of {
134.25/107.05	EmptyFM  -> True;
134.25/107.05	Branch left_key _ _ _ _  -> let {
134.25/107.05	biggest_left_key  = fst (findMax fm_l);
134.25/107.05	} in biggest_left_key < key}
134.25/107.05	"
134.25/107.05	is transformed to
134.25/107.05	"left_ok0 fm_l key EmptyFM = True;
134.25/107.05	left_ok0 fm_l key (Branch left_key _ _ _ _) = let {
134.25/107.05	biggest_left_key  = fst (findMax fm_l);
134.25/107.05	} in biggest_left_key < key;
134.25/107.05	"
134.25/107.05	The following Case expression
134.25/107.05	"case fm_R of {
134.25/107.05	Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R}
134.25/107.05	"
134.25/107.05	is transformed to
134.25/107.05	"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;
134.25/107.05	"
134.25/107.05	The following Case expression
134.25/107.05	"case fm_L of {
134.25/107.05	Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R}
134.25/107.05	"
134.25/107.05	is transformed to
134.25/107.05	"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;
134.25/107.05	"
134.25/107.05	
134.25/107.05	----------------------------------------
134.25/107.05	
134.25/107.05	(4)
134.25/107.05	Obligation:
134.25/107.05	mainModule Main 
134.25/107.05	module FiniteMap where {
134.25/107.05	import qualified Main;
134.25/107.05	import qualified Maybe;
134.25/107.05	import qualified Prelude;
134.25/107.05	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
134.25/107.05	
134.25/107.05	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
134.25/107.05	}
134.25/107.05	delFromFM :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
134.25/107.05	delFromFM EmptyFM del_key = emptyFM;
134.25/107.05	delFromFM (Branch key elt size fm_l fm_r) del_key  | del_key > key = mkBalBranch key elt fm_l (delFromFM fm_r del_key)
134.25/107.05	 | del_key < key = mkBalBranch key elt (delFromFM fm_l del_key) fm_r
134.25/107.05	 | key == del_key = glueBal fm_l fm_r;
134.25/107.05	
134.25/107.05	delListFromFM :: Ord a => FiniteMap a b  ->  [a]  ->  FiniteMap a b;
134.25/107.05	delListFromFM fm keys = foldl delFromFM fm keys;
134.25/107.05	
134.25/107.05	deleteMax :: Ord b => FiniteMap b a  ->  FiniteMap b a;
134.25/107.05	deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l;
134.25/107.05	deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
134.25/107.05	
134.25/107.05	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
134.25/107.05	deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r;
134.25/107.05	deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
134.25/107.05	
134.25/107.05	emptyFM :: FiniteMap b a;
134.25/107.05	emptyFM = EmptyFM;
134.25/107.05	
134.25/107.05	findMax :: FiniteMap b a  ->  (b,a);
134.25/107.05	findMax (Branch key elt _ _ EmptyFM) = (key,elt);
134.25/107.05	findMax (Branch key elt _ _ fm_r) = findMax fm_r;
134.25/107.05	
134.25/107.05	findMin :: FiniteMap a b  ->  (a,b);
134.25/107.05	findMin (Branch key elt _ EmptyFM _) = (key,elt);
134.25/107.05	findMin (Branch key elt _ fm_l _) = findMin fm_l;
134.25/107.05	
134.25/107.05	glueBal :: Ord a => FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
134.25/107.05	glueBal EmptyFM fm2 = fm2;
134.25/107.05	glueBal fm1 EmptyFM = fm1;
134.25/107.05	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
134.25/107.05	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
134.25/107.05	mid_elt1 = mid_elt10 vv2;
134.25/107.05	mid_elt10 (_,mid_elt1) = mid_elt1;
134.25/107.05	mid_elt2 = mid_elt20 vv3;
134.25/107.05	mid_elt20 (_,mid_elt2) = mid_elt2;
134.25/107.05	mid_key1 = mid_key10 vv2;
134.25/107.05	mid_key10 (mid_key1,_) = mid_key1;
134.25/107.05	mid_key2 = mid_key20 vv3;
134.25/107.05	mid_key20 (mid_key2,_) = mid_key2;
134.25/107.05	vv2 = findMax fm1;
134.25/107.05	vv3 = findMin fm2;
134.25/107.05	 };
134.25/107.05	
134.25/107.05	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
134.25/107.05	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
134.25/107.05	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
134.25/107.05	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
134.25/107.05	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
134.25/107.05	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);
134.25/107.05	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);
134.25/107.05	mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
134.25/107.05	 | otherwise = double_L fm_L fm_R;
134.25/107.05	mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
134.25/107.05	 | otherwise = double_R fm_L fm_R;
134.25/107.05	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;
134.25/107.05	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);
134.25/107.05	size_l = sizeFM fm_L;
134.25/107.05	size_r = sizeFM fm_R;
134.25/107.05	 };
134.25/107.05	
134.25/107.05	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
134.25/107.05	mkBranch which key elt fm_l fm_r = let { 
134.25/107.05	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
134.25/107.05	} in result where { 
134.25/107.05	balance_ok = True;
134.25/107.05	left_ok = left_ok0 fm_l key fm_l;
134.25/107.05	left_ok0 fm_l key EmptyFM = True;
134.25/107.05	left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
134.25/107.05	biggest_left_key = fst (findMax fm_l);
134.25/107.05	} in biggest_left_key < key;
134.25/107.05	left_size = sizeFM fm_l;
134.25/107.05	right_ok = right_ok0 fm_r key fm_r;
134.25/107.05	right_ok0 fm_r key EmptyFM = True;
134.25/107.05	right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
134.25/107.05	smallest_right_key = fst (findMin fm_r);
134.25/107.05	} in key < smallest_right_key;
134.25/107.05	right_size = sizeFM fm_r;
134.25/107.05	unbox :: Int  ->  Int;
134.25/107.05	unbox x = x;
134.25/107.05	 };
134.25/107.05	
134.25/107.05	sIZE_RATIO :: Int;
134.25/107.05	sIZE_RATIO = 5;
134.25/107.05	
134.25/107.05	sizeFM :: FiniteMap b a  ->  Int;
134.25/107.05	sizeFM EmptyFM = 0;
134.25/107.05	sizeFM (Branch _ _ size _ _) = size;
134.25/107.05	
134.25/107.05	}
134.25/107.05	module Maybe where {
134.25/107.05	import qualified FiniteMap;
134.25/107.05	import qualified Main;
134.25/107.05	import qualified Prelude;
134.25/107.05	}
134.25/107.05	module Main where {
134.25/107.05	import qualified FiniteMap;
134.25/107.05	import qualified Maybe;
134.25/107.05	import qualified Prelude;
134.25/107.05	}
134.25/107.05	
134.25/107.05	----------------------------------------
134.25/107.05	
134.25/107.05	(5) BR (EQUIVALENT)
134.25/107.05	Replaced joker patterns by fresh variables and removed binding patterns.
134.25/107.05	----------------------------------------
134.25/107.05	
134.25/107.05	(6)
134.25/107.05	Obligation:
134.25/107.05	mainModule Main 
134.25/107.05	module FiniteMap where {
134.25/107.05	import qualified Main;
134.25/107.05	import qualified Maybe;
134.25/107.05	import qualified Prelude;
134.25/107.05	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
134.25/107.05	
134.25/107.05	instance (Eq a, Eq b) => Eq FiniteMap b a where { 
134.25/107.05	}
134.25/107.05	delFromFM :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
134.25/107.05	delFromFM EmptyFM del_key = emptyFM;
134.25/107.05	delFromFM (Branch key elt size fm_l fm_r) del_key  | del_key > key = mkBalBranch key elt fm_l (delFromFM fm_r del_key)
134.25/107.05	 | del_key < key = mkBalBranch key elt (delFromFM fm_l del_key) fm_r
134.25/107.05	 | key == del_key = glueBal fm_l fm_r;
134.25/107.05	
134.25/107.05	delListFromFM :: Ord a => FiniteMap a b  ->  [a]  ->  FiniteMap a b;
134.25/107.05	delListFromFM fm keys = foldl delFromFM fm keys;
134.25/107.05	
134.25/107.05	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
134.25/107.05	deleteMax (Branch key elt xx fm_l EmptyFM) = fm_l;
134.25/107.05	deleteMax (Branch key elt xy fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
134.25/107.05	
134.25/107.05	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
134.25/107.05	deleteMin (Branch key elt xz EmptyFM fm_r) = fm_r;
134.25/107.05	deleteMin (Branch key elt yu fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
137.14/107.77	
137.14/107.77	emptyFM :: FiniteMap b a;
137.14/107.77	emptyFM = EmptyFM;
137.14/107.77	
137.14/107.77	findMax :: FiniteMap b a  ->  (b,a);
137.14/107.77	findMax (Branch key elt vuv vuw EmptyFM) = (key,elt);
137.14/107.77	findMax (Branch key elt vux vuy fm_r) = findMax fm_r;
137.14/107.77	
137.14/107.77	findMin :: FiniteMap b a  ->  (b,a);
137.14/107.77	findMin (Branch key elt yv EmptyFM yw) = (key,elt);
137.14/107.77	findMin (Branch key elt yx fm_l yy) = findMin fm_l;
137.14/107.77	
137.14/107.77	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	glueBal EmptyFM fm2 = fm2;
137.14/107.77	glueBal fm1 EmptyFM = fm1;
137.14/107.77	glueBal fm1 fm2  | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)
137.14/107.77	 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 
137.14/107.77	mid_elt1 = mid_elt10 vv2;
137.14/107.77	mid_elt10 (ww,mid_elt1) = mid_elt1;
137.14/107.77	mid_elt2 = mid_elt20 vv3;
137.14/107.77	mid_elt20 (wv,mid_elt2) = mid_elt2;
137.14/107.77	mid_key1 = mid_key10 vv2;
137.14/107.77	mid_key10 (mid_key1,wx) = mid_key1;
137.14/107.77	mid_key2 = mid_key20 vv3;
137.14/107.77	mid_key20 (mid_key2,wy) = mid_key2;
137.14/107.77	vv2 = findMax fm1;
137.14/107.77	vv3 = findMin fm2;
137.14/107.77	 };
137.14/107.77	
137.14/107.77	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
137.14/107.77	 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
137.14/107.77	 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
137.14/107.77	 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
137.14/107.77	double_L fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu 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);
137.14/107.77	double_R (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv 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);
137.14/107.77	mkBalBranch0 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
137.14/107.77	 | otherwise = double_L fm_L fm_R;
137.14/107.77	mkBalBranch1 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
137.14/107.77	 | otherwise = double_R fm_L fm_R;
137.14/107.77	single_L fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
137.14/107.77	single_R (Branch key_l elt_l vuz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
137.14/107.77	size_l = sizeFM fm_L;
137.14/107.77	size_r = sizeFM fm_R;
137.14/107.77	 };
137.14/107.77	
137.14/107.77	mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	mkBranch which key elt fm_l fm_r = let { 
137.14/107.77	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
137.14/107.77	} in result where { 
137.14/107.77	balance_ok = True;
137.14/107.77	left_ok = left_ok0 fm_l key fm_l;
137.14/107.77	left_ok0 fm_l key EmptyFM = True;
137.14/107.77	left_ok0 fm_l key (Branch left_key yz zu zv zw) = let { 
137.14/107.77	biggest_left_key = fst (findMax fm_l);
137.14/107.77	} in biggest_left_key < key;
137.14/107.77	left_size = sizeFM fm_l;
137.14/107.77	right_ok = right_ok0 fm_r key fm_r;
137.14/107.77	right_ok0 fm_r key EmptyFM = True;
137.14/107.77	right_ok0 fm_r key (Branch right_key zx zy zz vuu) = let { 
137.14/107.77	smallest_right_key = fst (findMin fm_r);
137.14/107.77	} in key < smallest_right_key;
137.14/107.77	right_size = sizeFM fm_r;
137.14/107.77	unbox :: Int  ->  Int;
137.14/107.77	unbox x = x;
137.14/107.77	 };
137.14/107.77	
137.14/107.77	sIZE_RATIO :: Int;
137.14/107.77	sIZE_RATIO = 5;
137.14/107.77	
137.14/107.77	sizeFM :: FiniteMap b a  ->  Int;
137.14/107.77	sizeFM EmptyFM = 0;
137.14/107.77	sizeFM (Branch wz xu size xv xw) = size;
137.14/107.77	
137.14/107.77	}
137.14/107.77	module Maybe where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Main;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.14/107.77	module Main where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Maybe;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.14/107.77	
137.14/107.77	----------------------------------------
137.14/107.77	
137.14/107.77	(7) COR (EQUIVALENT)
137.14/107.77	Cond Reductions:
137.14/107.77	The following Function with conditions
137.14/107.77	"undefined |Falseundefined;
137.14/107.77	"
137.14/107.77	is transformed to
137.14/107.77	"undefined  = undefined1;
137.14/107.77	"
137.14/107.77	"undefined0 True = undefined;
137.14/107.77	"
137.14/107.77	"undefined1  = undefined0 False;
137.14/107.77	"
137.14/107.77	The following Function with conditions
137.14/107.77	"glueBal EmptyFM fm2 = fm2;
137.14/107.77	glueBal fm1 EmptyFM = fm1;
137.14/107.77	glueBal fm1 fm2|sizeFM fm2 > sizeFM fm1mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)|otherwisemkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where {
137.14/107.77	mid_elt1  = mid_elt10 vv2;
137.14/107.77	;
137.14/107.77	mid_elt10 (ww,mid_elt1) = mid_elt1;
137.14/107.77	;
137.14/107.77	mid_elt2  = mid_elt20 vv3;
137.14/107.77	;
137.14/107.77	mid_elt20 (wv,mid_elt2) = mid_elt2;
137.14/107.77	;
137.14/107.77	mid_key1  = mid_key10 vv2;
137.14/107.77	;
137.14/107.77	mid_key10 (mid_key1,wx) = mid_key1;
137.14/107.77	;
137.14/107.77	mid_key2  = mid_key20 vv3;
137.14/107.77	;
137.14/107.77	mid_key20 (mid_key2,wy) = mid_key2;
137.14/107.77	;
137.14/107.77	vv2  = findMax fm1;
137.14/107.77	;
137.14/107.77	vv3  = findMin fm2;
137.14/107.77	} 
137.14/107.77	;
137.14/107.77	"
137.14/107.77	is transformed to
137.14/107.77	"glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
137.14/107.77	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
137.14/107.77	glueBal fm1 fm2 = glueBal2 fm1 fm2;
137.14/107.77	"
137.14/107.77	"glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where {
137.14/107.77	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
137.14/107.77	;
137.14/107.77	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
137.14/107.77	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
137.14/107.77	;
137.14/107.77	mid_elt1  = mid_elt10 vv2;
137.14/107.77	;
137.14/107.77	mid_elt10 (ww,mid_elt1) = mid_elt1;
137.14/107.77	;
137.14/107.77	mid_elt2  = mid_elt20 vv3;
137.14/107.77	;
137.14/107.77	mid_elt20 (wv,mid_elt2) = mid_elt2;
137.14/107.77	;
137.14/107.77	mid_key1  = mid_key10 vv2;
137.14/107.77	;
137.14/107.77	mid_key10 (mid_key1,wx) = mid_key1;
137.14/107.77	;
137.14/107.77	mid_key2  = mid_key20 vv3;
137.14/107.77	;
137.14/107.77	mid_key20 (mid_key2,wy) = mid_key2;
137.14/107.77	;
137.14/107.77	vv2  = findMax fm1;
137.14/107.77	;
137.14/107.77	vv3  = findMin fm2;
137.14/107.77	} 
137.14/107.77	;
137.14/107.77	"
137.14/107.77	"glueBal3 fm1 EmptyFM = fm1;
137.14/107.77	glueBal3 vxu vxv = glueBal2 vxu vxv;
137.14/107.77	"
137.14/107.77	"glueBal4 EmptyFM fm2 = fm2;
137.14/107.77	glueBal4 vxx vxy = glueBal3 vxx vxy;
137.14/107.77	"
137.14/107.77	The following Function with conditions
137.14/107.77	"delFromFM EmptyFM del_key = emptyFM;
137.14/107.77	delFromFM (Branch key elt size fm_l fm_r) del_key|del_key > keymkBalBranch key elt fm_l (delFromFM fm_r del_key)|del_key < keymkBalBranch key elt (delFromFM fm_l del_key) fm_r|key == del_keyglueBal fm_l fm_r;
137.14/107.77	"
137.14/107.77	is transformed to
137.14/107.77	"delFromFM EmptyFM del_key = delFromFM4 EmptyFM del_key;
137.14/107.77	delFromFM (Branch key elt size fm_l fm_r) del_key = delFromFM3 (Branch key elt size fm_l fm_r) del_key;
137.14/107.77	"
137.14/107.77	"delFromFM0 key elt size fm_l fm_r del_key True = glueBal fm_l fm_r;
137.14/107.77	"
137.14/107.77	"delFromFM1 key elt size fm_l fm_r del_key True = mkBalBranch key elt (delFromFM fm_l del_key) fm_r;
137.14/107.77	delFromFM1 key elt size fm_l fm_r del_key False = delFromFM0 key elt size fm_l fm_r del_key (key == del_key);
137.14/107.77	"
137.14/107.77	"delFromFM2 key elt size fm_l fm_r del_key True = mkBalBranch key elt fm_l (delFromFM fm_r del_key);
137.14/107.77	delFromFM2 key elt size fm_l fm_r del_key False = delFromFM1 key elt size fm_l fm_r del_key (del_key < key);
137.14/107.77	"
137.14/107.77	"delFromFM3 (Branch key elt size fm_l fm_r) del_key = delFromFM2 key elt size fm_l fm_r del_key (del_key > key);
137.14/107.77	"
137.14/107.77	"delFromFM4 EmptyFM del_key = emptyFM;
137.14/107.77	delFromFM4 vyv vyw = delFromFM3 vyv vyw;
137.14/107.77	"
137.14/107.77	The following Function with conditions
137.14/107.77	"mkBalBranch1 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
137.14/107.77	"
137.14/107.77	is transformed to
137.14/107.77	"mkBalBranch1 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr);
137.14/107.77	"
137.14/107.77	"mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = single_R fm_L fm_R;
137.14/107.77	mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr otherwise;
137.14/107.77	"
137.14/107.77	"mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = double_R fm_L fm_R;
137.14/107.77	"
137.14/107.77	"mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
137.14/107.77	"
137.14/107.77	The following Function with conditions
137.14/107.77	"mkBalBranch0 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
137.14/107.77	"
137.14/107.77	is transformed to
137.14/107.77	"mkBalBranch0 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr);
137.14/107.77	"
137.14/107.77	"mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr True = single_L fm_L fm_R;
137.14/107.77	mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr otherwise;
137.14/107.77	"
137.14/107.77	"mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr True = double_L fm_L fm_R;
137.14/107.77	"
137.14/107.77	"mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
137.14/107.77	"
137.14/107.77	The following Function with conditions
137.14/107.77	"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 {
137.14/107.77	double_L fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu 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);
137.14/107.77	;
137.14/107.77	double_R (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv 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);
137.14/107.77	;
137.14/107.77	mkBalBranch0 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
137.14/107.77	;
137.14/107.77	mkBalBranch1 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
137.14/107.77	;
137.14/107.77	single_L fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
137.14/107.77	;
137.14/107.77	single_R (Branch key_l elt_l vuz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
137.14/107.77	;
137.14/107.77	size_l  = sizeFM fm_L;
137.14/107.77	;
137.14/107.77	size_r  = sizeFM fm_R;
137.14/107.77	} 
137.14/107.77	;
137.14/107.77	"
137.14/107.77	is transformed to
137.14/107.77	"mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
137.14/107.77	"
137.14/107.77	"mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
137.14/107.77	double_L fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu 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);
137.14/107.77	;
137.14/107.77	double_R (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv 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);
137.14/107.77	;
137.14/107.77	mkBalBranch0 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr);
137.14/107.77	;
137.14/107.77	mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr True = double_L fm_L fm_R;
137.14/107.77	;
137.14/107.77	mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr True = single_L fm_L fm_R;
137.14/107.77	mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr otherwise;
137.14/107.77	;
137.14/107.77	mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
137.14/107.77	;
137.14/107.77	mkBalBranch1 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr);
137.14/107.77	;
137.14/107.77	mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = double_R fm_L fm_R;
137.14/107.77	;
137.14/107.77	mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = single_R fm_L fm_R;
137.14/107.77	mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr otherwise;
137.14/107.77	;
137.14/107.77	mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
137.14/107.77	;
137.14/107.77	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
137.14/107.77	;
137.14/107.77	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
137.14/107.77	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
137.14/107.77	;
137.14/107.77	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
137.14/107.77	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
137.14/107.77	;
137.14/107.77	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
137.14/107.77	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
137.14/107.77	;
137.14/107.77	single_L fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
137.14/107.77	;
137.14/107.77	single_R (Branch key_l elt_l vuz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
137.14/107.77	;
137.14/107.77	size_l  = sizeFM fm_L;
137.14/107.77	;
137.14/107.77	size_r  = sizeFM fm_R;
137.14/107.77	} 
137.14/107.77	;
137.14/107.77	"
137.14/107.77	
137.14/107.77	----------------------------------------
137.14/107.77	
137.14/107.77	(8)
137.14/107.77	Obligation:
137.14/107.77	mainModule Main 
137.14/107.77	module FiniteMap where {
137.14/107.77	import qualified Main;
137.14/107.77	import qualified Maybe;
137.14/107.77	import qualified Prelude;
137.14/107.77	data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;
137.14/107.77	
137.14/107.77	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
137.14/107.77	}
137.14/107.77	delFromFM :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
137.14/107.77	delFromFM EmptyFM del_key = delFromFM4 EmptyFM del_key;
137.14/107.77	delFromFM (Branch key elt size fm_l fm_r) del_key = delFromFM3 (Branch key elt size fm_l fm_r) del_key;
137.14/107.77	
137.14/107.77	delFromFM0 key elt size fm_l fm_r del_key True = glueBal fm_l fm_r;
137.14/107.77	
137.14/107.77	delFromFM1 key elt size fm_l fm_r del_key True = mkBalBranch key elt (delFromFM fm_l del_key) fm_r;
137.14/107.77	delFromFM1 key elt size fm_l fm_r del_key False = delFromFM0 key elt size fm_l fm_r del_key (key == del_key);
137.14/107.77	
137.14/107.77	delFromFM2 key elt size fm_l fm_r del_key True = mkBalBranch key elt fm_l (delFromFM fm_r del_key);
137.14/107.77	delFromFM2 key elt size fm_l fm_r del_key False = delFromFM1 key elt size fm_l fm_r del_key (del_key < key);
137.14/107.77	
137.14/107.77	delFromFM3 (Branch key elt size fm_l fm_r) del_key = delFromFM2 key elt size fm_l fm_r del_key (del_key > key);
137.14/107.77	
137.14/107.77	delFromFM4 EmptyFM del_key = emptyFM;
137.14/107.77	delFromFM4 vyv vyw = delFromFM3 vyv vyw;
137.14/107.77	
137.14/107.77	delListFromFM :: Ord b => FiniteMap b a  ->  [b]  ->  FiniteMap b a;
137.14/107.77	delListFromFM fm keys = foldl delFromFM fm keys;
137.14/107.77	
137.14/107.77	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	deleteMax (Branch key elt xx fm_l EmptyFM) = fm_l;
137.14/107.77	deleteMax (Branch key elt xy fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
137.14/107.77	
137.14/107.77	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	deleteMin (Branch key elt xz EmptyFM fm_r) = fm_r;
137.14/107.77	deleteMin (Branch key elt yu fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
137.14/107.77	
137.14/107.77	emptyFM :: FiniteMap a b;
137.14/107.77	emptyFM = EmptyFM;
137.14/107.77	
137.14/107.77	findMax :: FiniteMap b a  ->  (b,a);
137.14/107.77	findMax (Branch key elt vuv vuw EmptyFM) = (key,elt);
137.14/107.77	findMax (Branch key elt vux vuy fm_r) = findMax fm_r;
137.14/107.77	
137.14/107.77	findMin :: FiniteMap a b  ->  (a,b);
137.14/107.77	findMin (Branch key elt yv EmptyFM yw) = (key,elt);
137.14/107.77	findMin (Branch key elt yx fm_l yy) = findMin fm_l;
137.14/107.77	
137.14/107.77	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
137.14/107.77	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
137.14/107.77	glueBal fm1 fm2 = glueBal2 fm1 fm2;
137.14/107.77	
137.14/107.77	glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where { 
137.14/107.77	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
137.14/107.77	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
137.14/107.77	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
137.14/107.77	mid_elt1 = mid_elt10 vv2;
137.14/107.77	mid_elt10 (ww,mid_elt1) = mid_elt1;
137.14/107.77	mid_elt2 = mid_elt20 vv3;
137.14/107.77	mid_elt20 (wv,mid_elt2) = mid_elt2;
137.14/107.77	mid_key1 = mid_key10 vv2;
137.14/107.77	mid_key10 (mid_key1,wx) = mid_key1;
137.14/107.77	mid_key2 = mid_key20 vv3;
137.14/107.77	mid_key20 (mid_key2,wy) = mid_key2;
137.14/107.77	vv2 = findMax fm1;
137.14/107.77	vv3 = findMin fm2;
137.14/107.77	 };
137.14/107.77	
137.14/107.77	glueBal3 fm1 EmptyFM = fm1;
137.14/107.77	glueBal3 vxu vxv = glueBal2 vxu vxv;
137.14/107.77	
137.14/107.77	glueBal4 EmptyFM fm2 = fm2;
137.14/107.77	glueBal4 vxx vxy = glueBal3 vxx vxy;
137.14/107.77	
137.14/107.77	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 
137.14/107.77	double_L fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu 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);
137.14/107.77	double_R (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv 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);
137.14/107.77	mkBalBranch0 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr);
137.14/107.77	mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr True = double_L fm_L fm_R;
137.14/107.77	mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr True = single_L fm_L fm_R;
137.14/107.77	mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr otherwise;
137.14/107.77	mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
137.14/107.77	mkBalBranch1 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr);
137.14/107.77	mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = double_R fm_L fm_R;
137.14/107.77	mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = single_R fm_L fm_R;
137.14/107.77	mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr otherwise;
137.14/107.77	mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
137.14/107.77	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
137.14/107.77	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
137.14/107.77	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
137.14/107.77	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
137.14/107.77	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
137.14/107.77	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
137.14/107.77	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
137.14/107.77	single_L fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
137.14/107.77	single_R (Branch key_l elt_l vuz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
137.14/107.77	size_l = sizeFM fm_L;
137.14/107.77	size_r = sizeFM fm_R;
137.14/107.77	 };
137.14/107.77	
137.14/107.77	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	mkBranch which key elt fm_l fm_r = let { 
137.14/107.77	result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
137.14/107.77	} in result where { 
137.14/107.77	balance_ok = True;
137.14/107.77	left_ok = left_ok0 fm_l key fm_l;
137.14/107.77	left_ok0 fm_l key EmptyFM = True;
137.14/107.77	left_ok0 fm_l key (Branch left_key yz zu zv zw) = let { 
137.14/107.77	biggest_left_key = fst (findMax fm_l);
137.14/107.77	} in biggest_left_key < key;
137.14/107.77	left_size = sizeFM fm_l;
137.14/107.77	right_ok = right_ok0 fm_r key fm_r;
137.14/107.77	right_ok0 fm_r key EmptyFM = True;
137.14/107.77	right_ok0 fm_r key (Branch right_key zx zy zz vuu) = let { 
137.14/107.77	smallest_right_key = fst (findMin fm_r);
137.14/107.77	} in key < smallest_right_key;
137.14/107.77	right_size = sizeFM fm_r;
137.14/107.77	unbox :: Int  ->  Int;
137.14/107.77	unbox x = x;
137.14/107.77	 };
137.14/107.77	
137.14/107.77	sIZE_RATIO :: Int;
137.14/107.77	sIZE_RATIO = 5;
137.14/107.77	
137.14/107.77	sizeFM :: FiniteMap a b  ->  Int;
137.14/107.77	sizeFM EmptyFM = 0;
137.14/107.77	sizeFM (Branch wz xu size xv xw) = size;
137.14/107.77	
137.14/107.77	}
137.14/107.77	module Maybe where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Main;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.14/107.77	module Main where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Maybe;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.14/107.77	
137.14/107.77	----------------------------------------
137.14/107.77	
137.14/107.77	(9) LetRed (EQUIVALENT)
137.14/107.77	Let/Where Reductions:
137.14/107.77	The bindings of the following Let/Where expression
137.14/107.77	"mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
137.14/107.77	double_L fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu 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);
137.14/107.77	;
137.14/107.77	double_R (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv 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);
137.14/107.77	;
137.14/107.77	mkBalBranch0 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr);
137.14/107.77	;
137.14/107.77	mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr True = double_L fm_L fm_R;
137.14/107.77	;
137.14/107.77	mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr True = single_L fm_L fm_R;
137.14/107.77	mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vwv vww vwx fm_rl fm_rr otherwise;
137.14/107.77	;
137.14/107.77	mkBalBranch02 fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vwv vww vwx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
137.14/107.77	;
137.14/107.77	mkBalBranch1 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr);
137.14/107.77	;
137.14/107.77	mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = double_R fm_L fm_R;
137.14/107.77	;
137.14/107.77	mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr True = single_R fm_L fm_R;
137.14/107.77	mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vvw vvx vvy fm_ll fm_lr otherwise;
137.14/107.77	;
137.14/107.77	mkBalBranch12 fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vvw vvx vvy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
137.14/107.77	;
137.14/107.77	mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
137.14/107.77	;
137.14/107.77	mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
137.14/107.77	mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
137.14/107.77	;
137.14/107.77	mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
137.14/107.77	mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
137.14/107.77	;
137.14/107.77	mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
137.14/107.77	mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
137.14/107.77	;
137.14/107.77	single_L fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
137.14/107.77	;
137.14/107.77	single_R (Branch key_l elt_l vuz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
137.14/107.77	;
137.14/107.77	size_l  = sizeFM fm_L;
137.14/107.77	;
137.14/107.77	size_r  = sizeFM fm_R;
137.14/107.77	} 
137.14/107.77	"
137.14/107.77	are unpacked to the following functions on top level
137.14/107.77	"mkBalBranch6MkBalBranch2 vyz vzu vzv vzw key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch1 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr);
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vyz vzu vzv vzw fm_L fm_R fm_R;
137.14/107.77	mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R (mkBalBranch6Size_l vyz vzu vzv vzw > sIZE_RATIO * mkBalBranch6Size_r vyz vzu vzv vzw);
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch00 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr True = mkBalBranch6Double_L vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch0 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr);
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch12 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
137.14/107.77	"
137.14/107.77	"mkBalBranch6Size_r vyz vzu vzv vzw = sizeFM vyz;
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr True = mkBalBranch6Single_R vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr otherwise;
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr True = mkBalBranch6Single_L vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr otherwise;
137.14/107.77	"
137.14/107.77	"mkBalBranch6Single_R vyz vzu vzv vzw (Branch key_l elt_l vuz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vzu vzv fm_lr fm_r);
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch5 vyz vzu vzv vzw key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch5 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R (mkBalBranch6Size_r vyz vzu vzv vzw > sIZE_RATIO * mkBalBranch6Size_l vyz vzu vzv vzw);
137.14/107.77	"
137.14/107.77	"mkBalBranch6Single_L vyz vzu vzv vzw fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vzu vzv fm_l fm_rl) fm_rr;
137.14/107.77	"
137.14/107.77	"mkBalBranch6Double_L vyz vzu vzv vzw fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vzu vzv fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
137.14/107.77	"
137.14/107.77	"mkBalBranch6Size_l vyz vzu vzv vzw = sizeFM vzw;
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch10 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr True = mkBalBranch6Double_R vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	"
137.14/107.77	"mkBalBranch6Double_R vyz vzu vzv vzw (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vzu vzv fm_lrr fm_r);
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch02 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
137.14/107.77	"
137.14/107.77	"mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vyz vzu vzv vzw fm_L fm_R fm_L;
137.14/107.77	mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vyz vzu vzv vzw key elt fm_L fm_R otherwise;
137.14/107.77	"
137.14/107.77	The bindings of the following Let/Where expression
137.14/107.77	"let {
137.14/107.77	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
137.14/107.77	} in result where {
137.14/107.77	balance_ok  = True;
137.14/107.77	;
137.14/107.77	left_ok  = left_ok0 fm_l key fm_l;
137.14/107.77	;
137.14/107.77	left_ok0 fm_l key EmptyFM = True;
137.14/107.77	left_ok0 fm_l key (Branch left_key yz zu zv zw) = let {
137.14/107.77	biggest_left_key  = fst (findMax fm_l);
137.14/107.77	} in biggest_left_key < key;
137.14/107.77	;
137.14/107.77	left_size  = sizeFM fm_l;
137.14/107.77	;
137.14/107.77	right_ok  = right_ok0 fm_r key fm_r;
137.14/107.77	;
137.14/107.77	right_ok0 fm_r key EmptyFM = True;
137.14/107.77	right_ok0 fm_r key (Branch right_key zx zy zz vuu) = let {
137.14/107.77	smallest_right_key  = fst (findMin fm_r);
137.14/107.77	} in key < smallest_right_key;
137.14/107.77	;
137.14/107.77	right_size  = sizeFM fm_r;
137.14/107.77	;
137.14/107.77	unbox x = x;
137.14/107.77	} 
137.14/107.77	"
137.14/107.77	are unpacked to the following functions on top level
137.14/107.77	"mkBranchRight_ok0 vzx vzy vzz fm_r key EmptyFM = True;
137.14/107.77	mkBranchRight_ok0 vzx vzy vzz fm_r key (Branch right_key zx zy zz vuu) = key < mkBranchRight_ok0Smallest_right_key fm_r;
137.14/107.77	"
137.14/107.77	"mkBranchRight_size vzx vzy vzz = sizeFM vzx;
137.14/107.77	"
137.14/107.77	"mkBranchLeft_ok vzx vzy vzz = mkBranchLeft_ok0 vzx vzy vzz vzy vzz vzy;
137.14/107.77	"
137.14/107.77	"mkBranchLeft_size vzx vzy vzz = sizeFM vzy;
137.14/107.77	"
137.14/107.77	"mkBranchRight_ok vzx vzy vzz = mkBranchRight_ok0 vzx vzy vzz vzx vzz vzx;
137.14/107.77	"
137.14/107.77	"mkBranchLeft_ok0 vzx vzy vzz fm_l key EmptyFM = True;
137.14/107.77	mkBranchLeft_ok0 vzx vzy vzz fm_l key (Branch left_key yz zu zv zw) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
137.14/107.77	"
137.14/107.77	"mkBranchBalance_ok vzx vzy vzz = True;
137.14/107.77	"
137.14/107.77	"mkBranchUnbox vzx vzy vzz x = x;
137.14/107.77	"
137.14/107.77	The bindings of the following Let/Where expression
137.14/107.77	"let {
137.14/107.77	result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
137.14/107.77	} in result"
137.14/107.77	are unpacked to the following functions on top level
137.14/107.77	"mkBranchResult wuu wuv wuw wux = Branch wuu wuv (mkBranchUnbox wuw wux wuu (1 + mkBranchLeft_size wuw wux wuu + mkBranchRight_size wuw wux wuu)) wux wuw;
137.14/107.77	"
137.14/107.77	The bindings of the following Let/Where expression
137.14/107.77	"glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where {
137.14/107.77	glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2;
137.14/107.77	;
137.14/107.77	glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2);
137.14/107.77	glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise;
137.14/107.77	;
137.14/107.77	mid_elt1  = mid_elt10 vv2;
137.14/107.77	;
137.14/107.77	mid_elt10 (ww,mid_elt1) = mid_elt1;
137.14/107.77	;
137.14/107.77	mid_elt2  = mid_elt20 vv3;
137.14/107.77	;
137.14/107.77	mid_elt20 (wv,mid_elt2) = mid_elt2;
137.14/107.77	;
137.14/107.77	mid_key1  = mid_key10 vv2;
137.14/107.77	;
137.14/107.77	mid_key10 (mid_key1,wx) = mid_key1;
137.14/107.77	;
137.14/107.77	mid_key2  = mid_key20 vv3;
137.14/107.77	;
137.14/107.77	mid_key20 (mid_key2,wy) = mid_key2;
137.14/107.77	;
137.14/107.77	vv2  = findMax fm1;
137.14/107.77	;
137.14/107.77	vv3  = findMin fm2;
137.14/107.77	} 
137.14/107.77	"
137.14/107.77	are unpacked to the following functions on top level
137.14/107.77	"glueBal2Mid_elt2 wuy wuz = glueBal2Mid_elt20 wuy wuz (glueBal2Vv3 wuy wuz);
137.14/107.77	"
137.14/107.77	"glueBal2Mid_elt1 wuy wuz = glueBal2Mid_elt10 wuy wuz (glueBal2Vv2 wuy wuz);
137.14/107.77	"
137.14/107.77	"glueBal2Mid_elt20 wuy wuz (wv,mid_elt2) = mid_elt2;
137.14/107.77	"
137.14/107.77	"glueBal2GlueBal1 wuy wuz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 wuy wuz) (glueBal2Mid_elt2 wuy wuz) fm1 (deleteMin fm2);
137.14/107.77	glueBal2GlueBal1 wuy wuz fm1 fm2 False = glueBal2GlueBal0 wuy wuz fm1 fm2 otherwise;
137.14/107.77	"
137.14/107.77	"glueBal2GlueBal0 wuy wuz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 wuy wuz) (glueBal2Mid_elt1 wuy wuz) (deleteMax fm1) fm2;
137.14/107.77	"
137.14/107.77	"glueBal2Mid_key10 wuy wuz (mid_key1,wx) = mid_key1;
137.14/107.77	"
137.14/107.77	"glueBal2Vv2 wuy wuz = findMax wuy;
137.14/107.77	"
137.14/107.77	"glueBal2Vv3 wuy wuz = findMin wuz;
137.14/107.77	"
137.14/107.77	"glueBal2Mid_key1 wuy wuz = glueBal2Mid_key10 wuy wuz (glueBal2Vv2 wuy wuz);
137.14/107.77	"
137.14/107.77	"glueBal2Mid_key2 wuy wuz = glueBal2Mid_key20 wuy wuz (glueBal2Vv3 wuy wuz);
137.14/107.77	"
137.14/107.77	"glueBal2Mid_elt10 wuy wuz (ww,mid_elt1) = mid_elt1;
137.14/107.77	"
137.14/107.77	"glueBal2Mid_key20 wuy wuz (mid_key2,wy) = mid_key2;
137.14/107.77	"
137.14/107.77	The bindings of the following Let/Where expression
137.14/107.77	"let {
137.14/107.77	smallest_right_key  = fst (findMin fm_r);
137.14/107.77	} in key < smallest_right_key"
137.14/107.77	are unpacked to the following functions on top level
137.14/107.77	"mkBranchRight_ok0Smallest_right_key wvu = fst (findMin wvu);
137.14/107.77	"
137.14/107.77	The bindings of the following Let/Where expression
137.14/107.77	"let {
137.14/107.77	biggest_left_key  = fst (findMax fm_l);
137.14/107.77	} in biggest_left_key < key"
137.14/107.77	are unpacked to the following functions on top level
137.14/107.77	"mkBranchLeft_ok0Biggest_left_key wvv = fst (findMax wvv);
137.14/107.77	"
137.14/107.77	
137.14/107.77	----------------------------------------
137.14/107.77	
137.14/107.77	(10)
137.14/107.77	Obligation:
137.14/107.77	mainModule Main 
137.14/107.77	module FiniteMap where {
137.14/107.77	import qualified Main;
137.14/107.77	import qualified Maybe;
137.14/107.77	import qualified Prelude;
137.14/107.77	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
137.14/107.77	
137.14/107.77	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
137.14/107.77	}
137.14/107.77	delFromFM :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
137.14/107.77	delFromFM EmptyFM del_key = delFromFM4 EmptyFM del_key;
137.14/107.77	delFromFM (Branch key elt size fm_l fm_r) del_key = delFromFM3 (Branch key elt size fm_l fm_r) del_key;
137.14/107.77	
137.14/107.77	delFromFM0 key elt size fm_l fm_r del_key True = glueBal fm_l fm_r;
137.14/107.77	
137.14/107.77	delFromFM1 key elt size fm_l fm_r del_key True = mkBalBranch key elt (delFromFM fm_l del_key) fm_r;
137.14/107.77	delFromFM1 key elt size fm_l fm_r del_key False = delFromFM0 key elt size fm_l fm_r del_key (key == del_key);
137.14/107.77	
137.14/107.77	delFromFM2 key elt size fm_l fm_r del_key True = mkBalBranch key elt fm_l (delFromFM fm_r del_key);
137.14/107.77	delFromFM2 key elt size fm_l fm_r del_key False = delFromFM1 key elt size fm_l fm_r del_key (del_key < key);
137.14/107.77	
137.14/107.77	delFromFM3 (Branch key elt size fm_l fm_r) del_key = delFromFM2 key elt size fm_l fm_r del_key (del_key > key);
137.14/107.77	
137.14/107.77	delFromFM4 EmptyFM del_key = emptyFM;
137.14/107.77	delFromFM4 vyv vyw = delFromFM3 vyv vyw;
137.14/107.77	
137.14/107.77	delListFromFM :: Ord a => FiniteMap a b  ->  [a]  ->  FiniteMap a b;
137.14/107.77	delListFromFM fm keys = foldl delFromFM fm keys;
137.14/107.77	
137.14/107.77	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	deleteMax (Branch key elt xx fm_l EmptyFM) = fm_l;
137.14/107.77	deleteMax (Branch key elt xy fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
137.14/107.77	
137.14/107.77	deleteMin :: Ord b => FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	deleteMin (Branch key elt xz EmptyFM fm_r) = fm_r;
137.14/107.77	deleteMin (Branch key elt yu fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
137.14/107.77	
137.14/107.77	emptyFM :: FiniteMap a b;
137.14/107.77	emptyFM = EmptyFM;
137.14/107.77	
137.14/107.77	findMax :: FiniteMap b a  ->  (b,a);
137.14/107.77	findMax (Branch key elt vuv vuw EmptyFM) = (key,elt);
137.14/107.77	findMax (Branch key elt vux vuy fm_r) = findMax fm_r;
137.14/107.77	
137.14/107.77	findMin :: FiniteMap a b  ->  (a,b);
137.14/107.77	findMin (Branch key elt yv EmptyFM yw) = (key,elt);
137.14/107.77	findMin (Branch key elt yx fm_l yy) = findMin fm_l;
137.14/107.77	
137.14/107.77	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
137.14/107.77	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
137.14/107.77	glueBal fm1 fm2 = glueBal2 fm1 fm2;
137.14/107.77	
137.14/107.77	glueBal2 fm1 fm2 = glueBal2GlueBal1 fm1 fm2 fm1 fm2 (sizeFM fm2 > sizeFM fm1);
137.14/107.77	
137.14/107.77	glueBal2GlueBal0 wuy wuz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 wuy wuz) (glueBal2Mid_elt1 wuy wuz) (deleteMax fm1) fm2;
137.14/107.77	
137.14/107.77	glueBal2GlueBal1 wuy wuz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 wuy wuz) (glueBal2Mid_elt2 wuy wuz) fm1 (deleteMin fm2);
137.14/107.77	glueBal2GlueBal1 wuy wuz fm1 fm2 False = glueBal2GlueBal0 wuy wuz fm1 fm2 otherwise;
137.14/107.77	
137.14/107.77	glueBal2Mid_elt1 wuy wuz = glueBal2Mid_elt10 wuy wuz (glueBal2Vv2 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_elt10 wuy wuz (ww,mid_elt1) = mid_elt1;
137.14/107.77	
137.14/107.77	glueBal2Mid_elt2 wuy wuz = glueBal2Mid_elt20 wuy wuz (glueBal2Vv3 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_elt20 wuy wuz (wv,mid_elt2) = mid_elt2;
137.14/107.77	
137.14/107.77	glueBal2Mid_key1 wuy wuz = glueBal2Mid_key10 wuy wuz (glueBal2Vv2 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_key10 wuy wuz (mid_key1,wx) = mid_key1;
137.14/107.77	
137.14/107.77	glueBal2Mid_key2 wuy wuz = glueBal2Mid_key20 wuy wuz (glueBal2Vv3 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_key20 wuy wuz (mid_key2,wy) = mid_key2;
137.14/107.77	
137.14/107.77	glueBal2Vv2 wuy wuz = findMax wuy;
137.14/107.77	
137.14/107.77	glueBal2Vv3 wuy wuz = findMin wuz;
137.14/107.77	
137.14/107.77	glueBal3 fm1 EmptyFM = fm1;
137.14/107.77	glueBal3 vxu vxv = glueBal2 vxu vxv;
137.14/107.77	
137.14/107.77	glueBal4 EmptyFM fm2 = fm2;
137.14/107.77	glueBal4 vxx vxy = glueBal3 vxx vxy;
137.14/107.77	
137.14/107.77	mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 fm_R key elt fm_L key elt fm_L fm_R (mkBalBranch6Size_l fm_R key elt fm_L + mkBalBranch6Size_r fm_R key elt fm_L < 2);
137.14/107.77	
137.14/107.77	mkBalBranch6Double_L vyz vzu vzv vzw fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vzu vzv fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
137.14/107.77	
137.14/107.77	mkBalBranch6Double_R vyz vzu vzv vzw (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vzu vzv fm_lrr fm_r);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch0 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch00 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr True = mkBalBranch6Double_L vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr True = mkBalBranch6Single_L vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr otherwise;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch02 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch1 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch10 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr True = mkBalBranch6Double_R vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr True = mkBalBranch6Single_R vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr otherwise;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch12 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch2 vyz vzu vzv vzw key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vyz vzu vzv vzw fm_L fm_R fm_L;
137.14/107.77	mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vyz vzu vzv vzw key elt fm_L fm_R otherwise;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vyz vzu vzv vzw fm_L fm_R fm_R;
137.14/107.77	mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R (mkBalBranch6Size_l vyz vzu vzv vzw > sIZE_RATIO * mkBalBranch6Size_r vyz vzu vzv vzw);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch5 vyz vzu vzv vzw key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch5 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R (mkBalBranch6Size_r vyz vzu vzv vzw > sIZE_RATIO * mkBalBranch6Size_l vyz vzu vzv vzw);
137.14/107.77	
137.14/107.77	mkBalBranch6Single_L vyz vzu vzv vzw fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vzu vzv fm_l fm_rl) fm_rr;
137.14/107.77	
137.14/107.77	mkBalBranch6Single_R vyz vzu vzv vzw (Branch key_l elt_l vuz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vzu vzv fm_lr fm_r);
137.14/107.77	
137.14/107.77	mkBalBranch6Size_l vyz vzu vzv vzw = sizeFM vzw;
137.14/107.77	
137.14/107.77	mkBalBranch6Size_r vyz vzu vzv vzw = sizeFM vyz;
137.14/107.77	
137.14/107.77	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l;
137.14/107.77	
137.14/107.77	mkBranchBalance_ok vzx vzy vzz = True;
137.14/107.77	
137.14/107.77	mkBranchLeft_ok vzx vzy vzz = mkBranchLeft_ok0 vzx vzy vzz vzy vzz vzy;
137.14/107.77	
137.14/107.77	mkBranchLeft_ok0 vzx vzy vzz fm_l key EmptyFM = True;
137.14/107.77	mkBranchLeft_ok0 vzx vzy vzz fm_l key (Branch left_key yz zu zv zw) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
137.14/107.77	
137.14/107.77	mkBranchLeft_ok0Biggest_left_key wvv = fst (findMax wvv);
137.14/107.77	
137.14/107.77	mkBranchLeft_size vzx vzy vzz = sizeFM vzy;
137.14/107.77	
137.14/107.77	mkBranchResult wuu wuv wuw wux = Branch wuu wuv (mkBranchUnbox wuw wux wuu (1 + mkBranchLeft_size wuw wux wuu + mkBranchRight_size wuw wux wuu)) wux wuw;
137.14/107.77	
137.14/107.77	mkBranchRight_ok vzx vzy vzz = mkBranchRight_ok0 vzx vzy vzz vzx vzz vzx;
137.14/107.77	
137.14/107.77	mkBranchRight_ok0 vzx vzy vzz fm_r key EmptyFM = True;
137.14/107.77	mkBranchRight_ok0 vzx vzy vzz fm_r key (Branch right_key zx zy zz vuu) = key < mkBranchRight_ok0Smallest_right_key fm_r;
137.14/107.77	
137.14/107.77	mkBranchRight_ok0Smallest_right_key wvu = fst (findMin wvu);
137.14/107.77	
137.14/107.77	mkBranchRight_size vzx vzy vzz = sizeFM vzx;
137.14/107.77	
137.14/107.77	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
137.14/107.77	mkBranchUnbox vzx vzy vzz x = x;
137.14/107.77	
137.14/107.77	sIZE_RATIO :: Int;
137.14/107.77	sIZE_RATIO = 5;
137.14/107.77	
137.14/107.77	sizeFM :: FiniteMap b a  ->  Int;
137.14/107.77	sizeFM EmptyFM = 0;
137.14/107.77	sizeFM (Branch wz xu size xv xw) = size;
137.14/107.77	
137.14/107.77	}
137.14/107.77	module Maybe where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Main;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.14/107.77	module Main where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Maybe;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.14/107.77	
137.14/107.77	----------------------------------------
137.14/107.77	
137.14/107.77	(11) NumRed (SOUND)
137.14/107.77	Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
137.14/107.77	----------------------------------------
137.14/107.77	
137.14/107.77	(12)
137.14/107.77	Obligation:
137.14/107.77	mainModule Main 
137.14/107.77	module FiniteMap where {
137.14/107.77	import qualified Main;
137.14/107.77	import qualified Maybe;
137.14/107.77	import qualified Prelude;
137.14/107.77	data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;
137.14/107.77	
137.14/107.77	instance (Eq a, Eq b) => Eq FiniteMap a b where { 
137.14/107.77	}
137.14/107.77	delFromFM :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
137.14/107.77	delFromFM EmptyFM del_key = delFromFM4 EmptyFM del_key;
137.14/107.77	delFromFM (Branch key elt size fm_l fm_r) del_key = delFromFM3 (Branch key elt size fm_l fm_r) del_key;
137.14/107.77	
137.14/107.77	delFromFM0 key elt size fm_l fm_r del_key True = glueBal fm_l fm_r;
137.14/107.77	
137.14/107.77	delFromFM1 key elt size fm_l fm_r del_key True = mkBalBranch key elt (delFromFM fm_l del_key) fm_r;
137.14/107.77	delFromFM1 key elt size fm_l fm_r del_key False = delFromFM0 key elt size fm_l fm_r del_key (key == del_key);
137.14/107.77	
137.14/107.77	delFromFM2 key elt size fm_l fm_r del_key True = mkBalBranch key elt fm_l (delFromFM fm_r del_key);
137.14/107.77	delFromFM2 key elt size fm_l fm_r del_key False = delFromFM1 key elt size fm_l fm_r del_key (del_key < key);
137.14/107.77	
137.14/107.77	delFromFM3 (Branch key elt size fm_l fm_r) del_key = delFromFM2 key elt size fm_l fm_r del_key (del_key > key);
137.14/107.77	
137.14/107.77	delFromFM4 EmptyFM del_key = emptyFM;
137.14/107.77	delFromFM4 vyv vyw = delFromFM3 vyv vyw;
137.14/107.77	
137.14/107.77	delListFromFM :: Ord a => FiniteMap a b  ->  [a]  ->  FiniteMap a b;
137.14/107.77	delListFromFM fm keys = foldl delFromFM fm keys;
137.14/107.77	
137.14/107.77	deleteMax :: Ord a => FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	deleteMax (Branch key elt xx fm_l EmptyFM) = fm_l;
137.14/107.77	deleteMax (Branch key elt xy fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r);
137.14/107.77	
137.14/107.77	deleteMin :: Ord a => FiniteMap a b  ->  FiniteMap a b;
137.14/107.77	deleteMin (Branch key elt xz EmptyFM fm_r) = fm_r;
137.14/107.77	deleteMin (Branch key elt yu fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r;
137.14/107.77	
137.14/107.77	emptyFM :: FiniteMap a b;
137.14/107.77	emptyFM = EmptyFM;
137.14/107.77	
137.14/107.77	findMax :: FiniteMap b a  ->  (b,a);
137.14/107.77	findMax (Branch key elt vuv vuw EmptyFM) = (key,elt);
137.14/107.77	findMax (Branch key elt vux vuy fm_r) = findMax fm_r;
137.14/107.77	
137.14/107.77	findMin :: FiniteMap a b  ->  (a,b);
137.14/107.77	findMin (Branch key elt yv EmptyFM yw) = (key,elt);
137.14/107.77	findMin (Branch key elt yx fm_l yy) = findMin fm_l;
137.14/107.77	
137.14/107.77	glueBal :: Ord b => FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2;
137.14/107.77	glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM;
137.14/107.77	glueBal fm1 fm2 = glueBal2 fm1 fm2;
137.14/107.77	
137.14/107.77	glueBal2 fm1 fm2 = glueBal2GlueBal1 fm1 fm2 fm1 fm2 (sizeFM fm2 > sizeFM fm1);
137.14/107.77	
137.14/107.77	glueBal2GlueBal0 wuy wuz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 wuy wuz) (glueBal2Mid_elt1 wuy wuz) (deleteMax fm1) fm2;
137.14/107.77	
137.14/107.77	glueBal2GlueBal1 wuy wuz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 wuy wuz) (glueBal2Mid_elt2 wuy wuz) fm1 (deleteMin fm2);
137.14/107.77	glueBal2GlueBal1 wuy wuz fm1 fm2 False = glueBal2GlueBal0 wuy wuz fm1 fm2 otherwise;
137.14/107.77	
137.14/107.77	glueBal2Mid_elt1 wuy wuz = glueBal2Mid_elt10 wuy wuz (glueBal2Vv2 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_elt10 wuy wuz (ww,mid_elt1) = mid_elt1;
137.14/107.77	
137.14/107.77	glueBal2Mid_elt2 wuy wuz = glueBal2Mid_elt20 wuy wuz (glueBal2Vv3 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_elt20 wuy wuz (wv,mid_elt2) = mid_elt2;
137.14/107.77	
137.14/107.77	glueBal2Mid_key1 wuy wuz = glueBal2Mid_key10 wuy wuz (glueBal2Vv2 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_key10 wuy wuz (mid_key1,wx) = mid_key1;
137.14/107.77	
137.14/107.77	glueBal2Mid_key2 wuy wuz = glueBal2Mid_key20 wuy wuz (glueBal2Vv3 wuy wuz);
137.14/107.77	
137.14/107.77	glueBal2Mid_key20 wuy wuz (mid_key2,wy) = mid_key2;
137.14/107.77	
137.14/107.77	glueBal2Vv2 wuy wuz = findMax wuy;
137.14/107.77	
137.14/107.77	glueBal2Vv3 wuy wuz = findMin wuz;
137.14/107.77	
137.14/107.77	glueBal3 fm1 EmptyFM = fm1;
137.14/107.77	glueBal3 vxu vxv = glueBal2 vxu vxv;
137.14/107.77	
137.14/107.77	glueBal4 EmptyFM fm2 = fm2;
137.14/107.77	glueBal4 vxx vxy = glueBal3 vxx vxy;
137.14/107.77	
137.14/107.77	mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 fm_R key elt fm_L key elt fm_L fm_R (mkBalBranch6Size_l fm_R key elt fm_L + mkBalBranch6Size_r fm_R key elt fm_L < Pos (Succ (Succ Zero)));
137.14/107.77	
137.14/107.77	mkBalBranch6Double_L vyz vzu vzv vzw fm_l (Branch key_r elt_r vvz (Branch key_rl elt_rl vwu 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))))))) vzu vzv fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr);
137.14/107.77	
137.14/107.77	mkBalBranch6Double_R vyz vzu vzv vzw (Branch key_l elt_l vvu fm_ll (Branch key_lr elt_lr vvv 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))))))))))))) vzu vzv fm_lrr fm_r);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch0 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch00 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr True = mkBalBranch6Double_L vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr True = mkBalBranch6Single_L vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr otherwise;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch02 vyz vzu vzv vzw fm_L fm_R (Branch vwv vww vwx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vyz vzu vzv vzw fm_L fm_R vwv vww vwx fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch1 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch10 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr True = mkBalBranch6Double_R vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr True = mkBalBranch6Single_R vyz vzu vzv vzw fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr otherwise;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch12 vyz vzu vzv vzw fm_L fm_R (Branch vvw vvx vvy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vyz vzu vzv vzw fm_L fm_R vvw vvx vvy fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch2 vyz vzu vzv vzw key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vyz vzu vzv vzw fm_L fm_R fm_L;
137.14/107.77	mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vyz vzu vzv vzw key elt fm_L fm_R otherwise;
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vyz vzu vzv vzw fm_L fm_R fm_R;
137.14/107.77	mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vyz vzu vzv vzw key elt fm_L fm_R (mkBalBranch6Size_l vyz vzu vzv vzw > sIZE_RATIO * mkBalBranch6Size_r vyz vzu vzv vzw);
137.14/107.77	
137.14/107.77	mkBalBranch6MkBalBranch5 vyz vzu vzv vzw key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
137.14/107.77	mkBalBranch6MkBalBranch5 vyz vzu vzv vzw key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vyz vzu vzv vzw key elt fm_L fm_R (mkBalBranch6Size_r vyz vzu vzv vzw > sIZE_RATIO * mkBalBranch6Size_l vyz vzu vzv vzw);
137.14/107.77	
137.14/107.77	mkBalBranch6Single_L vyz vzu vzv vzw fm_l (Branch key_r elt_r vwy fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) vzu vzv fm_l fm_rl) fm_rr;
137.14/107.77	
137.14/107.77	mkBalBranch6Single_R vyz vzu vzv vzw (Branch key_l elt_l vuz 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)))))))))) vzu vzv fm_lr fm_r);
137.14/107.77	
137.14/107.77	mkBalBranch6Size_l vyz vzu vzv vzw = sizeFM vzw;
137.14/107.77	
137.14/107.77	mkBalBranch6Size_r vyz vzu vzv vzw = sizeFM vyz;
137.14/107.77	
137.14/107.77	mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
137.14/107.77	mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l;
137.14/107.77	
137.14/107.77	mkBranchBalance_ok vzx vzy vzz = True;
137.14/107.77	
137.14/107.77	mkBranchLeft_ok vzx vzy vzz = mkBranchLeft_ok0 vzx vzy vzz vzy vzz vzy;
137.14/107.77	
137.14/107.77	mkBranchLeft_ok0 vzx vzy vzz fm_l key EmptyFM = True;
137.14/107.77	mkBranchLeft_ok0 vzx vzy vzz fm_l key (Branch left_key yz zu zv zw) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
137.14/107.77	
137.14/107.77	mkBranchLeft_ok0Biggest_left_key wvv = fst (findMax wvv);
137.14/107.77	
137.14/107.77	mkBranchLeft_size vzx vzy vzz = sizeFM vzy;
137.14/107.77	
137.14/107.77	mkBranchResult wuu wuv wuw wux = Branch wuu wuv (mkBranchUnbox wuw wux wuu (Pos (Succ Zero) + mkBranchLeft_size wuw wux wuu + mkBranchRight_size wuw wux wuu)) wux wuw;
137.14/107.77	
137.14/107.77	mkBranchRight_ok vzx vzy vzz = mkBranchRight_ok0 vzx vzy vzz vzx vzz vzx;
137.14/107.77	
137.14/107.77	mkBranchRight_ok0 vzx vzy vzz fm_r key EmptyFM = True;
137.14/107.77	mkBranchRight_ok0 vzx vzy vzz fm_r key (Branch right_key zx zy zz vuu) = key < mkBranchRight_ok0Smallest_right_key fm_r;
137.14/107.77	
137.14/107.77	mkBranchRight_ok0Smallest_right_key wvu = fst (findMin wvu);
137.14/107.77	
137.14/107.77	mkBranchRight_size vzx vzy vzz = sizeFM vzx;
137.14/107.77	
137.14/107.77	mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
137.14/107.77	mkBranchUnbox vzx vzy vzz x = x;
137.14/107.77	
137.14/107.77	sIZE_RATIO :: Int;
137.14/107.77	sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero)))));
137.14/107.77	
137.14/107.77	sizeFM :: FiniteMap a b  ->  Int;
137.14/107.77	sizeFM EmptyFM = Pos Zero;
137.14/107.77	sizeFM (Branch wz xu size xv xw) = size;
137.14/107.77	
137.14/107.77	}
137.14/107.77	module Maybe where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Main;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.14/107.77	module Main where {
137.14/107.77	import qualified FiniteMap;
137.14/107.77	import qualified Maybe;
137.14/107.77	import qualified Prelude;
137.14/107.77	}
137.30/107.85	EOF