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


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


YES
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 be proven:

(0) HASKELL
(1) LR [EQUIVALENT, 0 ms]
(2) HASKELL
(3) CR [EQUIVALENT, 0 ms]
(4) HASKELL
(5) BR [EQUIVALENT, 0 ms]
(6) HASKELL
(7) COR [EQUIVALENT, 23 ms]
(8) HASKELL
(9) LetRed [EQUIVALENT, 0 ms]
(10) HASKELL
(11) NumRed [SOUND, 0 ms]
(12) HASKELL
(13) Narrow [SOUND, 0 ms]
(14) QDP
(15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
(16) YES


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

(0)
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 { 
}
addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM fm key_elt_pairs = addListToFM_C (\old new ->new) fm key_elt_pairs;

addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
add fmap (key,elt) = addToFM_C combiner fmap key elt;
 };

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 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 a b  ->  (a,b);
findMin (Branch key elt _ EmptyFM _) = (key,elt);
findMin (Branch key elt _ fm_l _) = findMin fm_l;

listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
listToFM = addListToFM emptyFM;

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

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

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

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
"addListToFM0 old new = new;
"

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

(2)
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 { 
}
addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;

addListToFM0 old new = new;

addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
add fmap (key,elt) = addToFM_C combiner fmap key elt;
 };

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

listToFM :: Ord a => [(a,b)]  ->  FiniteMap a b;
listToFM = addListToFM emptyFM;

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 = 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;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

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

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

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

(3) CR (EQUIVALENT)
Case Reductions:
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 { 
}
addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;

addListToFM0 old new = new;

addListToFM_C :: Ord a => (b  ->  b  ->  b)  ->  FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
add fmap (key,elt) = addToFM_C combiner fmap key elt;
 };

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

listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
listToFM = addListToFM emptyFM;

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

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

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

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

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

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

(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 b a where { 
}
addListToFM :: Ord b => FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;

addListToFM0 old new = new;

addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
add fmap (key,elt) = addToFM_C combiner fmap key elt;
 };

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 b a  ->  (b,a);
findMax (Branch key elt xv xw EmptyFM) = (key,elt);
findMax (Branch key elt xx xy fm_r) = findMax fm_r;

findMin :: FiniteMap a b  ->  (a,b);
findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;

listToFM :: Ord a => [(a,b)]  ->  FiniteMap a b;
listToFM = addListToFM emptyFM;

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 yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)  | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R
 | otherwise = double_L fm_L fm_R;
mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)  | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R
 | otherwise = double_R fm_L fm_R;
single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
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 vz wu wv ww) = 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 wx wy wz xu) = let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap a b  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch zz vuu size vuv vuw) = size;

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

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

(7) COR (EQUIVALENT)
Cond Reductions:
The following Function with conditions
"undefined |Falseundefined;
"
is transformed to
"undefined  = undefined1;
"
"undefined0 True = undefined;
"
"undefined1  = undefined0 False;
"
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_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_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_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 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;
"
The following Function with conditions
"mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
"
is transformed to
"mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
"
"mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
"
"mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
"
"mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
"
The following Function with conditions
"mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
"
is transformed to
"mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
"
"mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
"
"mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
"
"mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
"
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 yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
;
double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
;
mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R;
;
mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R;
;
single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr;
;
single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r);
;
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 yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
;
double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
;
mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
;
mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
;
mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
;
mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
;
mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
;
mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
;
mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
;
mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
;
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 zy 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 xz 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;
} 
;
"

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

(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 { 
}
addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;

addListToFM0 old new = new;

addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 
add fmap (key,elt) = addToFM_C combiner fmap key elt;
 };

addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
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 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap b a  ->  (b,a);
findMax (Branch key elt xv xw EmptyFM) = (key,elt);
findMax (Branch key elt xx xy fm_r) = findMax fm_r;

findMin :: FiniteMap a b  ->  (a,b);
findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;

listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
listToFM = addListToFM emptyFM;

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 yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
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 zy 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 xz 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 vz wu wv ww) = 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 wx wy wz xu) = let { 
smallest_right_key = fst (findMin fm_r);
} in key < smallest_right_key;
right_size = sizeFM fm_r;
unbox :: Int  ->  Int;
unbox x = x;
 };

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap b a  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch zz vuu size vuv vuw) = size;

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) LetRed (EQUIVALENT)
Let/Where Reductions:
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 yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
;
double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r);
;
mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
;
mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R;
;
mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R;
mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
;
mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
;
mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
;
mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R;
;
mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R;
mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
;
mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
;
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 zy 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 xz 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
"mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;
"
"mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu);
"
"mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;
"
"mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;
"
"mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwx;
"
"mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;
"
"mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr);
"
"mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vwy;
"
"mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vwz vxu fm_lrr fm_r);
"
"mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwz vxu fm_lr fm_r);
"
"mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr);
"
"mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu);
"
"mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vwz vxu fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);
"
"mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwz vxu fm_l fm_rl) fm_rr;
"
"mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);
"
"mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);
"
"mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise;
"
"mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise;
"
The bindings of the following Let/Where expression
"foldl add fm key_elt_pairs where {
add fmap (key,elt) = addToFM_C combiner fmap key elt;
} 
"
are unpacked to the following functions on top level
"addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;
"
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 vz wu wv ww) = 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 wx wy wz xu) = 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
"mkBranchBalance_ok vxw vxx vxy = True;
"
"mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key;
"
"mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r;
"
"mkBranchUnbox vxw vxx vxy x = x;
"
"mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxx vxw;
"
"mkBranchLeft_size vxw vxx vxy = sizeFM vxw;
"
"mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxy vxx vxy;
"
"mkBranchRight_size vxw vxx vxy = sizeFM vxy;
"
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 vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vxz vyw (1 + mkBranchLeft_size vyv vxz vyw + mkBranchRight_size vyv vxz vyw)) vyv vyw;
"
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 vyx = fst (findMax vyx);
"
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 vyy = fst (findMin vyy);
"

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

(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 { 
}
addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;

addListToFM0 old new = new;

addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs;

addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;

addToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  b  ->  a  ->  FiniteMap b a;
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 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap b a  ->  (b,a);
findMax (Branch key elt xv xw EmptyFM) = (key,elt);
findMax (Branch key elt xx xy fm_r) = findMax fm_r;

findMin :: FiniteMap b a  ->  (b,a);
findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;

listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
listToFM = addListToFM emptyFM;

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 fm_L fm_R key elt key elt fm_L fm_R (mkBalBranch6Size_l fm_L fm_R key elt + mkBalBranch6Size_r fm_L fm_R key elt < 2);

mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vwz vxu fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr);

mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vwz vxu fm_lrr fm_r);

mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr);

mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;

mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise;

mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr);

mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr);

mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;

mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise;

mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll);

mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R;

mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;

mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu);

mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R;
mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu);

mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwz vxu fm_l fm_rl) fm_rr;

mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwz vxu fm_lr fm_r);

mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwx;

mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vwy;

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 vxw vxx vxy = True;

mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxx vxw;

mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key;

mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);

mkBranchLeft_size vxw vxx vxy = sizeFM vxw;

mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vxz vyw (1 + mkBranchLeft_size vyv vxz vyw + mkBranchRight_size vyv vxz vyw)) vyv vyw;

mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxy vxx vxy;

mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r;

mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);

mkBranchRight_size vxw vxx vxy = sizeFM vxy;

mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
mkBranchUnbox vxw vxx vxy x = x;

sIZE_RATIO :: Int;
sIZE_RATIO = 5;

sizeFM :: FiniteMap b a  ->  Int;
sizeFM EmptyFM = 0;
sizeFM (Branch zz vuu size vuv vuw) = size;

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

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

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

