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