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