(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 { 
}
addListToFM :: Ord a => FiniteMap a b  ->  [(a,b)]  ->  FiniteMap a b;
addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs;

addListToFM0 old new = new;

addListToFM_C :: Ord b => (a  ->  a  ->  a)  ->  FiniteMap b a  ->  [(b,a)]  ->  FiniteMap b a;
addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs;

addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt;

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 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu;

emptyFM :: FiniteMap a b;
emptyFM = EmptyFM;

findMax :: FiniteMap b a  ->  (b,a);
findMax (Branch key elt xv xw EmptyFM) = (key,elt);
findMax (Branch key elt xx xy fm_r) = findMax fm_r;

findMin :: FiniteMap a b  ->  (a,b);
findMin (Branch key elt vux EmptyFM vuy) = (key,elt);
findMin (Branch key elt vuz fm_l vvu) = findMin fm_l;

listToFM :: Ord b => [(b,a)]  ->  FiniteMap b a;
listToFM = addListToFM emptyFM;

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 fm_L fm_R key elt key elt fm_L fm_R (mkBalBranch6Size_l fm_L fm_R key elt + mkBalBranch6Size_r fm_L fm_R key elt < Pos (Succ (Succ Zero)));

mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ Zero)))))) key_rl elt_rl (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))) vwz vxu fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr);

mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))) key_lr elt_lr (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))) key_l elt_l fm_ll fm_lrl) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))))) vwz vxu fm_lrr fm_r);

mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr);

mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R;

mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R;
mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise;

mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr);

mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr);

mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R;

mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R;
mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise;

mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll);

mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R;

mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L;
mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise;

mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R;
mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu);

mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R;
mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu);

mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) vwz vxu fm_l fm_rl) fm_rr;

mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))) key_l elt_l fm_ll (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))) vwz vxu fm_lr fm_r);

mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwx;

mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vwy;

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 vxw vxx vxy = True;

mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxx vxw;

mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True;
mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key;

mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx);

mkBranchLeft_size vxw vxx vxy = sizeFM vxw;

mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vxz vyw (Pos (Succ Zero) + mkBranchLeft_size vyv vxz vyw + mkBranchRight_size vyv vxz vyw)) vyv vyw;

mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxy vxx vxy;

mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True;
mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r;

mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy);

mkBranchRight_size vxw vxx vxy = sizeFM vxy;

mkBranchUnbox :: Ord a =>  ->  (FiniteMap a b) ( ->  a ( ->  (FiniteMap a b) (Int  ->  Int)));
mkBranchUnbox vxw vxx vxy x = x;

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

sizeFM :: FiniteMap a b  ->  Int;
sizeFM EmptyFM = Pos Zero;
sizeFM (Branch zz vuu size vuv vuw) = size;

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

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

(13) Narrow (SOUND)
Haskell To QDPs

