/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.hs /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


MAYBE
proof of /export/starexec/sandbox/benchmark/theBenchmark.hs
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


H-Termination with start terms of the given HASKELL could not be shown:

(0) HASKELL
(1) LR [EQUIVALENT, 0 ms]
(2) HASKELL
(3) CR [EQUIVALENT, 0 ms]
(4) HASKELL
(5) IFR [EQUIVALENT, 0 ms]
(6) HASKELL
(7) BR [EQUIVALENT, 0 ms]
(8) HASKELL
(9) COR [EQUIVALENT, 0 ms]
(10) HASKELL
(11) LetRed [EQUIVALENT, 0 ms]
(12) HASKELL
(13) NumRed [SOUND, 25 ms]
(14) HASKELL


----------------------------------------

(0)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM fm key elt = addToFM_C (\old new ->new) fm key elt;

addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM_C combiner EmptyFM key elt = unitFM key elt;
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
 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;

emptyFM :: FiniteMap b a;
emptyFM = EmptyFM;

findMax :: FiniteMap a b  ->  (a,b);
findMax (Branch key elt _ _ EmptyFM) = (key,elt);
findMax (Branch key elt _ _ fm_r) = findMax fm_r;

findMin :: FiniteMap b a  ->  (b,a);
findMin (Branch key elt _ EmptyFM _) = (key,elt);
findMin (Branch key elt _ fm_l _) = findMin fm_l;

fmToList :: FiniteMap b a  ->  [(b,a)];
fmToList fm = foldFM (\key elt rest ->(key,elt) : rest) [] fm;

foldFM :: (b  ->  c  ->  a  ->  a)  ->  a  ->  FiniteMap b c  ->  a;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
 | size_r > sIZE_RATIO * size_l = case fm_R of { 
Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
 | otherwise -> double_L fm_L fm_R; 
 } 
 | size_l > sIZE_RATIO * size_r = case fm_L of { 
Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
 | otherwise -> double_R fm_L fm_R; 
 } 
 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
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);
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);
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;
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);
size_l = sizeFM fm_L;
size_r = sizeFM fm_R;
 };

mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBranch which key elt fm_l fm_r = let { 
result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result where { 
balance_ok = True;
left_ok = case fm_l of { 
EmptyFM-> True; 
Branch left_key _ _ _ _-> let { 
biggest_left_key = fst (findMax fm_l);
} in biggest_left_key < key; 
 } ;
left_size = sizeFM fm_l;
right_ok = case fm_r of { 
EmptyFM-> True; 
Branch right_key _ _ _ _-> let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key; 
 } ;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
size_l = sizeFM fm_l;
size_r = sizeFM fm_r;
 };

plusFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 
gts = splitGT fm1 split_key;
lts = splitLT fm1 split_key;
new_elt = case lookupFM fm1 split_key of { 
Nothing-> elt2; 
Just elt1-> combiner elt1 elt2; 
 } ;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap b a  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch _ _ size _ _) = size;

splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitGT EmptyFM split_key = emptyFM;
splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
 | otherwise = fm_r;

splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
splitLT EmptyFM split_key = emptyFM;
splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
 | otherwise = fm_l;

unitFM :: b  ->  a  ->  FiniteMap b a;
unitFM key elt = Branch key elt 1 emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(1) LR (EQUIVALENT)
Lambda Reductions:
The following Lambda expression
"\oldnew->new"
is transformed to
"addToFM0 old new = new;
"
The following Lambda expression
"\keyeltrest->(key,elt) : rest"
is transformed to
"fmToList0 key elt rest = (key,elt) : rest;
"

----------------------------------------

(2)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM fm key elt = addToFM_C addToFM0 fm key elt;

addToFM0 old new = new;

addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM_C combiner EmptyFM key elt = unitFM key elt;
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
 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap b a  ->  (b,a);
findMax (Branch key elt _ _ EmptyFM) = (key,elt);
findMax (Branch key elt _ _ fm_r) = findMax fm_r;

findMin :: FiniteMap b a  ->  (b,a);
findMin (Branch key elt _ EmptyFM _) = (key,elt);
findMin (Branch key elt _ fm_l _) = findMin fm_l;

fmToList :: FiniteMap a b  ->  [(a,b)];
fmToList fm = foldFM fmToList0 [] fm;

fmToList0 key elt rest = (key,elt) : rest;

foldFM :: (b  ->  c  ->  a  ->  a)  ->  a  ->  FiniteMap b c  ->  a;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
 | size_r > sIZE_RATIO * size_l = case fm_R of { 
Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R
 | otherwise -> double_L fm_L fm_R; 
 } 
 | size_l > sIZE_RATIO * size_r = case fm_L of { 
Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R
 | otherwise -> double_R fm_L fm_R; 
 } 
 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
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);
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);
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;
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);
size_l = sizeFM fm_L;
size_r = sizeFM fm_R;
 };

mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBranch which key elt fm_l fm_r = let { 
result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result where { 
balance_ok = True;
left_ok = case fm_l of { 
EmptyFM-> True; 
Branch left_key _ _ _ _-> let { 
biggest_left_key = fst (findMax fm_l);
} in biggest_left_key < key; 
 } ;
left_size = sizeFM fm_l;
right_ok = case fm_r of { 
EmptyFM-> True; 
Branch right_key _ _ _ _-> let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key; 
 } ;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
size_l = sizeFM fm_l;
size_r = sizeFM fm_r;
 };

plusFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 
gts = splitGT fm1 split_key;
lts = splitLT fm1 split_key;
new_elt = case lookupFM fm1 split_key of { 
Nothing-> elt2; 
Just elt1-> combiner elt1 elt2; 
 } ;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap b a  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch _ _ size _ _) = size;

splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitGT EmptyFM split_key = emptyFM;
splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
 | otherwise = fm_r;

splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
splitLT EmptyFM split_key = emptyFM;
splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
 | otherwise = fm_l;

