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