digraph dp_graph {
node [outthreshold=100, inthreshold=100];1[label="FiniteMap.listToFM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
3[label="FiniteMap.listToFM vyz3",fontsize=16,color="black",shape="triangle"];3 -> 4[label="",style="solid", color="black", weight=3];
4[label="FiniteMap.addListToFM FiniteMap.emptyFM vyz3",fontsize=16,color="black",shape="box"];4 -> 5[label="",style="solid", color="black", weight=3];
5[label="FiniteMap.addListToFM_C FiniteMap.addListToFM0 FiniteMap.emptyFM vyz3",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3];
6 -> 20[label="",style="dashed", color="red", weight=0];
6[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) FiniteMap.emptyFM vyz3",fontsize=16,color="magenta"];6 -> 21[label="",style="dashed", color="magenta", weight=3];
6 -> 22[label="",style="dashed", color="magenta", weight=3];
21[label="FiniteMap.emptyFM",fontsize=16,color="black",shape="triangle"];21 -> 27[label="",style="solid", color="black", weight=3];
22[label="vyz3",fontsize=16,color="green",shape="box"];20[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz6 vyz311",fontsize=16,color="burlywood",shape="triangle"];59[label="vyz311/vyz3110 : vyz3111",fontsize=10,color="white",style="solid",shape="box"];20 -> 59[label="",style="solid", color="burlywood", weight=9];
59 -> 28[label="",style="solid", color="burlywood", weight=3];
60[label="vyz311/[]",fontsize=10,color="white",style="solid",shape="box"];20 -> 60[label="",style="solid", color="burlywood", weight=9];
60 -> 29[label="",style="solid", color="burlywood", weight=3];
27[label="FiniteMap.EmptyFM",fontsize=16,color="green",shape="box"];28[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz6 (vyz3110 : vyz3111)",fontsize=16,color="black",shape="box"];28 -> 30[label="",style="solid", color="black", weight=3];
29[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz6 []",fontsize=16,color="black",shape="box"];29 -> 31[label="",style="solid", color="black", weight=3];
30 -> 20[label="",style="dashed", color="red", weight=0];
30[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz6 vyz3110) vyz3111",fontsize=16,color="magenta"];30 -> 32[label="",style="dashed", color="magenta", weight=3];
30 -> 33[label="",style="dashed", color="magenta", weight=3];
31[label="vyz6",fontsize=16,color="green",shape="box"];32[label="FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz6 vyz3110",fontsize=16,color="burlywood",shape="box"];61[label="vyz3110/(vyz31100,vyz31101)",fontsize=10,color="white",style="solid",shape="box"];32 -> 61[label="",style="solid", color="burlywood", weight=9];
61 -> 34[label="",style="solid", color="burlywood", weight=3];
33[label="vyz3111",fontsize=16,color="green",shape="box"];34[label="FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz6 (vyz31100,vyz31101)",fontsize=16,color="black",shape="box"];34 -> 35[label="",style="solid", color="black", weight=3];
35[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 vyz6 vyz31100 vyz31101",fontsize=16,color="burlywood",shape="box"];62[label="vyz6/FiniteMap.EmptyFM",fontsize=10,color="white",style="solid",shape="box"];35 -> 62[label="",style="solid", color="burlywood", weight=9];
62 -> 36[label="",style="solid", color="burlywood", weight=3];
63[label="vyz6/FiniteMap.Branch vyz60 vyz61 vyz62 vyz63 vyz64",fontsize=10,color="white",style="solid",shape="box"];35 -> 63[label="",style="solid", color="burlywood", weight=9];
63 -> 37[label="",style="solid", color="burlywood", weight=3];
36[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 FiniteMap.EmptyFM vyz31100 vyz31101",fontsize=16,color="black",shape="box"];36 -> 38[label="",style="solid", color="black", weight=3];
37[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 (FiniteMap.Branch vyz60 vyz61 vyz62 vyz63 vyz64) vyz31100 vyz31101",fontsize=16,color="black",shape="box"];37 -> 39[label="",style="solid", color="black", weight=3];
38[label="FiniteMap.addToFM_C4 FiniteMap.addListToFM0 FiniteMap.EmptyFM vyz31100 vyz31101",fontsize=16,color="black",shape="box"];38 -> 40[label="",style="solid", color="black", weight=3];
39[label="FiniteMap.addToFM_C3 FiniteMap.addListToFM0 (FiniteMap.Branch vyz60 vyz61 vyz62 vyz63 vyz64) vyz31100 vyz31101",fontsize=16,color="black",shape="box"];39 -> 41[label="",style="solid", color="black", weight=3];
40[label="FiniteMap.unitFM vyz31100 vyz31101",fontsize=16,color="black",shape="box"];40 -> 42[label="",style="solid", color="black", weight=3];
41[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz60 vyz61 vyz62 vyz63 vyz64 vyz31100 vyz31101 (vyz31100 < vyz60)",fontsize=16,color="black",shape="box"];41 -> 43[label="",style="solid", color="black", weight=3];
42[label="FiniteMap.Branch vyz31100 vyz31101 (Pos (Succ Zero)) FiniteMap.emptyFM FiniteMap.emptyFM",fontsize=16,color="green",shape="box"];42 -> 44[label="",style="dashed", color="green", weight=3];
42 -> 45[label="",style="dashed", color="green", weight=3];
43[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz60 vyz61 vyz62 vyz63 vyz64 vyz31100 vyz31101 (compare vyz31100 vyz60 == LT)",fontsize=16,color="burlywood",shape="box"];64[label="vyz31100/()",fontsize=10,color="white",style="solid",shape="box"];43 -> 64[label="",style="solid", color="burlywood", weight=9];
64 -> 46[label="",style="solid", color="burlywood", weight=3];
44 -> 21[label="",style="dashed", color="red", weight=0];
44[label="FiniteMap.emptyFM",fontsize=16,color="magenta"];45 -> 21[label="",style="dashed", color="red", weight=0];
45[label="FiniteMap.emptyFM",fontsize=16,color="magenta"];46[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz60 vyz61 vyz62 vyz63 vyz64 () vyz31101 (compare () vyz60 == LT)",fontsize=16,color="burlywood",shape="box"];65[label="vyz60/()",fontsize=10,color="white",style="solid",shape="box"];46 -> 65[label="",style="solid", color="burlywood", weight=9];
65 -> 47[label="",style="solid", color="burlywood", weight=3];
47[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (compare () () == LT)",fontsize=16,color="black",shape="box"];47 -> 48[label="",style="solid", color="black", weight=3];
48[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (EQ == LT)",fontsize=16,color="black",shape="box"];48 -> 49[label="",style="solid", color="black", weight=3];
49[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 False",fontsize=16,color="black",shape="box"];49 -> 50[label="",style="solid", color="black", weight=3];
50[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (() > ())",fontsize=16,color="black",shape="box"];50 -> 51[label="",style="solid", color="black", weight=3];
51[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (compare () () == GT)",fontsize=16,color="black",shape="box"];51 -> 52[label="",style="solid", color="black", weight=3];
52[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (EQ == GT)",fontsize=16,color="black",shape="box"];52 -> 53[label="",style="solid", color="black", weight=3];
53[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 False",fontsize=16,color="black",shape="box"];53 -> 54[label="",style="solid", color="black", weight=3];
54[label="FiniteMap.addToFM_C0 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 otherwise",fontsize=16,color="black",shape="box"];54 -> 55[label="",style="solid", color="black", weight=3];
55[label="FiniteMap.addToFM_C0 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 True",fontsize=16,color="black",shape="box"];55 -> 56[label="",style="solid", color="black", weight=3];
56[label="FiniteMap.Branch () (FiniteMap.addListToFM0 vyz61 vyz31101) vyz62 vyz63 vyz64",fontsize=16,color="green",shape="box"];56 -> 57[label="",style="dashed", color="green", weight=3];
57[label="FiniteMap.addListToFM0 vyz61 vyz31101",fontsize=16,color="black",shape="box"];57 -> 58[label="",style="solid", color="black", weight=3];
58[label="vyz31101",fontsize=16,color="green",shape="box"];}

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

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_foldl(vyz6, :(vyz3110, vyz3111), h) -> new_foldl(new_addListToFM_CAdd(vyz6, vyz3110, h), vyz3111, h)

The TRS R consists of the following rules:

   new_addListToFM_CAdd(Branch(@0, vyz61, vyz62, vyz63, vyz64), @2(@0, vyz31101), h) -> Branch(@0, vyz31101, vyz62, vyz63, vyz64)
   new_addListToFM_CAdd(EmptyFM, @2(vyz31100, vyz31101), h) -> Branch(vyz31100, vyz31101, Pos(Succ(Zero)), new_emptyFM(h), new_emptyFM(h))
   new_emptyFM(h) -> EmptyFM

The set Q consists of the following terms:

   new_addListToFM_CAdd(EmptyFM, @2(x0, x1), x2)
   new_emptyFM(x0)
   new_addListToFM_CAdd(Branch(@0, x0, x1, x2, x3), @2(@0, x4), x5)

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(15) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*new_foldl(vyz6, :(vyz3110, vyz3111), h) -> new_foldl(new_addListToFM_CAdd(vyz6, vyz3110, h), vyz3111, h)
The graph contains the following edges 2 > 2, 3 >= 3


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

(16)
YES