unitFM :: b  ->  a  ->  FiniteMap b a;
unitFM key elt = Branch key elt 1 emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(3) CR (EQUIVALENT)
Case Reductions:
The following Case expression
"case compare x y of {
EQ  -> o;
LT  -> LT;
GT  -> GT}
"
is transformed to
"primCompAux0 o EQ = o;
primCompAux0 o LT = LT;
primCompAux0 o GT = GT;
"
The following Case expression
"case lookupFM fm1 split_key of {
Nothing  -> elt2;
Just elt1  -> combiner elt1 elt2}
"
is transformed to
"new_elt0 elt2 combiner Nothing = elt2;
new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2;
"
The following Case expression
"case fm_r of {
EmptyFM  -> True;
Branch right_key _ _ _ _  -> let {
smallest_right_key  = fst (findMin fm_r);
} in key < smallest_right_key}
"
is transformed to
"right_ok0 fm_r key EmptyFM = True;
right_ok0 fm_r key (Branch right_key _ _ _ _) = let {
smallest_right_key  = fst (findMin fm_r);
} in key < smallest_right_key;
"
The following Case expression
"case fm_l of {
EmptyFM  -> True;
Branch left_key _ _ _ _  -> let {
biggest_left_key  = fst (findMax fm_l);
} in biggest_left_key < key}
"
is transformed to
"left_ok0 fm_l key EmptyFM = True;
left_ok0 fm_l key (Branch left_key _ _ _ _) = let {
biggest_left_key  = fst (findMax fm_l);
} in biggest_left_key < key;
"
The following Case expression
"case fm_R of {
Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R}
"
is transformed to
"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;
"
The following Case expression
"case fm_L of {
Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R}
"
is transformed to
"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;
"

----------------------------------------

(4)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM fm key elt = addToFM_C addToFM0 fm key elt;

addToFM0 old new = new;

addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM_C combiner EmptyFM key elt = unitFM key elt;
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
 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap b a  ->  (b,a);
findMax (Branch key elt _ _ EmptyFM) = (key,elt);
findMax (Branch key elt _ _ fm_r) = findMax fm_r;

findMin :: FiniteMap a b  ->  (a,b);
findMin (Branch key elt _ EmptyFM _) = (key,elt);
findMin (Branch key elt _ fm_l _) = findMin fm_l;

fmToList :: FiniteMap b a  ->  [(b,a)];
fmToList fm = foldFM fmToList0 [] fm;

fmToList0 key elt rest = (key,elt) : rest;

foldFM :: (b  ->  a  ->  c  ->  c)  ->  c  ->  FiniteMap b a  ->  c;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
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);
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);
mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
 | otherwise = double_L fm_L fm_R;
mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
 | otherwise = double_R fm_L fm_R;
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;
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);
size_l = sizeFM fm_L;
size_r = sizeFM fm_R;
 };

mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBranch which key elt fm_l fm_r = let { 
result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result where { 
balance_ok = True;
left_ok = left_ok0 fm_l key fm_l;
left_ok0 fm_l key EmptyFM = True;
left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
biggest_left_key = fst (findMax fm_l);
} in biggest_left_key < key;
left_size = sizeFM fm_l;
right_ok = right_ok0 fm_r key fm_r;
right_ok0 fm_r key EmptyFM = True;
right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
size_l = sizeFM fm_l;
size_r = sizeFM fm_r;
 };

plusFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 
gts = splitGT fm1 split_key;
lts = splitLT fm1 split_key;
new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key);
new_elt0 elt2 combiner Nothing = elt2;
new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap a b  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch _ _ size _ _) = size;

splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
splitGT EmptyFM split_key = emptyFM;
splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
 | otherwise = fm_r;

splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitLT EmptyFM split_key = emptyFM;
splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
 | otherwise = fm_l;

unitFM :: a  ->  b  ->  FiniteMap a b;
unitFM key elt = Branch key elt 1 emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(5) IFR (EQUIVALENT)
If Reductions:
The following If expression
"if primGEqNatS x y then Succ (primDivNatS (primMinusNatS x y) (Succ y)) else Zero"
is transformed to
"primDivNatS0 x y True = Succ (primDivNatS (primMinusNatS x y) (Succ y));
primDivNatS0 x y False = Zero;
"
The following If expression
"if primGEqNatS x y then primModNatS (primMinusNatS x y) (Succ y) else Succ x"
is transformed to
"primModNatS0 x y True = primModNatS (primMinusNatS x y) (Succ y);
primModNatS0 x y False = Succ x;
"

----------------------------------------

(6)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM fm key elt = addToFM_C addToFM0 fm key elt;

addToFM0 old new = new;

addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM_C combiner EmptyFM key elt = unitFM key elt;
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
 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap b a  ->  (b,a);
findMax (Branch key elt _ _ EmptyFM) = (key,elt);
findMax (Branch key elt _ _ fm_r) = findMax fm_r;

findMin :: FiniteMap b a  ->  (b,a);
findMin (Branch key elt _ EmptyFM _) = (key,elt);
findMin (Branch key elt _ fm_l _) = findMin fm_l;

fmToList :: FiniteMap a b  ->  [(a,b)];
fmToList fm = foldFM fmToList0 [] fm;

fmToList0 key elt rest = (key,elt) : rest;

foldFM :: (c  ->  a  ->  b  ->  b)  ->  b  ->  FiniteMap c a  ->  b;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt _ fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
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);
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);
mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
 | otherwise = double_L fm_L fm_R;
mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
 | otherwise = double_R fm_L fm_R;
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;
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);
size_l = sizeFM fm_L;
size_r = sizeFM fm_R;
 };

mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBranch which key elt fm_l fm_r = let { 
result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result where { 
balance_ok = True;
left_ok = left_ok0 fm_l key fm_l;
left_ok0 fm_l key EmptyFM = True;
left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 
biggest_left_key = fst (findMax fm_l);
} in biggest_left_key < key;
left_size = sizeFM fm_l;
right_ok = right_ok0 fm_r key fm_r;
right_ok0 fm_r key EmptyFM = True;
right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr)  | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr
 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r)
 | otherwise = mkBranch 13 key elt fm_l fm_r where { 
size_l = sizeFM fm_l;
size_r = sizeFM fm_r;
 };

plusFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 
gts = splitGT fm1 split_key;
lts = splitLT fm1 split_key;
new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key);
new_elt0 elt2 combiner Nothing = elt2;
new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap a b  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch _ _ size _ _) = size;

splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
splitGT EmptyFM split_key = emptyFM;
splitGT (Branch key elt _ fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
 | otherwise = fm_r;

splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
splitLT EmptyFM split_key = emptyFM;
splitLT (Branch key elt _ fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
 | otherwise = fm_l;

unitFM :: a  ->  b  ->  FiniteMap a b;
unitFM key elt = Branch key elt 1 emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(7) BR (EQUIVALENT)
Replaced joker patterns by fresh variables and removed binding patterns.

Binding Reductions:
The bind variable of the following binding Pattern
"fm_l@(Branch vuv vuw vux vuy vuz)"
is replaced by the following term
"Branch vuv vuw vux vuy vuz"
The bind variable of the following binding Pattern
"fm_r@(Branch vvv vvw vvx vvy vvz)"
is replaced by the following term
"Branch vvv vvw vvx vvy vvz"

----------------------------------------

(8)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM fm key elt = addToFM_C addToFM0 fm key elt;

addToFM0 old new = new;

addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM_C combiner EmptyFM key elt = unitFM key elt;
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
 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt)
 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap a b  ->  (a,b);
findMax (Branch key elt vxy vxz EmptyFM) = (key,elt);
findMax (Branch key elt vyu vyv fm_r) = findMax fm_r;

findMin :: FiniteMap b a  ->  (b,a);
findMin (Branch key elt wvw EmptyFM wvx) = (key,elt);
findMin (Branch key elt wvy fm_l wvz) = findMin fm_l;

fmToList :: FiniteMap a b  ->  [(a,b)];
fmToList fm = foldFM fmToList0 [] fm;

fmToList0 key elt rest = (key,elt) : rest;

foldFM :: (a  ->  b  ->  c  ->  c)  ->  c  ->  FiniteMap a b  ->  c;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord a => FiniteMap a b  ->  a  ->  Maybe b;
lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt wvv fm_l fm_r) key_to_find  | key_to_find < key = lookupFM fm_l key_to_find
 | key_to_find > key = lookupFM fm_r key_to_find
 | otherwise = Just elt;

mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBalBranch key elt fm_L fm_R  | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R
 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R
 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L
 | otherwise = mkBranch 2 key elt fm_L fm_R where { 
double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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);
double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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);
mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
 | otherwise = double_L fm_L fm_R;
mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
 | otherwise = double_R fm_L fm_R;
single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
size_l = sizeFM fm_L;
size_r = sizeFM fm_R;
 };

mkBranch :: Ord b => Int  ->  b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBranch which key elt fm_l fm_r = let { 
result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result where { 
balance_ok = True;
left_ok = left_ok0 fm_l key fm_l;
left_ok0 fm_l key EmptyFM = True;
left_ok0 fm_l key (Branch left_key vww vwx vwy vwz) = let { 
biggest_left_key = fst (findMax fm_l);
} in biggest_left_key < key;
left_size = sizeFM fm_l;
right_ok = right_ok0 fm_r key fm_r;
right_ok0 fm_r key EmptyFM = True;
right_ok0 fm_r key (Branch right_key vxu vxv vxw vxx) = let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

mkVBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz)  | sIZE_RATIO * size_l < size_r = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz
 | sIZE_RATIO * size_r < size_l = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz))
 | otherwise = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) where { 
size_l = sizeFM (Branch vuv vuw vux vuy vuz);
size_r = sizeFM (Branch vvv vvw vvx vvy vvz);
 };

plusFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 
gts = splitGT fm1 split_key;
lts = splitLT fm1 split_key;
new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key);
new_elt0 elt2 combiner Nothing = elt2;
new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap a b  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch wux wuy size wuz wvu) = size;

splitGT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
splitGT EmptyFM split_key = emptyFM;
splitGT (Branch key elt vwu fm_l fm_r) split_key  | split_key > key = splitGT fm_r split_key
 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r
 | otherwise = fm_r;

splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitLT EmptyFM split_key = emptyFM;
splitLT (Branch key elt vwv fm_l fm_r) split_key  | split_key < key = splitLT fm_l split_key
 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key)
 | otherwise = fm_l;

unitFM :: a  ->  b  ->  FiniteMap a b;
unitFM key elt = Branch key elt 1 emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(9) COR (EQUIVALENT)
Cond Reductions:
The following Function with conditions
"absReal x|x >= 0x|otherwise`negate` x;
"
is transformed to
"absReal x = absReal2 x;
"
"absReal0 x True = `negate` x;
"
"absReal1 x True = x;
absReal1 x False = absReal0 x otherwise;
"
"absReal2 x = absReal1 x (x >= 0);
"
The following Function with conditions
"gcd' x 0 = x;
gcd' x y = gcd' y (x `rem` y);
"
is transformed to
"gcd' x wwu = gcd'2 x wwu;
gcd' x y = gcd'0 x y;
"
"gcd'0 x y = gcd' y (x `rem` y);
"
"gcd'1 True x wwu = x;
gcd'1 wwv www wwx = gcd'0 www wwx;
"
"gcd'2 x wwu = gcd'1 (wwu == 0) x wwu;
gcd'2 wwy wwz = gcd'0 wwy wwz;
"
The following Function with conditions
"gcd 0 0 = error [];
gcd x y = gcd' (abs x) (abs y) where {
gcd' x 0 = x;
gcd' x y = gcd' y (x `rem` y);
} 
;
"
is transformed to
"gcd wxu wxv = gcd3 wxu wxv;
gcd x y = gcd0 x y;
"
"gcd0 x y = gcd' (abs x) (abs y) where {
gcd' x wwu = gcd'2 x wwu;
gcd' x y = gcd'0 x y;
;
gcd'0 x y = gcd' y (x `rem` y);
;
gcd'1 True x wwu = x;
gcd'1 wwv www wwx = gcd'0 www wwx;
;
gcd'2 x wwu = gcd'1 (wwu == 0) x wwu;
gcd'2 wwy wwz = gcd'0 wwy wwz;
} 
;
"
"gcd1 True wxu wxv = error [];
gcd1 wxw wxx wxy = gcd0 wxx wxy;
"
"gcd2 True wxu wxv = gcd1 (wxv == 0) wxu wxv;
gcd2 wxz wyu wyv = gcd0 wyu wyv;
"
"gcd3 wxu wxv = gcd2 (wxu == 0) wxu wxv;
gcd3 wyw wyx = gcd0 wyw wyx;
"
The following Function with conditions
"undefined |Falseundefined;
"
is transformed to
"undefined  = undefined1;
"
"undefined0 True = undefined;
"
"undefined1  = undefined0 False;
"
The following Function with conditions
"reduce x y|y == 0error []|otherwisex `quot` d :% (y `quot` d) where {
d  = gcd x y;
} 
;
"
is transformed to
"reduce x y = reduce2 x y;
"
"reduce2 x y = reduce1 x y (y == 0) where {
d  = gcd x y;
;
reduce0 x y True = x `quot` d :% (y `quot` d);
;
reduce1 x y True = error [];
reduce1 x y False = reduce0 x y otherwise;
} 
;
"
The following Function with conditions
"compare x y|x == yEQ|x <= yLT|otherwiseGT;
"
is transformed to
"compare x y = compare3 x y;
"
"compare2 x y True = EQ;
compare2 x y False = compare1 x y (x <= y);
"
"compare1 x y True = LT;
compare1 x y False = compare0 x y otherwise;
"
"compare0 x y True = GT;
"
"compare3 x y = compare2 x y (x == y);
"
The following Function with conditions
"addToFM_C combiner EmptyFM key elt = unitFM key elt;
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;
"
is transformed to
"addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
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;
"
"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);
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;
"
"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;
"
"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;
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);
"
"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);
"
"addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx;
"
The following Function with conditions
"mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz)|sIZE_RATIO * size_l < size_rmkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz|sIZE_RATIO * size_r < size_lmkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz))|otherwisemkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) where {
size_l  = sizeFM (Branch vuv vuw vux vuy vuz);
;
size_r  = sizeFM (Branch vvv vvw vvx vvy vvz);
} 
;
"
is transformed to
"mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);
"
"mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_l < size_r) where {
mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);
;
mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz));
mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise;
;
mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz;
mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_r < size_l);
;
size_l  = sizeFM (Branch vuv vuw vux vuy vuz);
;
size_r  = sizeFM (Branch vvv vvw vvx vvy vvz);
} 
;
"
"mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy;
"
"mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx;
"
The following Function with conditions
"splitGT EmptyFM split_key = emptyFM;
splitGT (Branch key elt vwu fm_l fm_r) split_key|split_key > keysplitGT fm_r split_key|split_key < keymkVBalBranch key elt (splitGT fm_l split_key) fm_r|otherwisefm_r;
"
is transformed to
"splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key;
"
"splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise;
"
"splitGT0 key elt vwu fm_l fm_r split_key True = fm_r;
"
"splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key;
splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key);
"
"splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key);
"
"splitGT4 EmptyFM split_key = emptyFM;
splitGT4 xwu xwv = splitGT3 xwu xwv;
"
The following Function with conditions
"splitLT EmptyFM split_key = emptyFM;
splitLT (Branch key elt vwv fm_l fm_r) split_key|split_key < keysplitLT fm_l split_key|split_key > keymkVBalBranch key elt fm_l (splitLT fm_r split_key)|otherwisefm_l;
"
is transformed to
"splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key;
"
"splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key;
splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key);
"
"splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise;
"
"splitLT0 key elt vwv fm_l fm_r split_key True = fm_l;
"
"splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key);
"
"splitLT4 EmptyFM split_key = emptyFM;
splitLT4 xwy xwz = splitLT3 xwy xwz;
"
The following Function with conditions
"mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
"
is transformed to
"mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr);
"
"mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R;
"
"mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise;
"
"mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
"
The following Function with conditions
"mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
"
is transformed to
"mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr);
"
"mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise;
"
"mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R;
"
"mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
"
The following Function with conditions
"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 {
double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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);
;
double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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);
;
mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
;
mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
;
single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
;
single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
;
size_l  = sizeFM fm_L;
;
size_r  = sizeFM fm_R;
} 
;
"
is transformed to
"mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;
"
"mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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);
;
double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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);
;
mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr);
;
mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R;
;
mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise;
;
mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
;
mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr);
;
mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R;
;
mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise;
;
mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
;
mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
;
mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
;
mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
;
mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
;
single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
;
single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
;
size_l  = sizeFM fm_L;
;
size_r  = sizeFM fm_R;
} 
;
"
The following Function with conditions
"lookupFM EmptyFM key = Nothing;
lookupFM (Branch key elt wvv fm_l fm_r) key_to_find|key_to_find < keylookupFM fm_l key_to_find|key_to_find > keylookupFM fm_r key_to_find|otherwiseJust elt;
"
is transformed to
"lookupFM EmptyFM key = lookupFM4 EmptyFM key;
lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find;
"
"lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key);
"
"lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt;
"
"lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise;
"
"lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key);
"
"lookupFM4 EmptyFM key = Nothing;
lookupFM4 xxy xxz = lookupFM3 xxy xxz;
"

----------------------------------------

(10)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord b => FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
addToFM fm key elt = addToFM_C addToFM0 fm key elt;

addToFM0 old new = new;

addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
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;

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;

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);
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;

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;
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);

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);

addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap a b  ->  (a,b);
findMax (Branch key elt vxy vxz EmptyFM) = (key,elt);
findMax (Branch key elt vyu vyv fm_r) = findMax fm_r;

findMin :: FiniteMap a b  ->  (a,b);
findMin (Branch key elt wvw EmptyFM wvx) = (key,elt);
findMin (Branch key elt wvy fm_l wvz) = findMin fm_l;

fmToList :: FiniteMap b a  ->  [(b,a)];
fmToList fm = foldFM fmToList0 [] fm;

fmToList0 key elt rest = (key,elt) : rest;

foldFM :: (a  ->  c  ->  b  ->  b)  ->  b  ->  FiniteMap a c  ->  b;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = lookupFM4 EmptyFM key;
lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find;

lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt;

lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise;

lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key);

lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key);

lookupFM4 EmptyFM key = Nothing;
lookupFM4 xxy xxz = lookupFM3 xxy xxz;

mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;

mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 
double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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);
double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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);
mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr);
mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R;
mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise;
mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr);
mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R;
mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise;
mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
size_l = sizeFM fm_L;
size_r = sizeFM fm_R;
 };

mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBranch which key elt fm_l fm_r = let { 
result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result where { 
balance_ok = True;
left_ok = left_ok0 fm_l key fm_l;
left_ok0 fm_l key EmptyFM = True;
left_ok0 fm_l key (Branch left_key vww vwx vwy vwz) = let { 
biggest_left_key = fst (findMax fm_l);
} in biggest_left_key < key;
left_size = sizeFM fm_l;
right_ok = right_ok0 fm_r key fm_r;
right_ok0 fm_r key EmptyFM = True;
right_ok0 fm_r key (Branch right_key vxu vxv vxw vxx) = let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);

mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_l < size_r) where { 
mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);
mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz));
mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise;
mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz;
mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_r < size_l);
size_l = sizeFM (Branch vuv vuw vux vuy vuz);
size_r = sizeFM (Branch vvv vvw vvx vvy vvz);
 };

mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy;

mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx;

plusFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 
gts = splitGT fm1 split_key;
lts = splitLT fm1 split_key;
new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key);
new_elt0 elt2 combiner Nothing = elt2;
new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap a b  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch wux wuy size wuz wvu) = size;

splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key;

splitGT0 key elt vwu fm_l fm_r split_key True = fm_r;

splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise;

splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key;
splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key);

splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key);

splitGT4 EmptyFM split_key = emptyFM;
splitGT4 xwu xwv = splitGT3 xwu xwv;

splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key;

splitLT0 key elt vwv fm_l fm_r split_key True = fm_l;

splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise;

splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key;
splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key);

splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key);

splitLT4 EmptyFM split_key = emptyFM;
splitLT4 xwy xwz = splitLT3 xwy xwz;

unitFM :: a  ->  b  ->  FiniteMap a b;
unitFM key elt = Branch key elt 1 emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(11) LetRed (EQUIVALENT)
Let/Where Reductions:
The bindings of the following Let/Where expression
"gcd' (abs x) (abs y) where {
gcd' x wwu = gcd'2 x wwu;
gcd' x y = gcd'0 x y;
;
gcd'0 x y = gcd' y (x `rem` y);
;
gcd'1 True x wwu = x;
gcd'1 wwv www wwx = gcd'0 www wwx;
;
gcd'2 x wwu = gcd'1 (wwu == 0) x wwu;
gcd'2 wwy wwz = gcd'0 wwy wwz;
} 
"
are unpacked to the following functions on top level
"gcd0Gcd'1 True x wwu = x;
gcd0Gcd'1 wwv www wwx = gcd0Gcd'0 www wwx;
"
"gcd0Gcd'2 x wwu = gcd0Gcd'1 (wwu == 0) x wwu;
gcd0Gcd'2 wwy wwz = gcd0Gcd'0 wwy wwz;
"
"gcd0Gcd'0 x y = gcd0Gcd' y (x `rem` y);
"
"gcd0Gcd' x wwu = gcd0Gcd'2 x wwu;
gcd0Gcd' x y = gcd0Gcd'0 x y;
"
The bindings of the following Let/Where expression
"reduce1 x y (y == 0) where {
d  = gcd x y;
;
reduce0 x y True = x `quot` d :% (y `quot` d);
;
reduce1 x y True = error [];
reduce1 x y False = reduce0 x y otherwise;
} 
"
are unpacked to the following functions on top level
"reduce2D xyu xyv = gcd xyu xyv;
"
"reduce2Reduce0 xyu xyv x y True = x `quot` reduce2D xyu xyv :% (y `quot` reduce2D xyu xyv);
"
"reduce2Reduce1 xyu xyv x y True = error [];
reduce2Reduce1 xyu xyv x y False = reduce2Reduce0 xyu xyv x y otherwise;
"
The bindings of the following Let/Where expression
"mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where {
double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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);
;
double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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);
;
mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr);
;
mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R;
;
mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise;
;
mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
;
mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr);
;
mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R;
;
mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise;
;
mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
;
mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
;
mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L;
mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise;
;
mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R;
mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r);
;
mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l);
;
single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
;
single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
;
size_l  = sizeFM fm_L;
;
size_r  = sizeFM fm_R;
} 
"
are unpacked to the following functions on top level
"mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr);
"
"mkBalBranch6Single_R xyw xyx xyy xyz (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 xyw xyx fm_lr fm_r);
"
"mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
"
"mkBalBranch6Size_l xyw xyx xyy xyz = sizeFM xyy;
"
"mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
"
"mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Double_L xyw xyx xyy xyz fm_L fm_R;
"
"mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R fm_R;
mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_l xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_r xyw xyx xyy xyz);
"
"mkBalBranch6Double_L xyw xyx xyy xyz fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 xyw xyx fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
"
"mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_r xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_l xyw xyx xyy xyz);
"
"mkBalBranch6Single_L xyw xyx xyy xyz fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 xyw xyx fm_l fm_rl) fm_rr;
"
"mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Single_R xyw xyx xyy xyz fm_L fm_R;
mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise;
"
"mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr);
"
"mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Double_R xyw xyx xyy xyz fm_L fm_R;
"
"mkBalBranch6Double_R xyw xyx xyy xyz (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 xyw xyx fm_lrr fm_r);
"
"mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R fm_L;
mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R otherwise;
"
"mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
"
"mkBalBranch6Size_r xyw xyx xyy xyz = sizeFM xyz;
"
"mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Single_L xyw xyx xyy xyz fm_L fm_R;
mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise;
"
The bindings of the following Let/Where expression
"let {
result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result where {
balance_ok  = True;
;
left_ok  = left_ok0 fm_l key fm_l;
;
left_ok0 fm_l key EmptyFM = True;
left_ok0 fm_l key (Branch left_key vww vwx vwy vwz) = let {
biggest_left_key  = fst (findMax fm_l);
} in biggest_left_key < key;
;
left_size  = sizeFM fm_l;
;
right_ok  = right_ok0 fm_r key fm_r;
;
right_ok0 fm_r key EmptyFM = True;
right_ok0 fm_r key (Branch right_key vxu vxv vxw vxx) = let {
smallest_right_key  = fst (findMin fm_r);
} in key < smallest_right_key;
;
right_size  = sizeFM fm_r;
;
unbox x = x;
} 
"
are unpacked to the following functions on top level
"mkBranchLeft_size xzu xzv xzw = sizeFM xzu;
"
"mkBranchRight_size xzu xzv xzw = sizeFM xzv;
"
"mkBranchLeft_ok xzu xzv xzw = mkBranchLeft_ok0 xzu xzv xzw xzu xzw xzu;
"
"mkBranchUnbox xzu xzv xzw x = x;
"
"mkBranchLeft_ok0 xzu xzv xzw fm_l key EmptyFM = True;
mkBranchLeft_ok0 xzu xzv xzw fm_l key (Branch left_key vww vwx vwy vwz) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
"
"mkBranchBalance_ok xzu xzv xzw = True;
"
"mkBranchRight_ok xzu xzv xzw = mkBranchRight_ok0 xzu xzv xzw xzv xzw xzv;
"
"mkBranchRight_ok0 xzu xzv xzw fm_r key EmptyFM = True;
mkBranchRight_ok0 xzu xzv xzw fm_r key (Branch right_key vxu vxv vxw vxx) = key < mkBranchRight_ok0Smallest_right_key fm_r;
"
The bindings of the following Let/Where expression
"let {
result  = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r;
} in result"
are unpacked to the following functions on top level
"mkBranchResult xzx xzy xzz yuu = Branch xzx xzy (mkBranchUnbox xzz yuu xzx (1 + mkBranchLeft_size xzz yuu xzx + mkBranchRight_size xzz yuu xzx)) xzz yuu;
"
The bindings of the following Let/Where expression
"mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where {
gts  = splitGT fm1 split_key;
;
lts  = splitLT fm1 split_key;
;
new_elt  = new_elt0 elt2 combiner (lookupFM fm1 split_key);
;
new_elt0 elt2 combiner Nothing = elt2;
new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2;
} 
"
are unpacked to the following functions on top level
"plusFM_CLts yuv yuw yux yuy = splitLT yuv yuw;
"
"plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner Nothing = elt2;
plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner (Just elt1) = combiner elt1 elt2;
"
"plusFM_CGts yuv yuw yux yuy = splitGT yuv yuw;
"
"plusFM_CNew_elt yuv yuw yux yuy = plusFM_CNew_elt0 yuv yuw yux yuy yux yuy (lookupFM yuv yuw);
"
The bindings of the following Let/Where expression
"mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_l < size_r) where {
mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);
;
mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz));
mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise;
;
mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz;
mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_r < size_l);
;
size_l  = sizeFM (Branch vuv vuw vux vuy vuz);
;
size_r  = sizeFM (Branch vvv vvw vvx vvy vvz);
} 
"
are unpacked to the following functions on top level
"mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yuz yvu yvv yvw yvx);
"
"mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz));
mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise;
"
"mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yvy yvz ywu ywv yww);
"
"mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);
"
"mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz;
mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww < mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww);
"
The bindings of the following Let/Where expression
"let {
biggest_left_key  = fst (findMax fm_l);
} in biggest_left_key < key"
are unpacked to the following functions on top level
"mkBranchLeft_ok0Biggest_left_key ywx = fst (findMax ywx);
"
The bindings of the following Let/Where expression
"let {
smallest_right_key  = fst (findMin fm_r);
} in key < smallest_right_key"
are unpacked to the following functions on top level
"mkBranchRight_ok0Smallest_right_key ywy = fst (findMin ywy);
"

----------------------------------------

(12)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap b a = EmptyFM  | Branch b a Int (FiniteMap b a) (FiniteMap b a) ;

instance (Eq a, Eq b) => Eq FiniteMap a b where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM fm key elt = addToFM_C addToFM0 fm key elt;

addToFM0 old new = new;

addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
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;

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;

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);
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;

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;
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);

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);

addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap a b  ->  (a,b);
findMax (Branch key elt vxy vxz EmptyFM) = (key,elt);
findMax (Branch key elt vyu vyv fm_r) = findMax fm_r;

findMin :: FiniteMap a b  ->  (a,b);
findMin (Branch key elt wvw EmptyFM wvx) = (key,elt);
findMin (Branch key elt wvy fm_l wvz) = findMin fm_l;

fmToList :: FiniteMap a b  ->  [(a,b)];
fmToList fm = foldFM fmToList0 [] fm;

fmToList0 key elt rest = (key,elt) : rest;

foldFM :: (c  ->  b  ->  a  ->  a)  ->  a  ->  FiniteMap c b  ->  a;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = lookupFM4 EmptyFM key;
lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find;

lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt;

lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise;

lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key);

lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key);

lookupFM4 EmptyFM key = Nothing;
lookupFM4 xxy xxz = lookupFM3 xxy xxz;

mkBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;

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);

mkBalBranch6Double_L xyw xyx xyy xyz fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 xyw xyx fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);

mkBalBranch6Double_R xyw xyx xyy xyz (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 xyw xyx fm_lrr fm_r);

mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr);

mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Double_L xyw xyx xyy xyz fm_L fm_R;

mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Single_L xyw xyx xyy xyz fm_L fm_R;
mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise;

mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);

mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr);

mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Double_R xyw xyx xyy xyz fm_L fm_R;

mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Single_R xyw xyx xyy xyz fm_L fm_R;
mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise;

mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);

mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;

mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R fm_L;
mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R otherwise;

mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R fm_R;
mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_l xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_r xyw xyx xyy xyz);

mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_r xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_l xyw xyx xyy xyz);

mkBalBranch6Single_L xyw xyx xyy xyz fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 xyw xyx fm_l fm_rl) fm_rr;

mkBalBranch6Single_R xyw xyx xyy xyz (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 xyw xyx fm_lr fm_r);

mkBalBranch6Size_l xyw xyx xyy xyz = sizeFM xyy;

mkBalBranch6Size_r xyw xyx xyy xyz = sizeFM xyz;

mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;

mkBranchBalance_ok xzu xzv xzw = True;

mkBranchLeft_ok xzu xzv xzw = mkBranchLeft_ok0 xzu xzv xzw xzu xzw xzu;

mkBranchLeft_ok0 xzu xzv xzw fm_l key EmptyFM = True;
mkBranchLeft_ok0 xzu xzv xzw fm_l key (Branch left_key vww vwx vwy vwz) = mkBranchLeft_ok0Biggest_left_key fm_l < key;

mkBranchLeft_ok0Biggest_left_key ywx = fst (findMax ywx);

mkBranchLeft_size xzu xzv xzw = sizeFM xzu;

mkBranchResult xzx xzy xzz yuu = Branch xzx xzy (mkBranchUnbox xzz yuu xzx (1 + mkBranchLeft_size xzz yuu xzx + mkBranchRight_size xzz yuu xzx)) xzz yuu;

mkBranchRight_ok xzu xzv xzw = mkBranchRight_ok0 xzu xzv xzw xzv xzw xzv;

mkBranchRight_ok0 xzu xzv xzw fm_r key EmptyFM = True;
mkBranchRight_ok0 xzu xzv xzw fm_r key (Branch right_key vxu vxv vxw vxx) = key < mkBranchRight_ok0Smallest_right_key fm_r;

mkBranchRight_ok0Smallest_right_key ywy = fst (findMin ywy);

mkBranchRight_size xzu xzv xzw = sizeFM xzv;

mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
mkBranchUnbox xzu xzv xzw x = x;

mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);

mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3MkVBalBranch2 vvv vvw vvx vvy vvz vuv vuw vux vuy vuz key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_l vvv vvw vvx vvy vvz vuv vuw vux vuy vuz < mkVBalBranch3Size_r vvv vvw vvx vvy vvz vuv vuw vux vuy vuz);

mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);

mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz));
mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise;

mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz;
mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww < mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww);

mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yvy yvz ywu ywv yww);

mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yuz yvu yvv yvw yvx);

mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy;

mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx;

plusFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key (plusFM_CNew_elt fm1 split_key elt2 combiner) (plusFM_C combiner (plusFM_CLts fm1 split_key elt2 combiner) left) (plusFM_C combiner (plusFM_CGts fm1 split_key elt2 combiner) right);

plusFM_CGts yuv yuw yux yuy = splitGT yuv yuw;

plusFM_CLts yuv yuw yux yuy = splitLT yuv yuw;

plusFM_CNew_elt yuv yuw yux yuy = plusFM_CNew_elt0 yuv yuw yux yuy yux yuy (lookupFM yuv yuw);

plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner Nothing = elt2;
plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner (Just elt1) = combiner elt1 elt2;

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap b a  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch wux wuy size wuz wvu) = size;

splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key;

splitGT0 key elt vwu fm_l fm_r split_key True = fm_r;

splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise;

splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key;
splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key);

splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key);

splitGT4 EmptyFM split_key = emptyFM;
splitGT4 xwu xwv = splitGT3 xwu xwv;

splitLT :: Ord a => FiniteMap a b  ->  a  ->  FiniteMap a b;
splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key;

splitLT0 key elt vwv fm_l fm_r split_key True = fm_l;

splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise;

splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key;
splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key);

splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key);

splitLT4 EmptyFM split_key = emptyFM;
splitLT4 xwy xwz = splitLT3 xwy xwz;

unitFM :: a  ->  b  ->  FiniteMap a b;
unitFM key elt = Branch key elt 1 emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}

----------------------------------------

(13) NumRed (SOUND)
Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero.
----------------------------------------

(14)
Obligation:
mainModule Main 
module FiniteMap where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
data FiniteMap a b = EmptyFM  | Branch a b Int (FiniteMap a b) (FiniteMap a b) ;

instance (Eq a, Eq b) => Eq FiniteMap b a where { 
(==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2;
}
addToFM :: Ord a => FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM fm key elt = addToFM_C addToFM0 fm key elt;

addToFM0 old new = new;

addToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  a  ->  b  ->  FiniteMap a b;
addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt;
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;

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;

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);
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;

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;
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);

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);

addToFM_C4 combiner EmptyFM key elt = unitFM key elt;
addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx;

emptyFM :: FiniteMap b a;
emptyFM = EmptyFM;

findMax :: FiniteMap b a  ->  (b,a);
findMax (Branch key elt vxy vxz EmptyFM) = (key,elt);
findMax (Branch key elt vyu vyv fm_r) = findMax fm_r;

findMin :: FiniteMap b a  ->  (b,a);
findMin (Branch key elt wvw EmptyFM wvx) = (key,elt);
findMin (Branch key elt wvy fm_l wvz) = findMin fm_l;

fmToList :: FiniteMap b a  ->  [(b,a)];
fmToList fm = foldFM fmToList0 [] fm;

fmToList0 key elt rest = (key,elt) : rest;

foldFM :: (c  ->  a  ->  b  ->  b)  ->  b  ->  FiniteMap c a  ->  b;
foldFM k z EmptyFM = z;
foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l;

lookupFM :: Ord b => FiniteMap b a  ->  b  ->  Maybe a;
lookupFM EmptyFM key = lookupFM4 EmptyFM key;
lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find;

lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt;

lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find;
lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise;

lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find;
lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key);

lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key);

lookupFM4 EmptyFM key = Nothing;
lookupFM4 xxy xxz = lookupFM3 xxy xxz;

mkBalBranch :: Ord b => b  ->  a  ->  FiniteMap b a  ->  FiniteMap b a  ->  FiniteMap b a;
mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R;

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)));

mkBalBranch6Double_L xyw xyx xyy xyz fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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))))))) xyw xyx fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr);

mkBalBranch6Double_R xyw xyx xyy xyz (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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))))))))))))) xyw xyx fm_lrr fm_r);

mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr);

mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Double_L xyw xyx xyy xyz fm_L fm_R;

mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Single_L xyw xyx xyy xyz fm_L fm_R;
mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise;

mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);

mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr);

mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Double_R xyw xyx xyy xyz fm_L fm_R;

mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Single_R xyw xyx xyy xyz fm_L fm_R;
mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise;

mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);

mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;

mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R fm_L;
mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R otherwise;

mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R fm_R;
mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_l xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_r xyw xyx xyy xyz);

mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_r xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_l xyw xyx xyy xyz);

mkBalBranch6Single_L xyw xyx xyy xyz fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) xyw xyx fm_l fm_rl) fm_rr;

mkBalBranch6Single_R xyw xyx xyy xyz (Branch key_l elt_l vyw 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)))))))))) xyw xyx fm_lr fm_r);

mkBalBranch6Size_l xyw xyx xyy xyz = sizeFM xyy;

mkBalBranch6Size_r xyw xyx xyy xyz = sizeFM xyz;

mkBranch :: Ord a => Int  ->  a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r;

mkBranchBalance_ok xzu xzv xzw = True;

mkBranchLeft_ok xzu xzv xzw = mkBranchLeft_ok0 xzu xzv xzw xzu xzw xzu;

mkBranchLeft_ok0 xzu xzv xzw fm_l key EmptyFM = True;
mkBranchLeft_ok0 xzu xzv xzw fm_l key (Branch left_key vww vwx vwy vwz) = mkBranchLeft_ok0Biggest_left_key fm_l < key;

mkBranchLeft_ok0Biggest_left_key ywx = fst (findMax ywx);

mkBranchLeft_size xzu xzv xzw = sizeFM xzu;

mkBranchResult xzx xzy xzz yuu = Branch xzx xzy (mkBranchUnbox xzz yuu xzx (Pos (Succ Zero) + mkBranchLeft_size xzz yuu xzx + mkBranchRight_size xzz yuu xzx)) xzz yuu;

mkBranchRight_ok xzu xzv xzw = mkBranchRight_ok0 xzu xzv xzw xzv xzw xzv;

mkBranchRight_ok0 xzu xzv xzw fm_r key EmptyFM = True;
mkBranchRight_ok0 xzu xzv xzw fm_r key (Branch right_key vxu vxv vxw vxx) = key < mkBranchRight_ok0Smallest_right_key fm_r;

mkBranchRight_ok0Smallest_right_key ywy = fst (findMin ywy);

mkBranchRight_size xzu xzv xzw = sizeFM xzv;

mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  (FiniteMap a b) ( ->  a (Int  ->  Int)));
mkBranchUnbox xzu xzv xzw x = x;

mkVBalBranch :: Ord a => a  ->  b  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r;
mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM;
mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);

mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3MkVBalBranch2 vvv vvw vvx vvy vvz vuv vuw vux vuy vuz key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_l vvv vvw vvx vvy vvz vuv vuw vux vuy vuz < mkVBalBranch3Size_r vvv vvw vvx vvy vvz vuv vuw vux vuy vuz);

mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))) key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz);

mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz));
mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise;

mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz;
mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww < mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww);

mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yvy yvz ywu ywv yww);

mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yuz yvu yvv yvw yvx);

mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt;
mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy;

mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt;
mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx;

plusFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  FiniteMap a b  ->  FiniteMap a b;
plusFM_C combiner EmptyFM fm2 = fm2;
plusFM_C combiner fm1 EmptyFM = fm1;
plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key (plusFM_CNew_elt fm1 split_key elt2 combiner) (plusFM_C combiner (plusFM_CLts fm1 split_key elt2 combiner) left) (plusFM_C combiner (plusFM_CGts fm1 split_key elt2 combiner) right);

plusFM_CGts yuv yuw yux yuy = splitGT yuv yuw;

plusFM_CLts yuv yuw yux yuy = splitLT yuv yuw;

plusFM_CNew_elt yuv yuw yux yuy = plusFM_CNew_elt0 yuv yuw yux yuy yux yuy (lookupFM yuv yuw);

plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner Nothing = elt2;
plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner (Just elt1) = combiner elt1 elt2;

sIZE_RATIO :: Int;
sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero)))));

sizeFM :: FiniteMap b a  ->  Int;
sizeFM EmptyFM = Pos Zero;
sizeFM (Branch wux wuy size wuz wvu) = size;

splitGT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitGT EmptyFM split_key = splitGT4 EmptyFM split_key;
splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key;

splitGT0 key elt vwu fm_l fm_r split_key True = fm_r;

splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r;
splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise;

splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key;
splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key);

splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key);

splitGT4 EmptyFM split_key = emptyFM;
splitGT4 xwu xwv = splitGT3 xwu xwv;

splitLT :: Ord b => FiniteMap b a  ->  b  ->  FiniteMap b a;
splitLT EmptyFM split_key = splitLT4 EmptyFM split_key;
splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key;

splitLT0 key elt vwv fm_l fm_r split_key True = fm_l;

splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key);
splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise;

splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key;
splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key);

splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key);

splitLT4 EmptyFM split_key = emptyFM;
splitLT4 xwy xwz = splitLT3 xwy xwz;

unitFM :: b  ->  a  ->  FiniteMap b a;
unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM;

}
module Maybe where {
import qualified FiniteMap;
import qualified Main;
import qualified Prelude;
}
module Main where {
import qualified FiniteMap;
import qualified Maybe;
import qualified Prelude;
}