239.02/195.92 MAYBE 242.01/196.78 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 242.01/196.78 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 242.01/196.78 242.01/196.78 242.01/196.78 H-Termination with start terms of the given HASKELL could not be shown: 242.01/196.78 242.01/196.78 (0) HASKELL 242.01/196.78 (1) LR [EQUIVALENT, 0 ms] 242.01/196.78 (2) HASKELL 242.01/196.78 (3) CR [EQUIVALENT, 0 ms] 242.01/196.78 (4) HASKELL 242.01/196.78 (5) IFR [EQUIVALENT, 0 ms] 242.01/196.78 (6) HASKELL 242.01/196.78 (7) BR [EQUIVALENT, 0 ms] 242.01/196.78 (8) HASKELL 242.01/196.78 (9) COR [EQUIVALENT, 0 ms] 242.01/196.78 (10) HASKELL 242.01/196.78 (11) LetRed [EQUIVALENT, 45 ms] 242.01/196.78 (12) HASKELL 242.01/196.78 (13) NumRed [SOUND, 0 ms] 242.01/196.78 (14) HASKELL 242.01/196.78 242.01/196.78 242.01/196.78 ---------------------------------------- 242.01/196.78 242.01/196.78 (0) 242.01/196.78 Obligation: 242.01/196.78 mainModule Main 242.01/196.78 module FiniteMap where { 242.01/196.78 import qualified Main; 242.01/196.78 import qualified Maybe; 242.01/196.78 import qualified Prelude; 242.01/196.78 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 242.01/196.78 242.01/196.78 instance (Eq a, Eq b) => Eq FiniteMap b a where { 242.01/196.78 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 242.01/196.78 } 242.01/196.78 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 242.01/196.78 addToFM fm key elt = addToFM_C (\old new ->new) fm key elt; 242.01/196.78 242.01/196.78 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 242.01/196.78 addToFM_C combiner EmptyFM key elt = unitFM key elt; 242.01/196.78 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 242.01/196.78 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 242.01/196.78 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 242.01/196.78 242.01/196.78 deleteMax :: Ord a => FiniteMap a b -> FiniteMap a b; 242.01/196.78 deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l; 242.01/196.78 deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 242.01/196.78 242.01/196.78 deleteMin :: Ord b => FiniteMap b a -> FiniteMap b a; 242.01/196.78 deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r; 242.01/196.78 deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 242.01/196.78 242.01/196.78 emptyFM :: FiniteMap b a; 242.01/196.78 emptyFM = EmptyFM; 242.01/196.78 242.01/196.78 findMax :: FiniteMap b a -> (b,a); 242.01/196.78 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 242.01/196.78 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 242.01/196.78 242.01/196.78 findMin :: FiniteMap a b -> (a,b); 242.01/196.78 findMin (Branch key elt _ EmptyFM _) = (key,elt); 242.01/196.78 findMin (Branch key elt _ fm_l _) = findMin fm_l; 242.01/196.78 242.01/196.78 fmToList :: FiniteMap b a -> [(b,a)]; 242.01/196.78 fmToList fm = foldFM (\key elt rest ->(key,elt) : rest) [] fm; 242.01/196.78 242.01/196.78 foldFM :: (c -> b -> a -> a) -> a -> FiniteMap c b -> a; 242.01/196.78 foldFM k z EmptyFM = z; 242.01/196.78 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 242.01/196.78 242.01/196.78 glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 glueBal EmptyFM fm2 = fm2; 242.01/196.78 glueBal fm1 EmptyFM = fm1; 242.01/196.78 glueBal fm1 fm2 | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2) 242.01/196.78 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 242.01/196.78 mid_elt1 = (\(_,mid_elt1) ->mid_elt1) vv2; 242.01/196.78 mid_elt2 = (\(_,mid_elt2) ->mid_elt2) vv3; 242.01/196.78 mid_key1 = (\(mid_key1,_) ->mid_key1) vv2; 242.01/196.78 mid_key2 = (\(mid_key2,_) ->mid_key2) vv3; 242.01/196.78 vv2 = findMax fm1; 242.01/196.78 vv3 = findMin fm2; 242.01/196.78 }; 242.01/196.78 242.01/196.78 glueVBal :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.01/196.78 glueVBal EmptyFM fm2 = fm2; 242.01/196.78 glueVBal fm1 EmptyFM = fm1; 242.01/196.78 glueVBal fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (glueVBal fm_l fm_rl) fm_rr 242.01/196.78 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r) 242.01/196.78 | otherwise = glueBal fm_l fm_r where { 242.01/196.78 size_l = sizeFM fm_l; 242.01/196.78 size_r = sizeFM fm_r; 242.01/196.78 }; 242.01/196.78 242.01/196.78 intersectFM :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 intersectFM fm1 fm2 = intersectFM_C (\left right ->right) fm1 fm2; 242.01/196.78 242.01/196.78 intersectFM_C :: Ord a => (b -> c -> d) -> FiniteMap a b -> FiniteMap a c -> FiniteMap a d; 242.01/196.78 intersectFM_C combiner fm1 EmptyFM = emptyFM; 242.01/196.78 intersectFM_C combiner EmptyFM fm2 = emptyFM; 242.01/196.78 intersectFM_C combiner fm1 (Branch split_key elt2 _ left right) | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) 242.01/196.78 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 242.01/196.78 elt1 = (\(Just elt1) ->elt1) vv1; 242.01/196.78 gts = splitGT fm1 split_key; 242.01/196.78 lts = splitLT fm1 split_key; 242.01/196.78 maybe_elt1 = lookupFM fm1 split_key; 242.01/196.78 vv1 = maybe_elt1; 242.01/196.78 }; 242.01/196.78 242.01/196.78 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 242.01/196.78 lookupFM EmptyFM key = Nothing; 242.01/196.78 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 242.01/196.78 | key_to_find > key = lookupFM fm_r key_to_find 242.01/196.78 | otherwise = Just elt; 242.01/196.78 242.01/196.78 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.01/196.78 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 242.01/196.78 | size_r > sIZE_RATIO * size_l = case fm_R of { 242.01/196.78 Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R 242.01/196.78 | otherwise -> double_L fm_L fm_R; 242.01/196.78 } 242.01/196.78 | size_l > sIZE_RATIO * size_r = case fm_L of { 242.01/196.78 Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R 242.01/196.78 | otherwise -> double_R fm_L fm_R; 242.01/196.78 } 242.01/196.78 | otherwise = mkBranch 2 key elt fm_L fm_R where { 242.01/196.78 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); 242.01/196.78 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); 242.01/196.78 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; 242.01/196.78 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); 242.01/196.78 size_l = sizeFM fm_L; 242.01/196.78 size_r = sizeFM fm_R; 242.01/196.78 }; 242.01/196.78 242.01/196.78 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 mkBranch which key elt fm_l fm_r = let { 242.01/196.78 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 242.01/196.78 } in result where { 242.01/196.78 balance_ok = True; 242.01/196.78 left_ok = case fm_l of { 242.01/196.78 EmptyFM-> True; 242.01/196.78 Branch left_key _ _ _ _-> let { 242.01/196.78 biggest_left_key = fst (findMax fm_l); 242.01/196.78 } in biggest_left_key < key; 242.01/196.78 } ; 242.01/196.78 left_size = sizeFM fm_l; 242.01/196.78 right_ok = case fm_r of { 242.01/196.78 EmptyFM-> True; 242.01/196.78 Branch right_key _ _ _ _-> let { 242.01/196.78 smallest_right_key = fst (findMin fm_r); 242.01/196.78 } in key < smallest_right_key; 242.01/196.78 } ; 242.01/196.78 right_size = sizeFM fm_r; 242.01/196.78 unbox :: Int -> Int; 242.01/196.78 unbox x = x; 242.01/196.78 }; 242.01/196.78 242.01/196.78 mkVBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 242.01/196.78 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 242.01/196.78 mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr 242.01/196.78 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 242.01/196.78 | otherwise = mkBranch 13 key elt fm_l fm_r where { 242.01/196.78 size_l = sizeFM fm_l; 242.01/196.78 size_r = sizeFM fm_r; 242.01/196.78 }; 242.01/196.78 242.01/196.78 sIZE_RATIO :: Int; 242.01/196.78 sIZE_RATIO = 5; 242.01/196.78 242.01/196.78 sizeFM :: FiniteMap b a -> Int; 242.01/196.78 sizeFM EmptyFM = 0; 242.01/196.78 sizeFM (Branch _ _ size _ _) = size; 242.01/196.78 242.01/196.78 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 242.01/196.78 splitGT EmptyFM split_key = emptyFM; 242.01/196.78 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 242.01/196.78 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 242.01/196.78 | otherwise = fm_r; 242.01/196.78 242.01/196.78 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 242.01/196.78 splitLT EmptyFM split_key = emptyFM; 242.01/196.78 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 242.01/196.78 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 242.01/196.78 | otherwise = fm_l; 242.01/196.78 242.01/196.78 unitFM :: a -> b -> FiniteMap a b; 242.01/196.78 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 242.01/196.78 242.01/196.78 } 242.01/196.78 module Maybe where { 242.01/196.78 import qualified FiniteMap; 242.01/196.78 import qualified Main; 242.01/196.78 import qualified Prelude; 242.01/196.78 isJust :: Maybe a -> Bool; 242.01/196.78 isJust Nothing = False; 242.01/196.78 isJust _ = True; 242.01/196.78 242.01/196.78 } 242.01/196.78 module Main where { 242.01/196.78 import qualified FiniteMap; 242.01/196.78 import qualified Maybe; 242.01/196.78 import qualified Prelude; 242.01/196.78 } 242.01/196.78 242.01/196.78 ---------------------------------------- 242.01/196.78 242.01/196.78 (1) LR (EQUIVALENT) 242.01/196.78 Lambda Reductions: 242.01/196.78 The following Lambda expression 242.01/196.78 "\oldnew->new" 242.01/196.78 is transformed to 242.01/196.78 "addToFM0 old new = new; 242.01/196.78 " 242.01/196.78 The following Lambda expression 242.01/196.78 "\leftright->right" 242.01/196.78 is transformed to 242.01/196.78 "intersectFM0 left right = right; 242.01/196.78 " 242.01/196.78 The following Lambda expression 242.01/196.78 "\(_,mid_elt2)->mid_elt2" 242.01/196.78 is transformed to 242.01/196.78 "mid_elt20 (_,mid_elt2) = mid_elt2; 242.01/196.78 " 242.01/196.78 The following Lambda expression 242.01/196.78 "\(mid_key2,_)->mid_key2" 242.01/196.78 is transformed to 242.01/196.78 "mid_key20 (mid_key2,_) = mid_key2; 242.01/196.78 " 242.01/196.78 The following Lambda expression 242.01/196.78 "\(mid_key1,_)->mid_key1" 242.01/196.78 is transformed to 242.01/196.78 "mid_key10 (mid_key1,_) = mid_key1; 242.01/196.78 " 242.01/196.78 The following Lambda expression 242.01/196.78 "\(_,mid_elt1)->mid_elt1" 242.01/196.78 is transformed to 242.01/196.78 "mid_elt10 (_,mid_elt1) = mid_elt1; 242.01/196.78 " 242.01/196.78 The following Lambda expression 242.01/196.78 "\keyeltrest->(key,elt) : rest" 242.01/196.78 is transformed to 242.01/196.78 "fmToList0 key elt rest = (key,elt) : rest; 242.01/196.78 " 242.01/196.78 The following Lambda expression 242.01/196.78 "\(Just elt1)->elt1" 242.01/196.78 is transformed to 242.01/196.78 "elt10 (Just elt1) = elt1; 242.01/196.78 " 242.01/196.78 242.01/196.78 ---------------------------------------- 242.01/196.78 242.01/196.78 (2) 242.01/196.78 Obligation: 242.01/196.78 mainModule Main 242.01/196.78 module FiniteMap where { 242.01/196.78 import qualified Main; 242.01/196.78 import qualified Maybe; 242.01/196.78 import qualified Prelude; 242.01/196.78 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 242.01/196.78 242.01/196.78 instance (Eq a, Eq b) => Eq FiniteMap b a where { 242.01/196.78 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 242.01/196.78 } 242.01/196.78 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 242.01/196.78 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 242.01/196.78 242.01/196.78 addToFM0 old new = new; 242.01/196.78 242.01/196.78 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 242.01/196.78 addToFM_C combiner EmptyFM key elt = unitFM key elt; 242.01/196.78 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 242.01/196.78 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 242.01/196.78 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 242.01/196.78 242.01/196.78 deleteMax :: Ord a => FiniteMap a b -> FiniteMap a b; 242.01/196.78 deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l; 242.01/196.78 deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 242.01/196.78 242.01/196.78 deleteMin :: Ord a => FiniteMap a b -> FiniteMap a b; 242.01/196.78 deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r; 242.01/196.78 deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 242.01/196.78 242.01/196.78 emptyFM :: FiniteMap b a; 242.01/196.78 emptyFM = EmptyFM; 242.01/196.78 242.01/196.78 findMax :: FiniteMap b a -> (b,a); 242.01/196.78 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 242.01/196.78 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 242.01/196.78 242.01/196.78 findMin :: FiniteMap b a -> (b,a); 242.01/196.78 findMin (Branch key elt _ EmptyFM _) = (key,elt); 242.01/196.78 findMin (Branch key elt _ fm_l _) = findMin fm_l; 242.01/196.78 242.01/196.78 fmToList :: FiniteMap a b -> [(a,b)]; 242.01/196.78 fmToList fm = foldFM fmToList0 [] fm; 242.01/196.78 242.01/196.78 fmToList0 key elt rest = (key,elt) : rest; 242.01/196.78 242.01/196.78 foldFM :: (b -> c -> a -> a) -> a -> FiniteMap b c -> a; 242.01/196.78 foldFM k z EmptyFM = z; 242.01/196.78 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 242.01/196.78 242.01/196.78 glueBal :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.01/196.78 glueBal EmptyFM fm2 = fm2; 242.01/196.78 glueBal fm1 EmptyFM = fm1; 242.01/196.78 glueBal fm1 fm2 | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2) 242.01/196.78 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 242.01/196.78 mid_elt1 = mid_elt10 vv2; 242.01/196.78 mid_elt10 (_,mid_elt1) = mid_elt1; 242.01/196.78 mid_elt2 = mid_elt20 vv3; 242.01/196.78 mid_elt20 (_,mid_elt2) = mid_elt2; 242.01/196.78 mid_key1 = mid_key10 vv2; 242.01/196.78 mid_key10 (mid_key1,_) = mid_key1; 242.01/196.78 mid_key2 = mid_key20 vv3; 242.01/196.78 mid_key20 (mid_key2,_) = mid_key2; 242.01/196.78 vv2 = findMax fm1; 242.01/196.78 vv3 = findMin fm2; 242.01/196.78 }; 242.01/196.78 242.01/196.78 glueVBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 glueVBal EmptyFM fm2 = fm2; 242.01/196.78 glueVBal fm1 EmptyFM = fm1; 242.01/196.78 glueVBal fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (glueVBal fm_l fm_rl) fm_rr 242.01/196.78 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r) 242.01/196.78 | otherwise = glueBal fm_l fm_r where { 242.01/196.78 size_l = sizeFM fm_l; 242.01/196.78 size_r = sizeFM fm_r; 242.01/196.78 }; 242.01/196.78 242.01/196.78 intersectFM :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.01/196.78 intersectFM fm1 fm2 = intersectFM_C intersectFM0 fm1 fm2; 242.01/196.78 242.01/196.78 intersectFM0 left right = right; 242.01/196.78 242.01/196.78 intersectFM_C :: Ord b => (d -> c -> a) -> FiniteMap b d -> FiniteMap b c -> FiniteMap b a; 242.01/196.78 intersectFM_C combiner fm1 EmptyFM = emptyFM; 242.01/196.78 intersectFM_C combiner EmptyFM fm2 = emptyFM; 242.01/196.78 intersectFM_C combiner fm1 (Branch split_key elt2 _ left right) | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) 242.01/196.78 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 242.01/196.78 elt1 = elt10 vv1; 242.01/196.78 elt10 (Just elt1) = elt1; 242.01/196.78 gts = splitGT fm1 split_key; 242.01/196.78 lts = splitLT fm1 split_key; 242.01/196.78 maybe_elt1 = lookupFM fm1 split_key; 242.01/196.78 vv1 = maybe_elt1; 242.01/196.78 }; 242.01/196.78 242.01/196.78 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 242.01/196.78 lookupFM EmptyFM key = Nothing; 242.01/196.78 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 242.01/196.78 | key_to_find > key = lookupFM fm_r key_to_find 242.01/196.78 | otherwise = Just elt; 242.01/196.78 242.01/196.78 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 242.01/196.78 | size_r > sIZE_RATIO * size_l = case fm_R of { 242.01/196.78 Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R 242.01/196.78 | otherwise -> double_L fm_L fm_R; 242.01/196.78 } 242.01/196.78 | size_l > sIZE_RATIO * size_r = case fm_L of { 242.01/196.78 Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R 242.01/196.78 | otherwise -> double_R fm_L fm_R; 242.01/196.78 } 242.01/196.78 | otherwise = mkBranch 2 key elt fm_L fm_R where { 242.01/196.78 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); 242.01/196.78 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); 242.01/196.78 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; 242.01/196.78 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); 242.01/196.78 size_l = sizeFM fm_L; 242.01/196.78 size_r = sizeFM fm_R; 242.01/196.78 }; 242.01/196.78 242.01/196.78 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 mkBranch which key elt fm_l fm_r = let { 242.01/196.78 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 242.01/196.78 } in result where { 242.01/196.78 balance_ok = True; 242.01/196.78 left_ok = case fm_l of { 242.01/196.78 EmptyFM-> True; 242.01/196.78 Branch left_key _ _ _ _-> let { 242.01/196.78 biggest_left_key = fst (findMax fm_l); 242.01/196.78 } in biggest_left_key < key; 242.01/196.78 } ; 242.01/196.78 left_size = sizeFM fm_l; 242.01/196.78 right_ok = case fm_r of { 242.01/196.78 EmptyFM-> True; 242.01/196.78 Branch right_key _ _ _ _-> let { 242.01/196.78 smallest_right_key = fst (findMin fm_r); 242.01/196.78 } in key < smallest_right_key; 242.01/196.78 } ; 242.01/196.78 right_size = sizeFM fm_r; 242.01/196.78 unbox :: Int -> Int; 242.01/196.78 unbox x = x; 242.01/196.78 }; 242.01/196.78 242.01/196.78 mkVBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 242.01/196.78 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 242.01/196.78 mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr 242.01/196.78 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 242.01/196.78 | otherwise = mkBranch 13 key elt fm_l fm_r where { 242.01/196.78 size_l = sizeFM fm_l; 242.01/196.78 size_r = sizeFM fm_r; 242.01/196.78 }; 242.01/196.78 242.01/196.78 sIZE_RATIO :: Int; 242.01/196.78 sIZE_RATIO = 5; 242.01/196.78 242.01/196.78 sizeFM :: FiniteMap a b -> Int; 242.01/196.78 sizeFM EmptyFM = 0; 242.01/196.78 sizeFM (Branch _ _ size _ _) = size; 242.01/196.78 242.01/196.78 splitGT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 242.01/196.78 splitGT EmptyFM split_key = emptyFM; 242.01/196.78 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 242.01/196.78 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 242.01/196.78 | otherwise = fm_r; 242.01/196.78 242.01/196.78 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 242.01/196.78 splitLT EmptyFM split_key = emptyFM; 242.01/196.78 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 242.01/196.78 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 242.01/196.78 | otherwise = fm_l; 242.01/196.78 242.01/196.78 unitFM :: b -> a -> FiniteMap b a; 242.01/196.78 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 242.01/196.78 242.01/196.78 } 242.01/196.78 module Maybe where { 242.01/196.78 import qualified FiniteMap; 242.01/196.78 import qualified Main; 242.01/196.78 import qualified Prelude; 242.01/196.78 isJust :: Maybe a -> Bool; 242.01/196.78 isJust Nothing = False; 242.01/196.78 isJust _ = True; 242.01/196.78 242.01/196.78 } 242.01/196.78 module Main where { 242.01/196.78 import qualified FiniteMap; 242.01/196.78 import qualified Maybe; 242.01/196.78 import qualified Prelude; 242.01/196.78 } 242.01/196.78 242.01/196.78 ---------------------------------------- 242.01/196.78 242.01/196.78 (3) CR (EQUIVALENT) 242.01/196.78 Case Reductions: 242.01/196.78 The following Case expression 242.01/196.78 "case compare x y of { 242.01/196.78 EQ -> o; 242.01/196.78 LT -> LT; 242.01/196.78 GT -> GT} 242.01/196.78 " 242.01/196.78 is transformed to 242.01/196.78 "primCompAux0 o EQ = o; 242.01/196.78 primCompAux0 o LT = LT; 242.01/196.78 primCompAux0 o GT = GT; 242.01/196.78 " 242.01/196.78 The following Case expression 242.01/196.78 "case fm_r of { 242.01/196.78 EmptyFM -> True; 242.01/196.78 Branch right_key _ _ _ _ -> let { 242.01/196.78 smallest_right_key = fst (findMin fm_r); 242.01/196.78 } in key < smallest_right_key} 242.01/196.78 " 242.01/196.78 is transformed to 242.01/196.78 "right_ok0 fm_r key EmptyFM = True; 242.01/196.78 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 242.01/196.78 smallest_right_key = fst (findMin fm_r); 242.01/196.78 } in key < smallest_right_key; 242.01/196.78 " 242.01/196.78 The following Case expression 242.01/196.78 "case fm_l of { 242.01/196.78 EmptyFM -> True; 242.01/196.78 Branch left_key _ _ _ _ -> let { 242.01/196.78 biggest_left_key = fst (findMax fm_l); 242.01/196.78 } in biggest_left_key < key} 242.01/196.78 " 242.01/196.78 is transformed to 242.01/196.78 "left_ok0 fm_l key EmptyFM = True; 242.01/196.78 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 242.01/196.78 biggest_left_key = fst (findMax fm_l); 242.01/196.78 } in biggest_left_key < key; 242.01/196.78 " 242.01/196.78 The following Case expression 242.01/196.78 "case fm_R of { 242.01/196.78 Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R} 242.01/196.78 " 242.01/196.78 is transformed to 242.01/196.78 "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; 242.01/196.78 " 242.01/196.78 The following Case expression 242.01/196.78 "case fm_L of { 242.01/196.78 Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R} 242.01/196.78 " 242.01/196.78 is transformed to 242.01/196.78 "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; 242.01/196.78 " 242.01/196.78 242.01/196.78 ---------------------------------------- 242.01/196.78 242.01/196.78 (4) 242.01/196.78 Obligation: 242.01/196.78 mainModule Main 242.01/196.78 module FiniteMap where { 242.01/196.78 import qualified Main; 242.01/196.78 import qualified Maybe; 242.01/196.78 import qualified Prelude; 242.01/196.78 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 242.01/196.78 242.01/196.78 instance (Eq a, Eq b) => Eq FiniteMap a b where { 242.01/196.78 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 242.01/196.78 } 242.01/196.78 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 242.01/196.78 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 242.01/196.78 242.01/196.78 addToFM0 old new = new; 242.01/196.78 242.01/196.78 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 242.01/196.78 addToFM_C combiner EmptyFM key elt = unitFM key elt; 242.01/196.78 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 242.01/196.78 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 242.01/196.78 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 242.01/196.78 242.01/196.78 deleteMax :: Ord a => FiniteMap a b -> FiniteMap a b; 242.01/196.78 deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l; 242.01/196.78 deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 242.01/196.78 242.01/196.78 deleteMin :: Ord a => FiniteMap a b -> FiniteMap a b; 242.01/196.78 deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r; 242.01/196.78 deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 242.01/196.78 242.01/196.78 emptyFM :: FiniteMap b a; 242.01/196.78 emptyFM = EmptyFM; 242.01/196.78 242.01/196.78 findMax :: FiniteMap b a -> (b,a); 242.01/196.78 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 242.01/196.78 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 242.01/196.78 242.01/196.78 findMin :: FiniteMap a b -> (a,b); 242.01/196.78 findMin (Branch key elt _ EmptyFM _) = (key,elt); 242.01/196.78 findMin (Branch key elt _ fm_l _) = findMin fm_l; 242.01/196.78 242.01/196.78 fmToList :: FiniteMap a b -> [(a,b)]; 242.01/196.78 fmToList fm = foldFM fmToList0 [] fm; 242.01/196.78 242.01/196.78 fmToList0 key elt rest = (key,elt) : rest; 242.01/196.78 242.01/196.78 foldFM :: (c -> b -> a -> a) -> a -> FiniteMap c b -> a; 242.01/196.78 foldFM k z EmptyFM = z; 242.01/196.78 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 242.01/196.78 242.01/196.78 glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.01/196.78 glueBal EmptyFM fm2 = fm2; 242.01/196.78 glueBal fm1 EmptyFM = fm1; 242.01/196.78 glueBal fm1 fm2 | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2) 242.01/196.78 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 242.01/196.78 mid_elt1 = mid_elt10 vv2; 242.01/196.78 mid_elt10 (_,mid_elt1) = mid_elt1; 242.01/196.78 mid_elt2 = mid_elt20 vv3; 242.01/196.78 mid_elt20 (_,mid_elt2) = mid_elt2; 242.01/196.78 mid_key1 = mid_key10 vv2; 242.01/196.78 mid_key10 (mid_key1,_) = mid_key1; 242.01/196.78 mid_key2 = mid_key20 vv3; 242.01/196.78 mid_key20 (mid_key2,_) = mid_key2; 242.01/196.78 vv2 = findMax fm1; 242.01/196.78 vv3 = findMin fm2; 242.01/196.78 }; 242.01/196.78 242.01/196.78 glueVBal :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.01/196.78 glueVBal EmptyFM fm2 = fm2; 242.01/196.78 glueVBal fm1 EmptyFM = fm1; 242.01/196.78 glueVBal fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (glueVBal fm_l fm_rl) fm_rr 242.01/196.78 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r) 242.01/196.78 | otherwise = glueBal fm_l fm_r where { 242.01/196.78 size_l = sizeFM fm_l; 242.01/196.78 size_r = sizeFM fm_r; 242.01/196.78 }; 242.01/196.78 242.01/196.78 intersectFM :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.01/196.78 intersectFM fm1 fm2 = intersectFM_C intersectFM0 fm1 fm2; 242.01/196.78 242.01/196.78 intersectFM0 left right = right; 242.20/196.78 242.20/196.78 intersectFM_C :: Ord a => (d -> c -> b) -> FiniteMap a d -> FiniteMap a c -> FiniteMap a b; 242.20/196.78 intersectFM_C combiner fm1 EmptyFM = emptyFM; 242.20/196.78 intersectFM_C combiner EmptyFM fm2 = emptyFM; 242.20/196.78 intersectFM_C combiner fm1 (Branch split_key elt2 _ left right) | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) 242.20/196.78 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 242.20/196.78 elt1 = elt10 vv1; 242.20/196.78 elt10 (Just elt1) = elt1; 242.20/196.78 gts = splitGT fm1 split_key; 242.20/196.78 lts = splitLT fm1 split_key; 242.20/196.78 maybe_elt1 = lookupFM fm1 split_key; 242.20/196.78 vv1 = maybe_elt1; 242.20/196.78 }; 242.20/196.78 242.20/196.78 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 242.20/196.78 lookupFM EmptyFM key = Nothing; 242.20/196.78 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 242.20/196.78 | key_to_find > key = lookupFM fm_r key_to_find 242.20/196.78 | otherwise = Just elt; 242.20/196.78 242.20/196.78 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.20/196.78 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 242.20/196.78 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 242.20/196.78 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 242.20/196.78 | otherwise = mkBranch 2 key elt fm_L fm_R where { 242.20/196.78 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); 242.20/196.78 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); 242.20/196.78 mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 242.20/196.78 | otherwise = double_L fm_L fm_R; 242.20/196.78 mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 242.20/196.78 | otherwise = double_R fm_L fm_R; 242.20/196.78 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; 242.20/196.78 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); 242.20/196.78 size_l = sizeFM fm_L; 242.20/196.78 size_r = sizeFM fm_R; 242.20/196.78 }; 242.20/196.78 242.20/196.78 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.20/196.78 mkBranch which key elt fm_l fm_r = let { 242.20/196.78 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 242.20/196.78 } in result where { 242.20/196.78 balance_ok = True; 242.20/196.78 left_ok = left_ok0 fm_l key fm_l; 242.20/196.78 left_ok0 fm_l key EmptyFM = True; 242.20/196.78 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 242.20/196.78 biggest_left_key = fst (findMax fm_l); 242.20/196.78 } in biggest_left_key < key; 242.20/196.78 left_size = sizeFM fm_l; 242.20/196.78 right_ok = right_ok0 fm_r key fm_r; 242.20/196.78 right_ok0 fm_r key EmptyFM = True; 242.20/196.78 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 242.20/196.78 smallest_right_key = fst (findMin fm_r); 242.20/196.78 } in key < smallest_right_key; 242.20/196.78 right_size = sizeFM fm_r; 242.20/196.78 unbox :: Int -> Int; 242.20/196.78 unbox x = x; 242.20/196.78 }; 242.20/196.78 242.20/196.78 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.20/196.78 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 242.75/196.94 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 242.75/196.94 mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr 242.75/196.94 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 242.75/196.94 | otherwise = mkBranch 13 key elt fm_l fm_r where { 242.75/196.94 size_l = sizeFM fm_l; 242.75/196.94 size_r = sizeFM fm_r; 242.75/196.94 }; 242.75/196.94 242.75/196.94 sIZE_RATIO :: Int; 242.75/196.94 sIZE_RATIO = 5; 242.75/196.94 242.75/196.94 sizeFM :: FiniteMap a b -> Int; 242.75/196.94 sizeFM EmptyFM = 0; 242.75/196.94 sizeFM (Branch _ _ size _ _) = size; 242.75/196.94 242.75/196.94 splitGT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 242.75/196.94 splitGT EmptyFM split_key = emptyFM; 242.75/196.94 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 242.75/196.94 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 242.75/196.94 | otherwise = fm_r; 242.75/196.94 242.75/196.94 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 242.75/196.94 splitLT EmptyFM split_key = emptyFM; 242.75/196.94 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 242.75/196.94 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 242.75/196.94 | otherwise = fm_l; 242.75/196.94 242.75/196.94 unitFM :: b -> a -> FiniteMap b a; 242.75/196.94 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 242.75/196.94 242.75/196.94 } 242.75/196.94 module Maybe where { 242.75/196.94 import qualified FiniteMap; 242.75/196.94 import qualified Main; 242.75/196.94 import qualified Prelude; 242.75/196.94 isJust :: Maybe a -> Bool; 242.75/196.94 isJust Nothing = False; 242.75/196.94 isJust _ = True; 242.75/196.94 242.75/196.94 } 242.75/196.94 module Main where { 242.75/196.94 import qualified FiniteMap; 242.75/196.94 import qualified Maybe; 242.75/196.94 import qualified Prelude; 242.75/196.94 } 242.75/196.94 242.75/196.94 ---------------------------------------- 242.75/196.94 242.75/196.94 (5) IFR (EQUIVALENT) 242.75/196.94 If Reductions: 242.75/196.94 The following If expression 242.75/196.94 "if primGEqNatS x y then Succ (primDivNatS (primMinusNatS x y) (Succ y)) else Zero" 242.75/196.94 is transformed to 242.75/196.94 "primDivNatS0 x y True = Succ (primDivNatS (primMinusNatS x y) (Succ y)); 242.75/196.94 primDivNatS0 x y False = Zero; 242.75/196.94 " 242.75/196.94 The following If expression 242.75/196.94 "if primGEqNatS x y then primModNatS (primMinusNatS x y) (Succ y) else Succ x" 242.75/196.94 is transformed to 242.75/196.94 "primModNatS0 x y True = primModNatS (primMinusNatS x y) (Succ y); 242.75/196.94 primModNatS0 x y False = Succ x; 242.75/196.94 " 242.75/196.94 242.75/196.94 ---------------------------------------- 242.75/196.94 242.75/196.94 (6) 242.75/196.94 Obligation: 242.75/196.94 mainModule Main 242.75/196.94 module FiniteMap where { 242.75/196.94 import qualified Main; 242.75/196.94 import qualified Maybe; 242.75/196.94 import qualified Prelude; 242.75/196.94 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 242.75/196.94 242.75/196.94 instance (Eq a, Eq b) => Eq FiniteMap b a where { 242.75/196.94 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 242.75/196.94 } 242.75/196.94 addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b; 242.75/196.94 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 242.75/196.94 242.75/196.94 addToFM0 old new = new; 242.75/196.94 242.75/196.94 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 242.75/196.94 addToFM_C combiner EmptyFM key elt = unitFM key elt; 242.75/196.94 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 242.75/196.94 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 242.75/196.94 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 242.75/196.94 242.75/196.94 deleteMax :: Ord a => FiniteMap a b -> FiniteMap a b; 242.75/196.94 deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l; 242.75/196.94 deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 242.75/196.94 242.75/196.94 deleteMin :: Ord a => FiniteMap a b -> FiniteMap a b; 242.75/196.94 deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r; 242.75/196.94 deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 242.75/196.94 242.75/196.94 emptyFM :: FiniteMap b a; 242.75/196.94 emptyFM = EmptyFM; 242.75/196.94 242.75/196.94 findMax :: FiniteMap b a -> (b,a); 242.75/196.94 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 242.75/196.94 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 242.75/196.94 242.75/196.94 findMin :: FiniteMap b a -> (b,a); 242.75/196.94 findMin (Branch key elt _ EmptyFM _) = (key,elt); 242.75/196.94 findMin (Branch key elt _ fm_l _) = findMin fm_l; 242.75/196.94 242.75/196.94 fmToList :: FiniteMap a b -> [(a,b)]; 242.75/196.94 fmToList fm = foldFM fmToList0 [] fm; 242.75/196.94 242.75/196.94 fmToList0 key elt rest = (key,elt) : rest; 242.75/196.94 242.75/196.94 foldFM :: (a -> c -> b -> b) -> b -> FiniteMap a c -> b; 242.75/196.94 foldFM k z EmptyFM = z; 242.75/196.94 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 242.75/196.94 242.75/196.94 glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.75/196.94 glueBal EmptyFM fm2 = fm2; 242.75/196.94 glueBal fm1 EmptyFM = fm1; 242.75/196.94 glueBal fm1 fm2 | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2) 242.75/196.94 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 242.75/196.94 mid_elt1 = mid_elt10 vv2; 242.75/196.94 mid_elt10 (_,mid_elt1) = mid_elt1; 242.75/196.94 mid_elt2 = mid_elt20 vv3; 242.75/196.94 mid_elt20 (_,mid_elt2) = mid_elt2; 242.75/196.94 mid_key1 = mid_key10 vv2; 242.75/196.94 mid_key10 (mid_key1,_) = mid_key1; 242.75/196.94 mid_key2 = mid_key20 vv3; 242.75/196.94 mid_key20 (mid_key2,_) = mid_key2; 242.75/196.94 vv2 = findMax fm1; 242.75/196.94 vv3 = findMin fm2; 242.75/196.94 }; 242.75/196.94 242.75/196.94 glueVBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.75/196.94 glueVBal EmptyFM fm2 = fm2; 242.75/196.94 glueVBal fm1 EmptyFM = fm1; 242.75/196.94 glueVBal fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (glueVBal fm_l fm_rl) fm_rr 242.75/196.94 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (glueVBal fm_lr fm_r) 242.75/196.94 | otherwise = glueBal fm_l fm_r where { 242.75/196.94 size_l = sizeFM fm_l; 242.75/196.94 size_r = sizeFM fm_r; 242.75/196.94 }; 242.75/196.94 242.75/196.94 intersectFM :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.75/196.94 intersectFM fm1 fm2 = intersectFM_C intersectFM0 fm1 fm2; 242.75/196.94 242.75/196.94 intersectFM0 left right = right; 242.75/196.94 242.75/196.94 intersectFM_C :: Ord d => (b -> a -> c) -> FiniteMap d b -> FiniteMap d a -> FiniteMap d c; 242.75/196.94 intersectFM_C combiner fm1 EmptyFM = emptyFM; 242.75/196.94 intersectFM_C combiner EmptyFM fm2 = emptyFM; 242.75/196.94 intersectFM_C combiner fm1 (Branch split_key elt2 _ left right) | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) 242.75/196.94 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 242.75/196.94 elt1 = elt10 vv1; 242.75/196.94 elt10 (Just elt1) = elt1; 242.75/196.94 gts = splitGT fm1 split_key; 242.75/196.94 lts = splitLT fm1 split_key; 242.75/196.94 maybe_elt1 = lookupFM fm1 split_key; 242.75/196.94 vv1 = maybe_elt1; 242.75/196.94 }; 242.75/196.94 242.75/196.94 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 242.75/196.94 lookupFM EmptyFM key = Nothing; 242.75/196.94 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 242.75/196.94 | key_to_find > key = lookupFM fm_r key_to_find 242.75/196.94 | otherwise = Just elt; 242.75/196.94 242.75/196.94 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.75/196.94 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 242.75/196.94 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 242.75/196.94 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 242.75/196.94 | otherwise = mkBranch 2 key elt fm_L fm_R where { 242.75/196.94 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); 242.75/196.94 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); 242.75/196.94 mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 242.75/196.94 | otherwise = double_L fm_L fm_R; 242.75/196.94 mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 242.75/196.94 | otherwise = double_R fm_L fm_R; 242.75/196.94 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; 242.75/196.94 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); 242.75/196.94 size_l = sizeFM fm_L; 242.75/196.94 size_r = sizeFM fm_R; 242.75/196.94 }; 242.75/196.94 242.75/196.94 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.75/196.94 mkBranch which key elt fm_l fm_r = let { 242.75/196.94 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 242.75/196.94 } in result where { 242.75/196.94 balance_ok = True; 242.75/196.94 left_ok = left_ok0 fm_l key fm_l; 242.75/196.94 left_ok0 fm_l key EmptyFM = True; 242.75/196.94 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 242.75/196.94 biggest_left_key = fst (findMax fm_l); 242.75/196.94 } in biggest_left_key < key; 242.75/196.94 left_size = sizeFM fm_l; 242.75/196.94 right_ok = right_ok0 fm_r key fm_r; 242.75/196.94 right_ok0 fm_r key EmptyFM = True; 242.75/196.94 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 242.75/196.94 smallest_right_key = fst (findMin fm_r); 242.75/196.94 } in key < smallest_right_key; 242.75/196.94 right_size = sizeFM fm_r; 242.75/196.94 unbox :: Int -> Int; 242.75/196.94 unbox x = x; 242.75/196.94 }; 242.75/196.94 242.75/196.94 mkVBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.75/196.94 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 242.75/196.94 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 242.75/196.94 mkVBalBranch key elt fm_l@(Branch key_l elt_l _ fm_ll fm_lr) fm_r@(Branch key_r elt_r _ fm_rl fm_rr) | sIZE_RATIO * size_l < size_r = mkBalBranch key_r elt_r (mkVBalBranch key elt fm_l fm_rl) fm_rr 242.75/196.94 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 242.75/196.94 | otherwise = mkBranch 13 key elt fm_l fm_r where { 242.75/196.94 size_l = sizeFM fm_l; 242.75/196.94 size_r = sizeFM fm_r; 242.75/196.94 }; 242.75/196.94 242.75/196.94 sIZE_RATIO :: Int; 242.75/196.94 sIZE_RATIO = 5; 242.75/196.94 242.75/196.94 sizeFM :: FiniteMap b a -> Int; 242.75/196.94 sizeFM EmptyFM = 0; 242.75/196.94 sizeFM (Branch _ _ size _ _) = size; 242.75/196.94 242.75/196.94 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 242.75/196.94 splitGT EmptyFM split_key = emptyFM; 242.75/196.94 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 242.75/196.94 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 242.75/196.94 | otherwise = fm_r; 242.75/196.94 242.75/196.94 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 242.75/196.94 splitLT EmptyFM split_key = emptyFM; 242.75/196.94 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 242.75/196.94 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 242.75/196.94 | otherwise = fm_l; 242.75/196.94 242.75/196.94 unitFM :: b -> a -> FiniteMap b a; 242.75/196.94 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 242.75/196.94 242.75/196.94 } 242.75/196.94 module Maybe where { 242.75/196.94 import qualified FiniteMap; 242.75/196.94 import qualified Main; 242.75/196.94 import qualified Prelude; 242.75/196.94 isJust :: Maybe a -> Bool; 242.75/196.94 isJust Nothing = False; 242.75/196.94 isJust _ = True; 242.75/196.94 242.75/196.94 } 242.75/196.94 module Main where { 242.75/196.94 import qualified FiniteMap; 242.75/196.94 import qualified Maybe; 242.75/196.94 import qualified Prelude; 242.75/196.94 } 242.75/196.94 242.75/196.94 ---------------------------------------- 242.75/196.94 242.75/196.94 (7) BR (EQUIVALENT) 242.75/196.94 Replaced joker patterns by fresh variables and removed binding patterns. 242.75/196.94 242.75/196.94 Binding Reductions: 242.75/196.94 The bind variable of the following binding Pattern 242.75/196.94 "fm_l@(Branch vwz vxu vxv vxw vxx)" 242.75/196.94 is replaced by the following term 242.75/196.94 "Branch vwz vxu vxv vxw vxx" 242.75/196.94 The bind variable of the following binding Pattern 242.75/196.94 "fm_r@(Branch vxz vyu vyv vyw vyx)" 242.75/196.94 is replaced by the following term 242.75/196.94 "Branch vxz vyu vyv vyw vyx" 242.75/196.94 The bind variable of the following binding Pattern 242.75/196.94 "fm_l@(Branch vzv vzw vzx vzy vzz)" 242.75/196.94 is replaced by the following term 242.75/196.94 "Branch vzv vzw vzx vzy vzz" 242.75/196.94 The bind variable of the following binding Pattern 242.75/196.94 "fm_r@(Branch wuv wuw wux wuy wuz)" 242.75/196.94 is replaced by the following term 242.75/196.94 "Branch wuv wuw wux wuy wuz" 242.75/196.94 242.75/196.94 ---------------------------------------- 242.75/196.94 242.75/196.94 (8) 242.75/196.94 Obligation: 242.75/196.94 mainModule Main 242.75/196.94 module FiniteMap where { 242.75/196.94 import qualified Main; 242.75/196.94 import qualified Maybe; 242.75/196.94 import qualified Prelude; 242.75/196.94 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 242.75/196.94 242.75/196.94 instance (Eq a, Eq b) => Eq FiniteMap b a where { 242.75/196.94 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 242.75/196.94 } 242.75/196.94 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 242.75/196.94 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 242.75/196.94 242.75/196.94 addToFM0 old new = new; 242.75/196.94 242.75/196.94 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 242.75/196.95 addToFM_C combiner EmptyFM key elt = unitFM key elt; 242.75/196.95 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 242.75/196.95 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 242.75/196.95 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 242.75/196.95 242.75/196.95 deleteMax :: Ord a => FiniteMap a b -> FiniteMap a b; 242.75/196.95 deleteMax (Branch key elt wvu fm_l EmptyFM) = fm_l; 242.75/196.95 deleteMax (Branch key elt wvv fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 242.75/196.95 242.75/196.95 deleteMin :: Ord a => FiniteMap a b -> FiniteMap a b; 242.75/196.95 deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r; 242.75/196.95 deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 242.75/196.95 242.75/196.95 emptyFM :: FiniteMap a b; 242.75/196.95 emptyFM = EmptyFM; 242.75/196.95 242.75/196.95 findMax :: FiniteMap a b -> (a,b); 242.75/196.95 findMax (Branch key elt vvw vvx EmptyFM) = (key,elt); 242.75/196.95 findMax (Branch key elt vvy vvz fm_r) = findMax fm_r; 242.75/196.95 242.75/196.95 findMin :: FiniteMap b a -> (b,a); 242.75/196.95 findMin (Branch key elt wyy EmptyFM wyz) = (key,elt); 242.75/196.95 findMin (Branch key elt wzu fm_l wzv) = findMin fm_l; 242.75/196.95 242.75/196.95 fmToList :: FiniteMap a b -> [(a,b)]; 242.75/196.95 fmToList fm = foldFM fmToList0 [] fm; 242.75/196.95 242.75/196.95 fmToList0 key elt rest = (key,elt) : rest; 242.75/196.95 242.75/196.95 foldFM :: (a -> b -> c -> c) -> c -> FiniteMap a b -> c; 242.75/196.95 foldFM k z EmptyFM = z; 242.75/196.95 foldFM k z (Branch key elt vyy fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 242.75/196.95 242.75/196.95 glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.75/196.95 glueBal EmptyFM fm2 = fm2; 242.75/196.95 glueBal fm1 EmptyFM = fm1; 242.75/196.95 glueBal fm1 fm2 | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2) 242.75/196.95 | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 242.75/196.95 mid_elt1 = mid_elt10 vv2; 242.75/196.95 mid_elt10 (vwv,mid_elt1) = mid_elt1; 242.75/196.95 mid_elt2 = mid_elt20 vv3; 242.75/196.95 mid_elt20 (vwu,mid_elt2) = mid_elt2; 242.75/196.95 mid_key1 = mid_key10 vv2; 242.75/196.95 mid_key10 (mid_key1,vww) = mid_key1; 242.75/196.95 mid_key2 = mid_key20 vv3; 242.75/196.95 mid_key20 (mid_key2,vwx) = mid_key2; 242.75/196.95 vv2 = findMax fm1; 242.75/196.95 vv3 = findMin fm2; 242.75/196.95 }; 242.75/196.95 242.75/196.95 glueVBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.75/196.95 glueVBal EmptyFM fm2 = fm2; 242.75/196.95 glueVBal fm1 EmptyFM = fm1; 242.75/196.95 glueVBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) | sIZE_RATIO * size_l < size_r = mkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx 242.75/196.95 | sIZE_RATIO * size_r < size_l = mkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx)) 242.75/196.95 | otherwise = glueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) where { 242.75/196.95 size_l = sizeFM (Branch vwz vxu vxv vxw vxx); 242.75/196.95 size_r = sizeFM (Branch vxz vyu vyv vyw vyx); 242.75/196.95 }; 242.75/196.95 242.75/196.95 intersectFM :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.75/196.95 intersectFM fm1 fm2 = intersectFM_C intersectFM0 fm1 fm2; 242.75/196.95 242.75/196.95 intersectFM0 left right = right; 242.75/196.95 242.75/196.95 intersectFM_C :: Ord c => (a -> b -> d) -> FiniteMap c a -> FiniteMap c b -> FiniteMap c d; 242.75/196.95 intersectFM_C combiner fm1 EmptyFM = emptyFM; 242.75/196.95 intersectFM_C combiner EmptyFM fm2 = emptyFM; 242.75/196.95 intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) | Maybe.isJust maybe_elt1 = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) 242.75/196.95 | otherwise = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 242.75/196.95 elt1 = elt10 vv1; 242.75/196.95 elt10 (Just elt1) = elt1; 242.75/196.95 gts = splitGT fm1 split_key; 242.75/196.95 lts = splitLT fm1 split_key; 242.75/196.95 maybe_elt1 = lookupFM fm1 split_key; 242.75/196.95 vv1 = maybe_elt1; 242.75/196.95 }; 242.75/196.95 242.75/196.95 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 242.75/196.95 lookupFM EmptyFM key = Nothing; 242.75/196.95 lookupFM (Branch key elt vyz fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 242.75/196.95 | key_to_find > key = lookupFM fm_r key_to_find 242.75/196.95 | otherwise = Just elt; 242.75/196.95 242.75/196.95 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.75/196.95 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 242.75/196.95 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 242.75/196.95 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 242.75/196.95 | otherwise = mkBranch 2 key elt fm_L fm_R where { 242.75/196.95 double_L fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy 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); 242.75/196.95 double_R (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz 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); 242.75/196.95 mkBalBranch0 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 242.75/196.95 | otherwise = double_L fm_L fm_R; 242.75/196.95 mkBalBranch1 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 242.75/196.95 | otherwise = double_R fm_L fm_R; 242.75/196.95 single_L fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 242.75/196.95 single_R (Branch key_l elt_l wvx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 242.75/196.95 size_l = sizeFM fm_L; 242.75/196.95 size_r = sizeFM fm_R; 242.75/196.95 }; 242.75/196.95 242.75/196.95 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 242.75/196.95 mkBranch which key elt fm_l fm_r = let { 242.75/196.95 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 242.75/196.95 } in result where { 242.75/196.95 balance_ok = True; 242.75/196.95 left_ok = left_ok0 fm_l key fm_l; 242.75/196.95 left_ok0 fm_l key EmptyFM = True; 242.75/196.95 left_ok0 fm_l key (Branch left_key vuu vuv vuw vux) = let { 242.75/196.95 biggest_left_key = fst (findMax fm_l); 242.75/196.95 } in biggest_left_key < key; 242.75/196.95 left_size = sizeFM fm_l; 242.75/196.95 right_ok = right_ok0 fm_r key fm_r; 242.75/196.95 right_ok0 fm_r key EmptyFM = True; 242.75/196.95 right_ok0 fm_r key (Branch right_key vuy vuz vvu vvv) = let { 242.75/196.95 smallest_right_key = fst (findMin fm_r); 242.75/196.95 } in key < smallest_right_key; 242.75/196.95 right_size = sizeFM fm_r; 242.75/196.95 unbox :: Int -> Int; 242.75/196.95 unbox x = x; 242.75/196.95 }; 242.75/196.95 242.75/196.95 mkVBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 242.75/196.95 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 242.75/196.95 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 242.75/196.95 mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) | sIZE_RATIO * size_l < size_r = mkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz 242.75/196.95 | sIZE_RATIO * size_r < size_l = mkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz)) 242.75/196.95 | otherwise = mkBranch 13 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) where { 242.75/196.95 size_l = sizeFM (Branch vzv vzw vzx vzy vzz); 242.75/196.95 size_r = sizeFM (Branch wuv wuw wux wuy wuz); 242.75/196.95 }; 242.75/196.95 242.75/196.95 sIZE_RATIO :: Int; 242.75/196.95 sIZE_RATIO = 5; 242.75/196.95 242.75/196.95 sizeFM :: FiniteMap a b -> Int; 242.75/196.95 sizeFM EmptyFM = 0; 242.75/196.95 sizeFM (Branch wxx wxy size wxz wyu) = size; 242.75/196.95 242.75/196.95 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 242.75/196.95 splitGT EmptyFM split_key = emptyFM; 242.75/196.95 splitGT (Branch key elt wvw fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 242.75/196.95 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 242.75/196.95 | otherwise = fm_r; 242.75/196.95 242.75/196.95 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 242.75/196.95 splitLT EmptyFM split_key = emptyFM; 242.75/196.95 splitLT (Branch key elt zz fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 242.75/196.95 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 242.75/196.95 | otherwise = fm_l; 242.75/196.95 242.75/196.95 unitFM :: b -> a -> FiniteMap b a; 242.75/196.95 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 242.75/196.95 242.75/196.95 } 242.75/196.95 module Maybe where { 242.75/196.95 import qualified FiniteMap; 242.75/196.95 import qualified Main; 242.75/196.95 import qualified Prelude; 242.75/196.95 isJust :: Maybe a -> Bool; 242.75/196.95 isJust Nothing = False; 242.75/196.95 isJust wzw = True; 242.75/196.95 242.75/196.95 } 242.75/196.95 module Main where { 242.75/196.95 import qualified FiniteMap; 242.75/196.95 import qualified Maybe; 242.75/196.95 import qualified Prelude; 242.75/196.95 } 242.75/196.95 242.75/196.95 ---------------------------------------- 242.75/196.95 242.75/196.95 (9) COR (EQUIVALENT) 242.75/196.95 Cond Reductions: 242.75/196.95 The following Function with conditions 242.75/196.95 "compare x y|x == yEQ|x <= yLT|otherwiseGT; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "compare x y = compare3 x y; 242.75/196.95 " 242.75/196.95 "compare0 x y True = GT; 242.75/196.95 " 242.75/196.95 "compare1 x y True = LT; 242.75/196.95 compare1 x y False = compare0 x y otherwise; 242.75/196.95 " 242.75/196.95 "compare2 x y True = EQ; 242.75/196.95 compare2 x y False = compare1 x y (x <= y); 242.75/196.95 " 242.75/196.95 "compare3 x y = compare2 x y (x == y); 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "absReal x|x >= 0x|otherwise`negate` x; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "absReal x = absReal2 x; 242.75/196.95 " 242.75/196.95 "absReal0 x True = `negate` x; 242.75/196.95 " 242.75/196.95 "absReal1 x True = x; 242.75/196.95 absReal1 x False = absReal0 x otherwise; 242.75/196.95 " 242.75/196.95 "absReal2 x = absReal1 x (x >= 0); 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "gcd' x 0 = x; 242.75/196.95 gcd' x y = gcd' y (x `rem` y); 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "gcd' x wzx = gcd'2 x wzx; 242.75/196.95 gcd' x y = gcd'0 x y; 242.75/196.95 " 242.75/196.95 "gcd'0 x y = gcd' y (x `rem` y); 242.75/196.95 " 242.75/196.95 "gcd'1 True x wzx = x; 242.75/196.95 gcd'1 wzy wzz xuu = gcd'0 wzz xuu; 242.75/196.95 " 242.75/196.95 "gcd'2 x wzx = gcd'1 (wzx == 0) x wzx; 242.75/196.95 gcd'2 xuv xuw = gcd'0 xuv xuw; 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "gcd 0 0 = error []; 242.75/196.95 gcd x y = gcd' (abs x) (abs y) where { 242.75/196.95 gcd' x 0 = x; 242.75/196.95 gcd' x y = gcd' y (x `rem` y); 242.75/196.95 } 242.75/196.95 ; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "gcd xux xuy = gcd3 xux xuy; 242.75/196.95 gcd x y = gcd0 x y; 242.75/196.95 " 242.75/196.95 "gcd0 x y = gcd' (abs x) (abs y) where { 242.75/196.95 gcd' x wzx = gcd'2 x wzx; 242.75/196.95 gcd' x y = gcd'0 x y; 242.75/196.95 ; 242.75/196.95 gcd'0 x y = gcd' y (x `rem` y); 242.75/196.95 ; 242.75/196.95 gcd'1 True x wzx = x; 242.75/196.95 gcd'1 wzy wzz xuu = gcd'0 wzz xuu; 242.75/196.95 ; 242.75/196.95 gcd'2 x wzx = gcd'1 (wzx == 0) x wzx; 242.75/196.95 gcd'2 xuv xuw = gcd'0 xuv xuw; 242.75/196.95 } 242.75/196.95 ; 242.75/196.95 " 242.75/196.95 "gcd1 True xux xuy = error []; 242.75/196.95 gcd1 xuz xvu xvv = gcd0 xvu xvv; 242.75/196.95 " 242.75/196.95 "gcd2 True xux xuy = gcd1 (xuy == 0) xux xuy; 242.75/196.95 gcd2 xvw xvx xvy = gcd0 xvx xvy; 242.75/196.95 " 242.75/196.95 "gcd3 xux xuy = gcd2 (xux == 0) xux xuy; 242.75/196.95 gcd3 xvz xwu = gcd0 xvz xwu; 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "undefined |Falseundefined; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "undefined = undefined1; 242.75/196.95 " 242.75/196.95 "undefined0 True = undefined; 242.75/196.95 " 242.75/196.95 "undefined1 = undefined0 False; 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "reduce x y|y == 0error []|otherwisex `quot` d :% (y `quot` d) where { 242.75/196.95 d = gcd x y; 242.75/196.95 } 242.75/196.95 ; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "reduce x y = reduce2 x y; 242.75/196.95 " 242.75/196.95 "reduce2 x y = reduce1 x y (y == 0) where { 242.75/196.95 d = gcd x y; 242.75/196.95 ; 242.75/196.95 reduce0 x y True = x `quot` d :% (y `quot` d); 242.75/196.95 ; 242.75/196.95 reduce1 x y True = error []; 242.75/196.95 reduce1 x y False = reduce0 x y otherwise; 242.75/196.95 } 242.75/196.95 ; 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "splitLT EmptyFM split_key = emptyFM; 242.75/196.95 splitLT (Branch key elt zz fm_l fm_r) split_key|split_key < keysplitLT fm_l split_key|split_key > keymkVBalBranch key elt fm_l (splitLT fm_r split_key)|otherwisefm_l; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 242.75/196.95 splitLT (Branch key elt zz fm_l fm_r) split_key = splitLT3 (Branch key elt zz fm_l fm_r) split_key; 242.75/196.95 " 242.75/196.95 "splitLT1 key elt zz fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 242.75/196.95 splitLT1 key elt zz fm_l fm_r split_key False = splitLT0 key elt zz fm_l fm_r split_key otherwise; 242.75/196.95 " 242.75/196.95 "splitLT2 key elt zz fm_l fm_r split_key True = splitLT fm_l split_key; 242.75/196.95 splitLT2 key elt zz fm_l fm_r split_key False = splitLT1 key elt zz fm_l fm_r split_key (split_key > key); 242.75/196.95 " 242.75/196.95 "splitLT0 key elt zz fm_l fm_r split_key True = fm_l; 242.75/196.95 " 242.75/196.95 "splitLT3 (Branch key elt zz fm_l fm_r) split_key = splitLT2 key elt zz fm_l fm_r split_key (split_key < key); 242.75/196.95 " 242.75/196.95 "splitLT4 EmptyFM split_key = emptyFM; 242.75/196.95 splitLT4 xwx xwy = splitLT3 xwx xwy; 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "glueBal EmptyFM fm2 = fm2; 242.75/196.95 glueBal fm1 EmptyFM = fm1; 242.75/196.95 glueBal fm1 fm2|sizeFM fm2 > sizeFM fm1mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2)|otherwisemkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { 242.75/196.95 mid_elt1 = mid_elt10 vv2; 242.75/196.95 ; 242.75/196.95 mid_elt10 (vwv,mid_elt1) = mid_elt1; 242.75/196.95 ; 242.75/196.95 mid_elt2 = mid_elt20 vv3; 242.75/196.95 ; 242.75/196.95 mid_elt20 (vwu,mid_elt2) = mid_elt2; 242.75/196.95 ; 242.75/196.95 mid_key1 = mid_key10 vv2; 242.75/196.95 ; 242.75/196.95 mid_key10 (mid_key1,vww) = mid_key1; 242.75/196.95 ; 242.75/196.95 mid_key2 = mid_key20 vv3; 242.75/196.95 ; 242.75/196.95 mid_key20 (mid_key2,vwx) = mid_key2; 242.75/196.95 ; 242.75/196.95 vv2 = findMax fm1; 242.75/196.95 ; 242.75/196.95 vv3 = findMin fm2; 242.75/196.95 } 242.75/196.95 ; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2; 242.75/196.95 glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM; 242.75/196.95 glueBal fm1 fm2 = glueBal2 fm1 fm2; 242.75/196.95 " 242.75/196.95 "glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where { 242.75/196.95 glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2; 242.75/196.95 ; 242.75/196.95 glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2); 242.75/196.95 glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise; 242.75/196.95 ; 242.75/196.95 mid_elt1 = mid_elt10 vv2; 242.75/196.95 ; 242.75/196.95 mid_elt10 (vwv,mid_elt1) = mid_elt1; 242.75/196.95 ; 242.75/196.95 mid_elt2 = mid_elt20 vv3; 242.75/196.95 ; 242.75/196.95 mid_elt20 (vwu,mid_elt2) = mid_elt2; 242.75/196.95 ; 242.75/196.95 mid_key1 = mid_key10 vv2; 242.75/196.95 ; 242.75/196.95 mid_key10 (mid_key1,vww) = mid_key1; 242.75/196.95 ; 242.75/196.95 mid_key2 = mid_key20 vv3; 242.75/196.95 ; 242.75/196.95 mid_key20 (mid_key2,vwx) = mid_key2; 242.75/196.95 ; 242.75/196.95 vv2 = findMax fm1; 242.75/196.95 ; 242.75/196.95 vv3 = findMin fm2; 242.75/196.95 } 242.75/196.95 ; 242.75/196.95 " 242.75/196.95 "glueBal3 fm1 EmptyFM = fm1; 242.75/196.95 glueBal3 xxu xxv = glueBal2 xxu xxv; 242.75/196.95 " 242.75/196.95 "glueBal4 EmptyFM fm2 = fm2; 242.75/196.95 glueBal4 xxx xxy = glueBal3 xxx xxy; 242.75/196.95 " 242.75/196.95 The following Function with conditions 242.75/196.95 "glueVBal EmptyFM fm2 = fm2; 242.75/196.95 glueVBal fm1 EmptyFM = fm1; 242.75/196.95 glueVBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx)|sIZE_RATIO * size_l < size_rmkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx|sIZE_RATIO * size_r < size_lmkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx))|otherwiseglueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) where { 242.75/196.95 size_l = sizeFM (Branch vwz vxu vxv vxw vxx); 242.75/196.95 ; 242.75/196.95 size_r = sizeFM (Branch vxz vyu vyv vyw vyx); 242.75/196.95 } 242.75/196.95 ; 242.75/196.95 " 242.75/196.95 is transformed to 242.75/196.95 "glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2; 242.75/196.95 glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM; 242.75/196.95 glueVBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 242.75/196.95 " 242.75/196.95 "glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * size_l < size_r) where { 242.75/196.95 glueVBal0 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = glueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.09 ; 243.36/197.09 glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx)); 243.36/197.09 glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal0 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx otherwise; 243.36/197.09 ; 243.36/197.09 glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx; 243.36/197.09 glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * size_r < size_l); 243.36/197.09 ; 243.36/197.09 size_l = sizeFM (Branch vwz vxu vxv vxw vxx); 243.36/197.09 ; 243.36/197.09 size_r = sizeFM (Branch vxz vyu vyv vyw vyx); 243.36/197.09 } 243.36/197.09 ; 243.36/197.09 " 243.36/197.09 "glueVBal4 fm1 EmptyFM = fm1; 243.36/197.09 glueVBal4 xyw xyx = glueVBal3 xyw xyx; 243.36/197.09 " 243.36/197.09 "glueVBal5 EmptyFM fm2 = fm2; 243.36/197.09 glueVBal5 xyz xzu = glueVBal4 xyz xzu; 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "lookupFM EmptyFM key = Nothing; 243.36/197.09 lookupFM (Branch key elt vyz fm_l fm_r) key_to_find|key_to_find < keylookupFM fm_l key_to_find|key_to_find > keylookupFM fm_r key_to_find|otherwiseJust elt; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "lookupFM EmptyFM key = lookupFM4 EmptyFM key; 243.36/197.09 lookupFM (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find; 243.36/197.09 " 243.36/197.09 "lookupFM0 key elt vyz fm_l fm_r key_to_find True = Just elt; 243.36/197.09 " 243.36/197.09 "lookupFM2 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 243.36/197.09 lookupFM2 key elt vyz fm_l fm_r key_to_find False = lookupFM1 key elt vyz fm_l fm_r key_to_find (key_to_find > key); 243.36/197.09 " 243.36/197.09 "lookupFM1 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 243.36/197.09 lookupFM1 key elt vyz fm_l fm_r key_to_find False = lookupFM0 key elt vyz fm_l fm_r key_to_find otherwise; 243.36/197.09 " 243.36/197.09 "lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM2 key elt vyz fm_l fm_r key_to_find (key_to_find < key); 243.36/197.09 " 243.36/197.09 "lookupFM4 EmptyFM key = Nothing; 243.36/197.09 lookupFM4 xzx xzy = lookupFM3 xzx xzy; 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "addToFM_C combiner EmptyFM key elt = unitFM key elt; 243.36/197.09 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; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 243.36/197.09 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; 243.36/197.09 " 243.36/197.09 "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; 243.36/197.09 " 243.36/197.09 "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); 243.36/197.09 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; 243.36/197.09 " 243.36/197.09 "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; 243.36/197.09 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); 243.36/197.09 " 243.36/197.09 "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); 243.36/197.09 " 243.36/197.09 "addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 243.36/197.09 addToFM_C4 yuv yuw yux yuy = addToFM_C3 yuv yuw yux yuy; 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 243.36/197.09 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 243.36/197.09 mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz)|sIZE_RATIO * size_l < size_rmkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz|sIZE_RATIO * size_r < size_lmkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz))|otherwisemkBranch 13 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) where { 243.36/197.09 size_l = sizeFM (Branch vzv vzw vzx vzy vzz); 243.36/197.09 ; 243.36/197.09 size_r = sizeFM (Branch wuv wuw wux wuy wuz); 243.36/197.09 } 243.36/197.09 ; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 243.36/197.09 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 243.36/197.09 mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.09 " 243.36/197.09 "mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * size_l < size_r) where { 243.36/197.09 mkVBalBranch0 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBranch 13 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.09 ; 243.36/197.09 mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz)); 243.36/197.09 mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch0 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz otherwise; 243.36/197.09 ; 243.36/197.09 mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz; 243.36/197.09 mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * size_r < size_l); 243.36/197.09 ; 243.36/197.09 size_l = sizeFM (Branch vzv vzw vzx vzy vzz); 243.36/197.09 ; 243.36/197.09 size_r = sizeFM (Branch wuv wuw wux wuy wuz); 243.36/197.09 } 243.36/197.09 ; 243.36/197.09 " 243.36/197.09 "mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 243.36/197.09 mkVBalBranch4 yvw yvx yvy yvz = mkVBalBranch3 yvw yvx yvy yvz; 243.36/197.09 " 243.36/197.09 "mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 243.36/197.09 mkVBalBranch5 ywv yww ywx ywy = mkVBalBranch4 ywv yww ywx ywy; 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "splitGT EmptyFM split_key = emptyFM; 243.36/197.09 splitGT (Branch key elt wvw fm_l fm_r) split_key|split_key > keysplitGT fm_r split_key|split_key < keymkVBalBranch key elt (splitGT fm_l split_key) fm_r|otherwisefm_r; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 243.36/197.09 splitGT (Branch key elt wvw fm_l fm_r) split_key = splitGT3 (Branch key elt wvw fm_l fm_r) split_key; 243.36/197.09 " 243.36/197.09 "splitGT0 key elt wvw fm_l fm_r split_key True = fm_r; 243.36/197.09 " 243.36/197.09 "splitGT2 key elt wvw fm_l fm_r split_key True = splitGT fm_r split_key; 243.36/197.09 splitGT2 key elt wvw fm_l fm_r split_key False = splitGT1 key elt wvw fm_l fm_r split_key (split_key < key); 243.36/197.09 " 243.36/197.09 "splitGT1 key elt wvw fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 243.36/197.09 splitGT1 key elt wvw fm_l fm_r split_key False = splitGT0 key elt wvw fm_l fm_r split_key otherwise; 243.36/197.09 " 243.36/197.09 "splitGT3 (Branch key elt wvw fm_l fm_r) split_key = splitGT2 key elt wvw fm_l fm_r split_key (split_key > key); 243.36/197.09 " 243.36/197.09 "splitGT4 EmptyFM split_key = emptyFM; 243.36/197.09 splitGT4 yxv yxw = splitGT3 yxv yxw; 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "mkBalBranch1 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "mkBalBranch1 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr); 243.36/197.09 " 243.36/197.09 "mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr True = single_R fm_L fm_R; 243.36/197.09 mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr False = mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr otherwise; 243.36/197.09 " 243.36/197.09 "mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr True = double_R fm_L fm_R; 243.36/197.09 " 243.36/197.09 "mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "mkBalBranch0 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "mkBalBranch0 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr); 243.36/197.09 " 243.36/197.09 "mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = double_L fm_L fm_R; 243.36/197.09 " 243.36/197.09 "mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = single_L fm_L fm_R; 243.36/197.09 mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr otherwise; 243.36/197.09 " 243.36/197.09 "mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "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 { 243.36/197.09 double_L fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy 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); 243.36/197.09 ; 243.36/197.09 double_R (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz 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); 243.36/197.09 ; 243.36/197.09 mkBalBranch0 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R; 243.36/197.09 ; 243.36/197.09 mkBalBranch1 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R; 243.36/197.09 ; 243.36/197.09 single_L fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 243.36/197.09 ; 243.36/197.09 single_R (Branch key_l elt_l wvx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 243.36/197.09 ; 243.36/197.09 size_l = sizeFM fm_L; 243.36/197.09 ; 243.36/197.09 size_r = sizeFM fm_R; 243.36/197.09 } 243.36/197.09 ; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 243.36/197.09 " 243.36/197.09 "mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 243.36/197.09 double_L fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy 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); 243.36/197.09 ; 243.36/197.09 double_R (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz 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); 243.36/197.09 ; 243.36/197.09 mkBalBranch0 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr); 243.36/197.09 ; 243.36/197.09 mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = double_L fm_L fm_R; 243.36/197.09 ; 243.36/197.09 mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = single_L fm_L fm_R; 243.36/197.09 mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr otherwise; 243.36/197.09 ; 243.36/197.09 mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 243.36/197.09 ; 243.36/197.09 mkBalBranch1 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr); 243.36/197.09 ; 243.36/197.09 mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr True = double_R fm_L fm_R; 243.36/197.09 ; 243.36/197.09 mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr True = single_R fm_L fm_R; 243.36/197.09 mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr False = mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr otherwise; 243.36/197.09 ; 243.36/197.09 mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 243.36/197.09 ; 243.36/197.09 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 243.36/197.09 ; 243.36/197.09 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 243.36/197.09 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 243.36/197.09 ; 243.36/197.09 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 243.36/197.09 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 243.36/197.09 ; 243.36/197.09 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 243.36/197.09 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 243.36/197.09 ; 243.36/197.09 single_L fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 243.36/197.09 ; 243.36/197.09 single_R (Branch key_l elt_l wvx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 243.36/197.09 ; 243.36/197.09 size_l = sizeFM fm_L; 243.36/197.09 ; 243.36/197.09 size_r = sizeFM fm_R; 243.36/197.09 } 243.36/197.09 ; 243.36/197.09 " 243.36/197.09 The following Function with conditions 243.36/197.09 "intersectFM_C combiner fm1 EmptyFM = emptyFM; 243.36/197.09 intersectFM_C combiner EmptyFM fm2 = emptyFM; 243.36/197.09 intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right)|Maybe.isJust maybe_elt1mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right)|otherwiseglueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right) where { 243.36/197.09 elt1 = elt10 vv1; 243.36/197.09 ; 243.36/197.09 elt10 (Just elt1) = elt1; 243.36/197.09 ; 243.36/197.09 gts = splitGT fm1 split_key; 243.36/197.09 ; 243.36/197.09 lts = splitLT fm1 split_key; 243.36/197.09 ; 243.36/197.09 maybe_elt1 = lookupFM fm1 split_key; 243.36/197.09 ; 243.36/197.09 vv1 = maybe_elt1; 243.36/197.09 } 243.36/197.09 ; 243.36/197.09 " 243.36/197.09 is transformed to 243.36/197.09 "intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM; 243.36/197.09 intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2; 243.36/197.09 intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right); 243.36/197.09 " 243.36/197.09 "intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C1 combiner fm1 split_key elt2 wyx left right (Maybe.isJust maybe_elt1) where { 243.36/197.09 elt1 = elt10 vv1; 243.36/197.09 ; 243.36/197.09 elt10 (Just elt1) = elt1; 243.36/197.09 ; 243.36/197.09 gts = splitGT fm1 split_key; 243.36/197.09 ; 243.36/197.09 intersectFM_C0 combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right); 243.36/197.09 ; 243.36/197.09 intersectFM_C1 combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right); 243.36/197.09 intersectFM_C1 combiner fm1 split_key elt2 wyx left right False = intersectFM_C0 combiner fm1 split_key elt2 wyx left right otherwise; 243.36/197.09 ; 243.36/197.09 lts = splitLT fm1 split_key; 243.36/197.09 ; 243.36/197.09 maybe_elt1 = lookupFM fm1 split_key; 243.36/197.09 ; 243.36/197.09 vv1 = maybe_elt1; 243.36/197.09 } 243.36/197.09 ; 243.36/197.09 " 243.36/197.09 "intersectFM_C3 combiner EmptyFM fm2 = emptyFM; 243.36/197.09 intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx; 243.36/197.09 " 243.36/197.09 "intersectFM_C4 combiner fm1 EmptyFM = emptyFM; 243.36/197.09 intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv; 243.36/197.09 " 243.36/197.09 243.36/197.09 ---------------------------------------- 243.36/197.09 243.36/197.09 (10) 243.36/197.09 Obligation: 243.36/197.09 mainModule Main 243.36/197.09 module FiniteMap where { 243.36/197.09 import qualified Main; 243.36/197.09 import qualified Maybe; 243.36/197.09 import qualified Prelude; 243.36/197.09 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 243.36/197.09 243.36/197.09 instance (Eq a, Eq b) => Eq FiniteMap a b where { 243.36/197.09 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 243.36/197.09 } 243.36/197.09 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 243.36/197.09 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 243.36/197.09 243.36/197.09 addToFM0 old new = new; 243.36/197.09 243.36/197.09 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 243.36/197.09 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 243.36/197.09 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; 243.36/197.09 243.36/197.09 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; 243.36/197.09 243.36/197.09 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); 243.36/197.09 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; 243.36/197.09 243.36/197.09 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; 243.36/197.09 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); 243.36/197.09 243.36/197.09 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); 243.36/197.09 243.36/197.09 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 243.36/197.09 addToFM_C4 yuv yuw yux yuy = addToFM_C3 yuv yuw yux yuy; 243.36/197.09 243.36/197.09 deleteMax :: Ord b => FiniteMap b a -> FiniteMap b a; 243.36/197.09 deleteMax (Branch key elt wvu fm_l EmptyFM) = fm_l; 243.36/197.09 deleteMax (Branch key elt wvv fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 243.36/197.09 243.36/197.09 deleteMin :: Ord a => FiniteMap a b -> FiniteMap a b; 243.36/197.09 deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r; 243.36/197.09 deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 243.36/197.09 243.36/197.09 emptyFM :: FiniteMap b a; 243.36/197.09 emptyFM = EmptyFM; 243.36/197.09 243.36/197.09 findMax :: FiniteMap a b -> (a,b); 243.36/197.09 findMax (Branch key elt vvw vvx EmptyFM) = (key,elt); 243.36/197.09 findMax (Branch key elt vvy vvz fm_r) = findMax fm_r; 243.36/197.09 243.36/197.09 findMin :: FiniteMap b a -> (b,a); 243.36/197.09 findMin (Branch key elt wyy EmptyFM wyz) = (key,elt); 243.36/197.09 findMin (Branch key elt wzu fm_l wzv) = findMin fm_l; 243.36/197.09 243.36/197.09 fmToList :: FiniteMap b a -> [(b,a)]; 243.36/197.09 fmToList fm = foldFM fmToList0 [] fm; 243.36/197.09 243.36/197.09 fmToList0 key elt rest = (key,elt) : rest; 243.36/197.09 243.36/197.09 foldFM :: (b -> c -> a -> a) -> a -> FiniteMap b c -> a; 243.36/197.09 foldFM k z EmptyFM = z; 243.36/197.09 foldFM k z (Branch key elt vyy fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 243.36/197.09 243.36/197.09 glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.09 glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2; 243.36/197.09 glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM; 243.36/197.09 glueBal fm1 fm2 = glueBal2 fm1 fm2; 243.36/197.09 243.36/197.09 glueBal2 fm1 fm2 = glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where { 243.36/197.09 glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2; 243.36/197.09 glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2); 243.36/197.09 glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise; 243.36/197.09 mid_elt1 = mid_elt10 vv2; 243.36/197.09 mid_elt10 (vwv,mid_elt1) = mid_elt1; 243.36/197.09 mid_elt2 = mid_elt20 vv3; 243.36/197.09 mid_elt20 (vwu,mid_elt2) = mid_elt2; 243.36/197.09 mid_key1 = mid_key10 vv2; 243.36/197.09 mid_key10 (mid_key1,vww) = mid_key1; 243.36/197.09 mid_key2 = mid_key20 vv3; 243.36/197.09 mid_key20 (mid_key2,vwx) = mid_key2; 243.36/197.09 vv2 = findMax fm1; 243.36/197.09 vv3 = findMin fm2; 243.36/197.09 }; 243.36/197.09 243.36/197.09 glueBal3 fm1 EmptyFM = fm1; 243.36/197.09 glueBal3 xxu xxv = glueBal2 xxu xxv; 243.36/197.09 243.36/197.09 glueBal4 EmptyFM fm2 = fm2; 243.36/197.09 glueBal4 xxx xxy = glueBal3 xxx xxy; 243.36/197.09 243.36/197.09 glueVBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.09 glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2; 243.36/197.09 glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM; 243.36/197.09 glueVBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.09 243.36/197.09 glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * size_l < size_r) where { 243.36/197.09 glueVBal0 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = glueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.09 glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx)); 243.36/197.09 glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal0 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx otherwise; 243.36/197.09 glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx; 243.36/197.09 glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * size_r < size_l); 243.36/197.09 size_l = sizeFM (Branch vwz vxu vxv vxw vxx); 243.36/197.09 size_r = sizeFM (Branch vxz vyu vyv vyw vyx); 243.36/197.09 }; 243.36/197.09 243.36/197.09 glueVBal4 fm1 EmptyFM = fm1; 243.36/197.09 glueVBal4 xyw xyx = glueVBal3 xyw xyx; 243.36/197.09 243.36/197.09 glueVBal5 EmptyFM fm2 = fm2; 243.36/197.09 glueVBal5 xyz xzu = glueVBal4 xyz xzu; 243.36/197.09 243.36/197.09 intersectFM :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.09 intersectFM fm1 fm2 = intersectFM_C intersectFM0 fm1 fm2; 243.36/197.09 243.36/197.09 intersectFM0 left right = right; 243.36/197.09 243.36/197.09 intersectFM_C :: Ord d => (b -> c -> a) -> FiniteMap d b -> FiniteMap d c -> FiniteMap d a; 243.36/197.09 intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM; 243.36/197.09 intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2; 243.36/197.09 intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right); 243.36/197.09 243.36/197.09 intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C1 combiner fm1 split_key elt2 wyx left right (Maybe.isJust maybe_elt1) where { 243.36/197.09 elt1 = elt10 vv1; 243.36/197.09 elt10 (Just elt1) = elt1; 243.36/197.09 gts = splitGT fm1 split_key; 243.36/197.09 intersectFM_C0 combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right); 243.36/197.09 intersectFM_C1 combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right); 243.36/197.09 intersectFM_C1 combiner fm1 split_key elt2 wyx left right False = intersectFM_C0 combiner fm1 split_key elt2 wyx left right otherwise; 243.36/197.09 lts = splitLT fm1 split_key; 243.36/197.09 maybe_elt1 = lookupFM fm1 split_key; 243.36/197.09 vv1 = maybe_elt1; 243.36/197.09 }; 243.36/197.09 243.36/197.09 intersectFM_C3 combiner EmptyFM fm2 = emptyFM; 243.36/197.09 intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx; 243.36/197.09 243.36/197.09 intersectFM_C4 combiner fm1 EmptyFM = emptyFM; 243.36/197.09 intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv; 243.36/197.09 243.36/197.09 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 243.36/197.09 lookupFM EmptyFM key = lookupFM4 EmptyFM key; 243.36/197.09 lookupFM (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find; 243.36/197.09 243.36/197.09 lookupFM0 key elt vyz fm_l fm_r key_to_find True = Just elt; 243.36/197.09 243.36/197.09 lookupFM1 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 243.36/197.09 lookupFM1 key elt vyz fm_l fm_r key_to_find False = lookupFM0 key elt vyz fm_l fm_r key_to_find otherwise; 243.36/197.09 243.36/197.09 lookupFM2 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 243.36/197.09 lookupFM2 key elt vyz fm_l fm_r key_to_find False = lookupFM1 key elt vyz fm_l fm_r key_to_find (key_to_find > key); 243.36/197.09 243.36/197.09 lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM2 key elt vyz fm_l fm_r key_to_find (key_to_find < key); 243.36/197.09 243.36/197.09 lookupFM4 EmptyFM key = Nothing; 243.36/197.09 lookupFM4 xzx xzy = lookupFM3 xzx xzy; 243.36/197.09 243.36/197.09 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.09 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 243.36/197.09 243.36/197.09 mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 243.36/197.09 double_L fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy 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); 243.36/197.09 double_R (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz 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); 243.36/197.09 mkBalBranch0 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr); 243.36/197.09 mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = double_L fm_L fm_R; 243.36/197.09 mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = single_L fm_L fm_R; 243.36/197.09 mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr otherwise; 243.36/197.09 mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 243.36/197.09 mkBalBranch1 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr); 243.36/197.09 mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr True = double_R fm_L fm_R; 243.36/197.09 mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr True = single_R fm_L fm_R; 243.36/197.09 mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr False = mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr otherwise; 243.36/197.09 mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 243.36/197.09 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 243.36/197.09 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 243.36/197.09 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 243.36/197.09 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 243.36/197.09 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 243.36/197.09 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 243.36/197.09 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 243.36/197.09 single_L fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 243.36/197.09 single_R (Branch key_l elt_l wvx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 243.36/197.09 size_l = sizeFM fm_L; 243.36/197.09 size_r = sizeFM fm_R; 243.36/197.09 }; 243.36/197.09 243.36/197.09 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.09 mkBranch which key elt fm_l fm_r = let { 243.36/197.09 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 243.36/197.09 } in result where { 243.36/197.09 balance_ok = True; 243.36/197.09 left_ok = left_ok0 fm_l key fm_l; 243.36/197.09 left_ok0 fm_l key EmptyFM = True; 243.36/197.09 left_ok0 fm_l key (Branch left_key vuu vuv vuw vux) = let { 243.36/197.09 biggest_left_key = fst (findMax fm_l); 243.36/197.09 } in biggest_left_key < key; 243.36/197.09 left_size = sizeFM fm_l; 243.36/197.09 right_ok = right_ok0 fm_r key fm_r; 243.36/197.09 right_ok0 fm_r key EmptyFM = True; 243.36/197.09 right_ok0 fm_r key (Branch right_key vuy vuz vvu vvv) = let { 243.36/197.09 smallest_right_key = fst (findMin fm_r); 243.36/197.09 } in key < smallest_right_key; 243.36/197.09 right_size = sizeFM fm_r; 243.36/197.09 unbox :: Int -> Int; 243.36/197.09 unbox x = x; 243.36/197.09 }; 243.36/197.09 243.36/197.09 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.09 mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 243.36/197.09 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 243.36/197.09 mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.09 243.36/197.09 mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * size_l < size_r) where { 243.36/197.09 mkVBalBranch0 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBranch 13 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.09 mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz)); 243.36/197.09 mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch0 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz otherwise; 243.36/197.09 mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz; 243.36/197.09 mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * size_r < size_l); 243.36/197.09 size_l = sizeFM (Branch vzv vzw vzx vzy vzz); 243.36/197.09 size_r = sizeFM (Branch wuv wuw wux wuy wuz); 243.36/197.09 }; 243.36/197.09 243.36/197.09 mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 243.36/197.09 mkVBalBranch4 yvw yvx yvy yvz = mkVBalBranch3 yvw yvx yvy yvz; 243.36/197.09 243.36/197.09 mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 243.36/197.09 mkVBalBranch5 ywv yww ywx ywy = mkVBalBranch4 ywv yww ywx ywy; 243.36/197.09 243.36/197.09 sIZE_RATIO :: Int; 243.36/197.09 sIZE_RATIO = 5; 243.36/197.09 243.36/197.09 sizeFM :: FiniteMap a b -> Int; 243.36/197.09 sizeFM EmptyFM = 0; 243.36/197.09 sizeFM (Branch wxx wxy size wxz wyu) = size; 243.36/197.09 243.36/197.09 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 243.36/197.09 splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 243.36/197.09 splitGT (Branch key elt wvw fm_l fm_r) split_key = splitGT3 (Branch key elt wvw fm_l fm_r) split_key; 243.36/197.09 243.36/197.09 splitGT0 key elt wvw fm_l fm_r split_key True = fm_r; 243.36/197.09 243.36/197.09 splitGT1 key elt wvw fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 243.36/197.09 splitGT1 key elt wvw fm_l fm_r split_key False = splitGT0 key elt wvw fm_l fm_r split_key otherwise; 243.36/197.09 243.36/197.09 splitGT2 key elt wvw fm_l fm_r split_key True = splitGT fm_r split_key; 243.36/197.09 splitGT2 key elt wvw fm_l fm_r split_key False = splitGT1 key elt wvw fm_l fm_r split_key (split_key < key); 243.36/197.09 243.36/197.09 splitGT3 (Branch key elt wvw fm_l fm_r) split_key = splitGT2 key elt wvw fm_l fm_r split_key (split_key > key); 243.36/197.09 243.36/197.09 splitGT4 EmptyFM split_key = emptyFM; 243.36/197.09 splitGT4 yxv yxw = splitGT3 yxv yxw; 243.36/197.09 243.36/197.09 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 243.36/197.09 splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 243.36/197.09 splitLT (Branch key elt zz fm_l fm_r) split_key = splitLT3 (Branch key elt zz fm_l fm_r) split_key; 243.36/197.09 243.36/197.09 splitLT0 key elt zz fm_l fm_r split_key True = fm_l; 243.36/197.09 243.36/197.09 splitLT1 key elt zz fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 243.36/197.09 splitLT1 key elt zz fm_l fm_r split_key False = splitLT0 key elt zz fm_l fm_r split_key otherwise; 243.36/197.09 243.36/197.09 splitLT2 key elt zz fm_l fm_r split_key True = splitLT fm_l split_key; 243.36/197.09 splitLT2 key elt zz fm_l fm_r split_key False = splitLT1 key elt zz fm_l fm_r split_key (split_key > key); 243.36/197.09 243.36/197.09 splitLT3 (Branch key elt zz fm_l fm_r) split_key = splitLT2 key elt zz fm_l fm_r split_key (split_key < key); 243.36/197.09 243.36/197.09 splitLT4 EmptyFM split_key = emptyFM; 243.36/197.09 splitLT4 xwx xwy = splitLT3 xwx xwy; 243.36/197.09 243.36/197.09 unitFM :: b -> a -> FiniteMap b a; 243.36/197.09 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 243.36/197.09 243.36/197.09 } 243.36/197.09 module Maybe where { 243.36/197.09 import qualified FiniteMap; 243.36/197.09 import qualified Main; 243.36/197.09 import qualified Prelude; 243.36/197.09 isJust :: Maybe a -> Bool; 243.36/197.09 isJust Nothing = False; 243.36/197.09 isJust wzw = True; 243.36/197.09 243.36/197.09 } 243.36/197.09 module Main where { 243.36/197.09 import qualified FiniteMap; 243.36/197.09 import qualified Maybe; 243.36/197.09 import qualified Prelude; 243.36/197.09 } 243.36/197.09 243.36/197.09 ---------------------------------------- 243.36/197.09 243.36/197.09 (11) LetRed (EQUIVALENT) 243.36/197.09 Let/Where Reductions: 243.36/197.09 The bindings of the following Let/Where expression 243.36/197.09 "gcd' (abs x) (abs y) where { 243.36/197.09 gcd' x wzx = gcd'2 x wzx; 243.36/197.09 gcd' x y = gcd'0 x y; 243.36/197.09 ; 243.36/197.09 gcd'0 x y = gcd' y (x `rem` y); 243.36/197.09 ; 243.36/197.09 gcd'1 True x wzx = x; 243.36/197.09 gcd'1 wzy wzz xuu = gcd'0 wzz xuu; 243.36/197.09 ; 243.36/197.09 gcd'2 x wzx = gcd'1 (wzx == 0) x wzx; 243.36/197.09 gcd'2 xuv xuw = gcd'0 xuv xuw; 243.36/197.09 } 243.36/197.09 " 243.36/197.09 are unpacked to the following functions on top level 243.36/197.09 "gcd0Gcd'0 x y = gcd0Gcd' y (x `rem` y); 243.36/197.09 " 243.36/197.09 "gcd0Gcd' x wzx = gcd0Gcd'2 x wzx; 243.36/197.09 gcd0Gcd' x y = gcd0Gcd'0 x y; 243.36/197.09 " 243.36/197.09 "gcd0Gcd'1 True x wzx = x; 243.36/197.09 gcd0Gcd'1 wzy wzz xuu = gcd0Gcd'0 wzz xuu; 243.36/197.09 " 243.36/197.09 "gcd0Gcd'2 x wzx = gcd0Gcd'1 (wzx == 0) x wzx; 243.36/197.09 gcd0Gcd'2 xuv xuw = gcd0Gcd'0 xuv xuw; 243.36/197.09 " 243.36/197.09 The bindings of the following Let/Where expression 243.36/197.09 "reduce1 x y (y == 0) where { 243.36/197.09 d = gcd x y; 243.36/197.09 ; 243.36/197.09 reduce0 x y True = x `quot` d :% (y `quot` d); 243.36/197.09 ; 243.36/197.09 reduce1 x y True = error []; 243.36/197.09 reduce1 x y False = reduce0 x y otherwise; 243.36/197.09 } 243.36/197.09 " 243.36/197.09 are unpacked to the following functions on top level 243.36/197.09 "reduce2Reduce1 yzw yzx x y True = error []; 243.36/197.09 reduce2Reduce1 yzw yzx x y False = reduce2Reduce0 yzw yzx x y otherwise; 243.36/197.09 " 243.36/197.09 "reduce2D yzw yzx = gcd yzw yzx; 243.36/197.09 " 243.36/197.09 "reduce2Reduce0 yzw yzx x y True = x `quot` reduce2D yzw yzx :% (y `quot` reduce2D yzw yzx); 243.36/197.09 " 243.36/197.09 The bindings of the following Let/Where expression 243.36/197.09 "glueBal1 fm1 fm2 (sizeFM fm2 > sizeFM fm1) where { 243.36/197.09 glueBal0 fm1 fm2 True = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2; 243.36/197.09 ; 243.36/197.09 glueBal1 fm1 fm2 True = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2); 243.36/197.09 glueBal1 fm1 fm2 False = glueBal0 fm1 fm2 otherwise; 243.36/197.09 ; 243.36/197.09 mid_elt1 = mid_elt10 vv2; 243.36/197.09 ; 243.36/197.09 mid_elt10 (vwv,mid_elt1) = mid_elt1; 243.36/197.09 ; 243.36/197.09 mid_elt2 = mid_elt20 vv3; 243.36/197.09 ; 243.36/197.09 mid_elt20 (vwu,mid_elt2) = mid_elt2; 243.36/197.09 ; 243.36/197.09 mid_key1 = mid_key10 vv2; 243.36/197.09 ; 243.36/197.09 mid_key10 (mid_key1,vww) = mid_key1; 243.36/197.09 ; 243.36/197.09 mid_key2 = mid_key20 vv3; 243.36/197.09 ; 243.36/197.09 mid_key20 (mid_key2,vwx) = mid_key2; 243.36/197.09 ; 243.36/197.09 vv2 = findMax fm1; 243.36/197.09 ; 243.36/197.09 vv3 = findMin fm2; 243.36/197.09 } 243.36/197.09 " 243.36/197.09 are unpacked to the following functions on top level 243.36/197.09 "glueBal2Vv3 yzy yzz = findMin yzy; 243.36/197.09 " 243.36/197.09 "glueBal2Mid_elt20 yzy yzz (vwu,mid_elt2) = mid_elt2; 243.36/197.09 " 243.36/197.09 "glueBal2Mid_key20 yzy yzz (mid_key2,vwx) = mid_key2; 243.36/197.09 " 243.36/197.09 "glueBal2Mid_key2 yzy yzz = glueBal2Mid_key20 yzy yzz (glueBal2Vv3 yzy yzz); 243.36/197.09 " 243.36/197.09 "glueBal2Mid_elt1 yzy yzz = glueBal2Mid_elt10 yzy yzz (glueBal2Vv2 yzy yzz); 243.36/197.09 " 243.36/197.09 "glueBal2Mid_key1 yzy yzz = glueBal2Mid_key10 yzy yzz (glueBal2Vv2 yzy yzz); 243.36/197.09 " 243.36/197.09 "glueBal2GlueBal1 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 yzy yzz) (glueBal2Mid_elt2 yzy yzz) fm1 (deleteMin fm2); 243.36/197.09 glueBal2GlueBal1 yzy yzz fm1 fm2 False = glueBal2GlueBal0 yzy yzz fm1 fm2 otherwise; 243.36/197.09 " 243.36/197.09 "glueBal2GlueBal0 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 yzy yzz) (glueBal2Mid_elt1 yzy yzz) (deleteMax fm1) fm2; 243.36/197.09 " 243.36/197.09 "glueBal2Mid_key10 yzy yzz (mid_key1,vww) = mid_key1; 243.36/197.09 " 243.36/197.09 "glueBal2Mid_elt2 yzy yzz = glueBal2Mid_elt20 yzy yzz (glueBal2Vv3 yzy yzz); 243.36/197.09 " 243.36/197.09 "glueBal2Vv2 yzy yzz = findMax yzz; 243.36/197.09 " 243.36/197.09 "glueBal2Mid_elt10 yzy yzz (vwv,mid_elt1) = mid_elt1; 243.36/197.09 " 243.36/197.09 The bindings of the following Let/Where expression 243.36/197.09 "mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * size_l < size_r) where { 243.36/197.09 mkVBalBranch0 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBranch 13 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.09 ; 243.36/197.09 mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz)); 243.36/197.09 mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch0 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz otherwise; 243.36/197.09 ; 243.36/197.09 mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz; 243.36/197.09 mkVBalBranch2 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch1 key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * size_r < size_l); 243.36/197.09 ; 243.36/197.09 size_l = sizeFM (Branch vzv vzw vzx vzy vzz); 243.36/197.09 ; 243.36/197.09 size_r = sizeFM (Branch wuv wuw wux wuy wuz); 243.36/197.09 } 243.36/197.09 " 243.36/197.09 are unpacked to the following functions on top level 243.36/197.09 "mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz)); 243.36/197.09 mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz otherwise; 243.36/197.09 " 243.36/197.09 "mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuu zuv zuw zux zuy); 243.36/197.09 " 243.36/197.09 "mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuz zvu zvv zvw zvx); 243.36/197.09 " 243.36/197.09 "mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz; 243.36/197.09 mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx < mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx); 243.36/197.09 " 243.36/197.09 "mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBranch 13 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.09 " 243.36/197.09 The bindings of the following Let/Where expression 243.36/197.09 "mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 243.36/197.09 double_L fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy 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); 243.36/197.09 ; 243.36/197.09 double_R (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz 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); 243.36/197.09 ; 243.36/197.09 mkBalBranch0 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr); 243.36/197.09 ; 243.36/197.09 mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = double_L fm_L fm_R; 243.36/197.09 ; 243.36/197.09 mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr True = single_L fm_L fm_R; 243.36/197.09 mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr False = mkBalBranch00 fm_L fm_R wwz wxu wxv fm_rl fm_rr otherwise; 243.36/197.09 ; 243.36/197.09 mkBalBranch02 fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch01 fm_L fm_R wwz wxu wxv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 243.36/197.09 ; 243.36/197.09 mkBalBranch1 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr); 243.36/197.09 ; 243.36/197.09 mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr True = double_R fm_L fm_R; 243.36/197.09 ; 243.36/197.09 mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr True = single_R fm_L fm_R; 243.36/197.09 mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr False = mkBalBranch10 fm_L fm_R wwu wwv www fm_ll fm_lr otherwise; 243.36/197.09 ; 243.36/197.09 mkBalBranch12 fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch11 fm_L fm_R wwu wwv www fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 243.36/197.09 ; 243.36/197.09 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 243.36/197.09 ; 243.36/197.09 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 243.36/197.09 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 243.36/197.09 ; 243.36/197.09 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 243.36/197.09 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 243.36/197.09 ; 243.36/197.09 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 243.36/197.09 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 243.36/197.10 ; 243.36/197.10 single_L fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 243.36/197.10 ; 243.36/197.10 single_R (Branch key_l elt_l wvx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 243.36/197.10 ; 243.36/197.10 size_l = sizeFM fm_L; 243.36/197.10 ; 243.36/197.10 size_r = sizeFM fm_R; 243.36/197.10 } 243.36/197.10 " 243.36/197.10 are unpacked to the following functions on top level 243.36/197.10 "mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr); 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr True = mkBalBranch6Double_L zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr True = mkBalBranch6Single_R zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr False = mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr otherwise; 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr True = mkBalBranch6Double_R zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 243.36/197.10 " 243.36/197.10 "mkBalBranch6Single_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 zvy zvz fm_l fm_rl) fm_rr; 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R fm_R; 243.36/197.10 mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_l zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_r zvy zvz zwu zwv); 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R fm_L; 243.36/197.10 mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R otherwise; 243.36/197.10 " 243.36/197.10 "mkBalBranch6Double_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 zvy zvz fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr); 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr); 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_r zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_l zvy zvz zwu zwv); 243.36/197.10 " 243.36/197.10 "mkBalBranch6Double_R zvy zvz zwu zwv (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 zvy zvz fm_lrr fm_r); 243.36/197.10 " 243.36/197.10 "mkBalBranch6Single_R zvy zvz zwu zwv (Branch key_l elt_l wvx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 zvy zvz fm_lr fm_r); 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 243.36/197.10 " 243.36/197.10 "mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr True = mkBalBranch6Single_L zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr False = mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr otherwise; 243.36/197.10 " 243.36/197.10 "mkBalBranch6Size_r zvy zvz zwu zwv = sizeFM zwu; 243.36/197.10 " 243.36/197.10 "mkBalBranch6Size_l zvy zvz zwu zwv = sizeFM zwv; 243.36/197.10 " 243.36/197.10 The bindings of the following Let/Where expression 243.36/197.10 "intersectFM_C1 combiner fm1 split_key elt2 wyx left right (Maybe.isJust maybe_elt1) where { 243.36/197.10 elt1 = elt10 vv1; 243.36/197.10 ; 243.36/197.10 elt10 (Just elt1) = elt1; 243.36/197.10 ; 243.36/197.10 gts = splitGT fm1 split_key; 243.36/197.10 ; 243.36/197.10 intersectFM_C0 combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner lts left) (intersectFM_C combiner gts right); 243.36/197.10 ; 243.36/197.10 intersectFM_C1 combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner elt1 elt2) (intersectFM_C combiner lts left) (intersectFM_C combiner gts right); 243.36/197.10 intersectFM_C1 combiner fm1 split_key elt2 wyx left right False = intersectFM_C0 combiner fm1 split_key elt2 wyx left right otherwise; 243.36/197.10 ; 243.36/197.10 lts = splitLT fm1 split_key; 243.36/197.10 ; 243.36/197.10 maybe_elt1 = lookupFM fm1 split_key; 243.36/197.10 ; 243.36/197.10 vv1 = maybe_elt1; 243.36/197.10 } 243.36/197.10 " 243.36/197.10 are unpacked to the following functions on top level 243.36/197.10 "intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right); 243.36/197.10 " 243.36/197.10 "intersectFM_C2Lts zww zwx = splitLT zww zwx; 243.36/197.10 " 243.36/197.10 "intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner (intersectFM_C2Elt1 zww zwx) elt2) (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right); 243.36/197.10 intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right False = intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right otherwise; 243.36/197.10 " 243.36/197.10 "intersectFM_C2Elt10 zww zwx (Just elt1) = elt1; 243.36/197.10 " 243.36/197.10 "intersectFM_C2Elt1 zww zwx = intersectFM_C2Elt10 zww zwx (intersectFM_C2Vv1 zww zwx); 243.36/197.10 " 243.36/197.10 "intersectFM_C2Vv1 zww zwx = intersectFM_C2Maybe_elt1 zww zwx; 243.36/197.10 " 243.36/197.10 "intersectFM_C2Maybe_elt1 zww zwx = lookupFM zww zwx; 243.36/197.10 " 243.36/197.10 "intersectFM_C2Gts zww zwx = splitGT zww zwx; 243.36/197.10 " 243.36/197.10 The bindings of the following Let/Where expression 243.36/197.10 "let { 243.36/197.10 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 243.36/197.10 } in result where { 243.36/197.10 balance_ok = True; 243.36/197.10 ; 243.36/197.10 left_ok = left_ok0 fm_l key fm_l; 243.36/197.10 ; 243.36/197.10 left_ok0 fm_l key EmptyFM = True; 243.36/197.10 left_ok0 fm_l key (Branch left_key vuu vuv vuw vux) = let { 243.36/197.10 biggest_left_key = fst (findMax fm_l); 243.36/197.10 } in biggest_left_key < key; 243.36/197.10 ; 243.36/197.10 left_size = sizeFM fm_l; 243.36/197.10 ; 243.36/197.10 right_ok = right_ok0 fm_r key fm_r; 243.36/197.10 ; 243.36/197.10 right_ok0 fm_r key EmptyFM = True; 243.36/197.10 right_ok0 fm_r key (Branch right_key vuy vuz vvu vvv) = let { 243.36/197.10 smallest_right_key = fst (findMin fm_r); 243.36/197.10 } in key < smallest_right_key; 243.36/197.10 ; 243.36/197.10 right_size = sizeFM fm_r; 243.36/197.10 ; 243.36/197.10 unbox x = x; 243.36/197.10 } 243.36/197.10 " 243.36/197.10 are unpacked to the following functions on top level 243.36/197.10 "mkBranchRight_ok zwy zwz zxu = mkBranchRight_ok0 zwy zwz zxu zwy zwz zwy; 243.36/197.10 " 243.36/197.10 "mkBranchLeft_size zwy zwz zxu = sizeFM zxu; 243.36/197.10 " 243.36/197.10 "mkBranchBalance_ok zwy zwz zxu = True; 243.36/197.10 " 243.36/197.10 "mkBranchRight_ok0 zwy zwz zxu fm_r key EmptyFM = True; 243.36/197.10 mkBranchRight_ok0 zwy zwz zxu fm_r key (Branch right_key vuy vuz vvu vvv) = key < mkBranchRight_ok0Smallest_right_key fm_r; 243.36/197.10 " 243.36/197.10 "mkBranchLeft_ok zwy zwz zxu = mkBranchLeft_ok0 zwy zwz zxu zxu zwz zxu; 243.36/197.10 " 243.36/197.10 "mkBranchLeft_ok0 zwy zwz zxu fm_l key EmptyFM = True; 243.36/197.10 mkBranchLeft_ok0 zwy zwz zxu fm_l key (Branch left_key vuu vuv vuw vux) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 243.36/197.10 " 243.36/197.10 "mkBranchUnbox zwy zwz zxu x = x; 243.36/197.10 " 243.36/197.10 "mkBranchRight_size zwy zwz zxu = sizeFM zwy; 243.36/197.10 " 243.36/197.10 The bindings of the following Let/Where expression 243.36/197.10 "let { 243.36/197.10 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 243.36/197.10 } in result" 243.36/197.10 are unpacked to the following functions on top level 243.36/197.10 "mkBranchResult zxv zxw zxx zxy = Branch zxv zxw (mkBranchUnbox zxx zxv zxy (1 + mkBranchLeft_size zxx zxv zxy + mkBranchRight_size zxx zxv zxy)) zxy zxx; 243.36/197.10 " 243.36/197.10 The bindings of the following Let/Where expression 243.36/197.10 "glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * size_l < size_r) where { 243.36/197.10 glueVBal0 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = glueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.10 ; 243.36/197.10 glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx)); 243.36/197.10 glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal0 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx otherwise; 243.36/197.10 ; 243.36/197.10 glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx; 243.36/197.10 glueVBal2 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal1 vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * size_r < size_l); 243.36/197.10 ; 243.36/197.10 size_l = sizeFM (Branch vwz vxu vxv vxw vxx); 243.36/197.10 ; 243.36/197.10 size_r = sizeFM (Branch vxz vyu vyv vyw vyx); 243.36/197.10 } 243.36/197.10 " 243.36/197.10 are unpacked to the following functions on top level 243.36/197.10 "glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zxz zyu zyv zyw zyx); 243.36/197.10 " 243.36/197.10 "glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx; 243.36/197.10 glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw < glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw); 243.36/197.10 " 243.36/197.10 "glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = glueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.10 " 243.36/197.10 "glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx)); 243.36/197.10 glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx otherwise; 243.36/197.10 " 243.36/197.10 "glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zyy zyz zzu zzv zzw); 243.36/197.10 " 243.36/197.10 The bindings of the following Let/Where expression 243.36/197.10 "let { 243.36/197.10 smallest_right_key = fst (findMin fm_r); 243.36/197.10 } in key < smallest_right_key" 243.36/197.10 are unpacked to the following functions on top level 243.36/197.10 "mkBranchRight_ok0Smallest_right_key zzx = fst (findMin zzx); 243.36/197.10 " 243.36/197.10 The bindings of the following Let/Where expression 243.36/197.10 "let { 243.36/197.10 biggest_left_key = fst (findMax fm_l); 243.36/197.10 } in biggest_left_key < key" 243.36/197.10 are unpacked to the following functions on top level 243.36/197.10 "mkBranchLeft_ok0Biggest_left_key zzy = fst (findMax zzy); 243.36/197.10 " 243.36/197.10 243.36/197.10 ---------------------------------------- 243.36/197.10 243.36/197.10 (12) 243.36/197.10 Obligation: 243.36/197.10 mainModule Main 243.36/197.10 module FiniteMap where { 243.36/197.10 import qualified Main; 243.36/197.10 import qualified Maybe; 243.36/197.10 import qualified Prelude; 243.36/197.10 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 243.36/197.10 243.36/197.10 instance (Eq a, Eq b) => Eq FiniteMap a b where { 243.36/197.10 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 243.36/197.10 } 243.36/197.10 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 243.36/197.10 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 243.36/197.10 243.36/197.10 addToFM0 old new = new; 243.36/197.10 243.36/197.10 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 243.36/197.10 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 243.36/197.10 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; 243.36/197.10 243.36/197.10 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; 243.36/197.10 243.36/197.10 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); 243.36/197.10 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; 243.36/197.10 243.36/197.10 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; 243.36/197.10 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); 243.36/197.10 243.36/197.10 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); 243.36/197.10 243.36/197.10 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 243.36/197.10 addToFM_C4 yuv yuw yux yuy = addToFM_C3 yuv yuw yux yuy; 243.36/197.10 243.36/197.10 deleteMax :: Ord b => FiniteMap b a -> FiniteMap b a; 243.36/197.10 deleteMax (Branch key elt wvu fm_l EmptyFM) = fm_l; 243.36/197.10 deleteMax (Branch key elt wvv fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 243.36/197.10 243.36/197.10 deleteMin :: Ord b => FiniteMap b a -> FiniteMap b a; 243.36/197.10 deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r; 243.36/197.10 deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 243.36/197.10 243.36/197.10 emptyFM :: FiniteMap a b; 243.36/197.10 emptyFM = EmptyFM; 243.36/197.10 243.36/197.10 findMax :: FiniteMap a b -> (a,b); 243.36/197.10 findMax (Branch key elt vvw vvx EmptyFM) = (key,elt); 243.36/197.10 findMax (Branch key elt vvy vvz fm_r) = findMax fm_r; 243.36/197.10 243.36/197.10 findMin :: FiniteMap b a -> (b,a); 243.36/197.10 findMin (Branch key elt wyy EmptyFM wyz) = (key,elt); 243.36/197.10 findMin (Branch key elt wzu fm_l wzv) = findMin fm_l; 243.36/197.10 243.36/197.10 fmToList :: FiniteMap b a -> [(b,a)]; 243.36/197.10 fmToList fm = foldFM fmToList0 [] fm; 243.36/197.10 243.36/197.10 fmToList0 key elt rest = (key,elt) : rest; 243.36/197.10 243.36/197.10 foldFM :: (b -> a -> c -> c) -> c -> FiniteMap b a -> c; 243.36/197.10 foldFM k z EmptyFM = z; 243.36/197.10 foldFM k z (Branch key elt vyy fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 243.36/197.10 243.36/197.10 glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.10 glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2; 243.36/197.10 glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM; 243.36/197.10 glueBal fm1 fm2 = glueBal2 fm1 fm2; 243.36/197.10 243.36/197.10 glueBal2 fm1 fm2 = glueBal2GlueBal1 fm2 fm1 fm1 fm2 (sizeFM fm2 > sizeFM fm1); 243.36/197.10 243.36/197.10 glueBal2GlueBal0 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 yzy yzz) (glueBal2Mid_elt1 yzy yzz) (deleteMax fm1) fm2; 243.36/197.10 243.36/197.10 glueBal2GlueBal1 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 yzy yzz) (glueBal2Mid_elt2 yzy yzz) fm1 (deleteMin fm2); 243.36/197.10 glueBal2GlueBal1 yzy yzz fm1 fm2 False = glueBal2GlueBal0 yzy yzz fm1 fm2 otherwise; 243.36/197.10 243.36/197.10 glueBal2Mid_elt1 yzy yzz = glueBal2Mid_elt10 yzy yzz (glueBal2Vv2 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_elt10 yzy yzz (vwv,mid_elt1) = mid_elt1; 243.36/197.10 243.36/197.10 glueBal2Mid_elt2 yzy yzz = glueBal2Mid_elt20 yzy yzz (glueBal2Vv3 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_elt20 yzy yzz (vwu,mid_elt2) = mid_elt2; 243.36/197.10 243.36/197.10 glueBal2Mid_key1 yzy yzz = glueBal2Mid_key10 yzy yzz (glueBal2Vv2 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_key10 yzy yzz (mid_key1,vww) = mid_key1; 243.36/197.10 243.36/197.10 glueBal2Mid_key2 yzy yzz = glueBal2Mid_key20 yzy yzz (glueBal2Vv3 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_key20 yzy yzz (mid_key2,vwx) = mid_key2; 243.36/197.10 243.36/197.10 glueBal2Vv2 yzy yzz = findMax yzz; 243.36/197.10 243.36/197.10 glueBal2Vv3 yzy yzz = findMin yzy; 243.36/197.10 243.36/197.10 glueBal3 fm1 EmptyFM = fm1; 243.36/197.10 glueBal3 xxu xxv = glueBal2 xxu xxv; 243.36/197.10 243.36/197.10 glueBal4 EmptyFM fm2 = fm2; 243.36/197.10 glueBal4 xxx xxy = glueBal3 xxx xxy; 243.36/197.10 243.36/197.10 glueVBal :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.10 glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2; 243.36/197.10 glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM; 243.36/197.10 glueVBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.10 243.36/197.10 glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal3GlueVBal2 vxz vyu vyv vyw vyx vwz vxu vxv vxw vxx vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * glueVBal3Size_l vxz vyu vyv vyw vyx vwz vxu vxv vxw vxx < glueVBal3Size_r vxz vyu vyv vyw vyx vwz vxu vxv vxw vxx); 243.36/197.10 243.36/197.10 glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = glueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.10 243.36/197.10 glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx)); 243.36/197.10 glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx otherwise; 243.36/197.10 243.36/197.10 glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx; 243.36/197.10 glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw < glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw); 243.36/197.10 243.36/197.10 glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zyy zyz zzu zzv zzw); 243.36/197.10 243.36/197.10 glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zxz zyu zyv zyw zyx); 243.36/197.10 243.36/197.10 glueVBal4 fm1 EmptyFM = fm1; 243.36/197.10 glueVBal4 xyw xyx = glueVBal3 xyw xyx; 243.36/197.10 243.36/197.10 glueVBal5 EmptyFM fm2 = fm2; 243.36/197.10 glueVBal5 xyz xzu = glueVBal4 xyz xzu; 243.36/197.10 243.36/197.10 intersectFM :: Ord a => FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.10 intersectFM fm1 fm2 = intersectFM_C intersectFM0 fm1 fm2; 243.36/197.10 243.36/197.10 intersectFM0 left right = right; 243.36/197.10 243.36/197.10 intersectFM_C :: Ord c => (d -> b -> a) -> FiniteMap c d -> FiniteMap c b -> FiniteMap c a; 243.36/197.10 intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM; 243.36/197.10 intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2; 243.36/197.10 intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right); 243.36/197.10 243.36/197.10 intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2IntersectFM_C1 fm1 split_key combiner fm1 split_key elt2 wyx left right (Maybe.isJust (intersectFM_C2Maybe_elt1 fm1 split_key)); 243.36/197.10 243.36/197.10 intersectFM_C2Elt1 zww zwx = intersectFM_C2Elt10 zww zwx (intersectFM_C2Vv1 zww zwx); 243.36/197.10 243.36/197.10 intersectFM_C2Elt10 zww zwx (Just elt1) = elt1; 243.36/197.10 243.36/197.10 intersectFM_C2Gts zww zwx = splitGT zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right); 243.36/197.10 243.36/197.10 intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner (intersectFM_C2Elt1 zww zwx) elt2) (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right); 243.36/197.10 intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right False = intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right otherwise; 243.36/197.10 243.36/197.10 intersectFM_C2Lts zww zwx = splitLT zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C2Maybe_elt1 zww zwx = lookupFM zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C2Vv1 zww zwx = intersectFM_C2Maybe_elt1 zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C3 combiner EmptyFM fm2 = emptyFM; 243.36/197.10 intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx; 243.36/197.10 243.36/197.10 intersectFM_C4 combiner fm1 EmptyFM = emptyFM; 243.36/197.10 intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv; 243.36/197.10 243.36/197.10 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 243.36/197.10 lookupFM EmptyFM key = lookupFM4 EmptyFM key; 243.36/197.10 lookupFM (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find; 243.36/197.10 243.36/197.10 lookupFM0 key elt vyz fm_l fm_r key_to_find True = Just elt; 243.36/197.10 243.36/197.10 lookupFM1 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 243.36/197.10 lookupFM1 key elt vyz fm_l fm_r key_to_find False = lookupFM0 key elt vyz fm_l fm_r key_to_find otherwise; 243.36/197.10 243.36/197.10 lookupFM2 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 243.36/197.10 lookupFM2 key elt vyz fm_l fm_r key_to_find False = lookupFM1 key elt vyz fm_l fm_r key_to_find (key_to_find > key); 243.36/197.10 243.36/197.10 lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM2 key elt vyz fm_l fm_r key_to_find (key_to_find < key); 243.36/197.10 243.36/197.10 lookupFM4 EmptyFM key = Nothing; 243.36/197.10 lookupFM4 xzx xzy = lookupFM3 xzx xzy; 243.36/197.10 243.36/197.10 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.10 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < 2); 243.36/197.10 243.36/197.10 mkBalBranch6Double_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 zvy zvz fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr); 243.36/197.10 243.36/197.10 mkBalBranch6Double_R zvy zvz zwu zwv (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 zvy zvz fm_lrr fm_r); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr True = mkBalBranch6Double_L zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr True = mkBalBranch6Single_L zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr False = mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr otherwise; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr True = mkBalBranch6Double_R zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr True = mkBalBranch6Single_R zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr False = mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr otherwise; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R fm_L; 243.36/197.10 mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R otherwise; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R fm_R; 243.36/197.10 mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_l zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_r zvy zvz zwu zwv); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_r zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_l zvy zvz zwu zwv); 243.36/197.10 243.36/197.10 mkBalBranch6Single_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 zvy zvz fm_l fm_rl) fm_rr; 243.36/197.10 243.36/197.10 mkBalBranch6Single_R zvy zvz zwu zwv (Branch key_l elt_l wvx fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 zvy zvz fm_lr fm_r); 243.36/197.10 243.36/197.10 mkBalBranch6Size_l zvy zvz zwu zwv = sizeFM zwv; 243.36/197.10 243.36/197.10 mkBalBranch6Size_r zvy zvz zwu zwv = sizeFM zwu; 243.36/197.10 243.36/197.10 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.10 mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l; 243.36/197.10 243.36/197.10 mkBranchBalance_ok zwy zwz zxu = True; 243.36/197.10 243.36/197.10 mkBranchLeft_ok zwy zwz zxu = mkBranchLeft_ok0 zwy zwz zxu zxu zwz zxu; 243.36/197.10 243.36/197.10 mkBranchLeft_ok0 zwy zwz zxu fm_l key EmptyFM = True; 243.36/197.10 mkBranchLeft_ok0 zwy zwz zxu fm_l key (Branch left_key vuu vuv vuw vux) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 243.36/197.10 243.36/197.10 mkBranchLeft_ok0Biggest_left_key zzy = fst (findMax zzy); 243.36/197.10 243.36/197.10 mkBranchLeft_size zwy zwz zxu = sizeFM zxu; 243.36/197.10 243.36/197.10 mkBranchResult zxv zxw zxx zxy = Branch zxv zxw (mkBranchUnbox zxx zxv zxy (1 + mkBranchLeft_size zxx zxv zxy + mkBranchRight_size zxx zxv zxy)) zxy zxx; 243.36/197.10 243.36/197.10 mkBranchRight_ok zwy zwz zxu = mkBranchRight_ok0 zwy zwz zxu zwy zwz zwy; 243.36/197.10 243.36/197.10 mkBranchRight_ok0 zwy zwz zxu fm_r key EmptyFM = True; 243.36/197.10 mkBranchRight_ok0 zwy zwz zxu fm_r key (Branch right_key vuy vuz vvu vvv) = key < mkBranchRight_ok0Smallest_right_key fm_r; 243.36/197.10 243.36/197.10 mkBranchRight_ok0Smallest_right_key zzx = fst (findMin zzx); 243.36/197.10 243.36/197.10 mkBranchRight_size zwy zwz zxu = sizeFM zwy; 243.36/197.10 243.36/197.10 mkBranchUnbox :: Ord a => -> (FiniteMap a b) ( -> a ( -> (FiniteMap a b) (Int -> Int))); 243.36/197.10 mkBranchUnbox zwy zwz zxu x = x; 243.36/197.10 243.36/197.10 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.10 mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 243.36/197.10 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 243.36/197.10 mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.10 243.36/197.10 mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch3MkVBalBranch2 vzv vzw vzx vzy vzz wuv wuw wux wuy wuz key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * mkVBalBranch3Size_l vzv vzw vzx vzy vzz wuv wuw wux wuy wuz < mkVBalBranch3Size_r vzv vzw vzx vzy vzz wuv wuw wux wuy wuz); 243.36/197.10 243.36/197.10 mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBranch 13 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.10 243.36/197.10 mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz)); 243.36/197.10 mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz otherwise; 243.36/197.10 243.36/197.10 mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz; 243.36/197.10 mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx < mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx); 243.36/197.10 243.36/197.10 mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuu zuv zuw zux zuy); 243.36/197.10 243.36/197.10 mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuz zvu zvv zvw zvx); 243.36/197.10 243.36/197.10 mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 243.36/197.10 mkVBalBranch4 yvw yvx yvy yvz = mkVBalBranch3 yvw yvx yvy yvz; 243.36/197.10 243.36/197.10 mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 243.36/197.10 mkVBalBranch5 ywv yww ywx ywy = mkVBalBranch4 ywv yww ywx ywy; 243.36/197.10 243.36/197.10 sIZE_RATIO :: Int; 243.36/197.10 sIZE_RATIO = 5; 243.36/197.10 243.36/197.10 sizeFM :: FiniteMap b a -> Int; 243.36/197.10 sizeFM EmptyFM = 0; 243.36/197.10 sizeFM (Branch wxx wxy size wxz wyu) = size; 243.36/197.10 243.36/197.10 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 243.36/197.10 splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 243.36/197.10 splitGT (Branch key elt wvw fm_l fm_r) split_key = splitGT3 (Branch key elt wvw fm_l fm_r) split_key; 243.36/197.10 243.36/197.10 splitGT0 key elt wvw fm_l fm_r split_key True = fm_r; 243.36/197.10 243.36/197.10 splitGT1 key elt wvw fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 243.36/197.10 splitGT1 key elt wvw fm_l fm_r split_key False = splitGT0 key elt wvw fm_l fm_r split_key otherwise; 243.36/197.10 243.36/197.10 splitGT2 key elt wvw fm_l fm_r split_key True = splitGT fm_r split_key; 243.36/197.10 splitGT2 key elt wvw fm_l fm_r split_key False = splitGT1 key elt wvw fm_l fm_r split_key (split_key < key); 243.36/197.10 243.36/197.10 splitGT3 (Branch key elt wvw fm_l fm_r) split_key = splitGT2 key elt wvw fm_l fm_r split_key (split_key > key); 243.36/197.10 243.36/197.10 splitGT4 EmptyFM split_key = emptyFM; 243.36/197.10 splitGT4 yxv yxw = splitGT3 yxv yxw; 243.36/197.10 243.36/197.10 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 243.36/197.10 splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 243.36/197.10 splitLT (Branch key elt zz fm_l fm_r) split_key = splitLT3 (Branch key elt zz fm_l fm_r) split_key; 243.36/197.10 243.36/197.10 splitLT0 key elt zz fm_l fm_r split_key True = fm_l; 243.36/197.10 243.36/197.10 splitLT1 key elt zz fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 243.36/197.10 splitLT1 key elt zz fm_l fm_r split_key False = splitLT0 key elt zz fm_l fm_r split_key otherwise; 243.36/197.10 243.36/197.10 splitLT2 key elt zz fm_l fm_r split_key True = splitLT fm_l split_key; 243.36/197.10 splitLT2 key elt zz fm_l fm_r split_key False = splitLT1 key elt zz fm_l fm_r split_key (split_key > key); 243.36/197.10 243.36/197.10 splitLT3 (Branch key elt zz fm_l fm_r) split_key = splitLT2 key elt zz fm_l fm_r split_key (split_key < key); 243.36/197.10 243.36/197.10 splitLT4 EmptyFM split_key = emptyFM; 243.36/197.10 splitLT4 xwx xwy = splitLT3 xwx xwy; 243.36/197.10 243.36/197.10 unitFM :: b -> a -> FiniteMap b a; 243.36/197.10 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 243.36/197.10 243.36/197.10 } 243.36/197.10 module Maybe where { 243.36/197.10 import qualified FiniteMap; 243.36/197.10 import qualified Main; 243.36/197.10 import qualified Prelude; 243.36/197.10 isJust :: Maybe a -> Bool; 243.36/197.10 isJust Nothing = False; 243.36/197.10 isJust wzw = True; 243.36/197.10 243.36/197.10 } 243.36/197.10 module Main where { 243.36/197.10 import qualified FiniteMap; 243.36/197.10 import qualified Maybe; 243.36/197.10 import qualified Prelude; 243.36/197.10 } 243.36/197.10 243.36/197.10 ---------------------------------------- 243.36/197.10 243.36/197.10 (13) NumRed (SOUND) 243.36/197.10 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 243.36/197.10 ---------------------------------------- 243.36/197.10 243.36/197.10 (14) 243.36/197.10 Obligation: 243.36/197.10 mainModule Main 243.36/197.10 module FiniteMap where { 243.36/197.10 import qualified Main; 243.36/197.10 import qualified Maybe; 243.36/197.10 import qualified Prelude; 243.36/197.10 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 243.36/197.10 243.36/197.10 instance (Eq a, Eq b) => Eq FiniteMap b a where { 243.36/197.10 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 243.36/197.10 } 243.36/197.10 addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b; 243.36/197.10 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 243.36/197.10 243.36/197.10 addToFM0 old new = new; 243.36/197.10 243.36/197.10 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 243.36/197.10 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 243.36/197.10 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; 243.36/197.10 243.36/197.10 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; 243.36/197.10 243.36/197.10 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); 243.36/197.10 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; 243.36/197.10 243.36/197.10 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; 243.36/197.10 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); 243.36/197.10 243.36/197.10 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); 243.36/197.10 243.36/197.10 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 243.36/197.10 addToFM_C4 yuv yuw yux yuy = addToFM_C3 yuv yuw yux yuy; 243.36/197.10 243.36/197.10 deleteMax :: Ord a => FiniteMap a b -> FiniteMap a b; 243.36/197.10 deleteMax (Branch key elt wvu fm_l EmptyFM) = fm_l; 243.36/197.10 deleteMax (Branch key elt wvv fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); 243.36/197.10 243.36/197.10 deleteMin :: Ord a => FiniteMap a b -> FiniteMap a b; 243.36/197.10 deleteMin (Branch key elt wyv EmptyFM fm_r) = fm_r; 243.36/197.10 deleteMin (Branch key elt wyw fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; 243.36/197.10 243.36/197.10 emptyFM :: FiniteMap b a; 243.36/197.10 emptyFM = EmptyFM; 243.36/197.10 243.36/197.10 findMax :: FiniteMap a b -> (a,b); 243.36/197.10 findMax (Branch key elt vvw vvx EmptyFM) = (key,elt); 243.36/197.10 findMax (Branch key elt vvy vvz fm_r) = findMax fm_r; 243.36/197.10 243.36/197.10 findMin :: FiniteMap b a -> (b,a); 243.36/197.10 findMin (Branch key elt wyy EmptyFM wyz) = (key,elt); 243.36/197.10 findMin (Branch key elt wzu fm_l wzv) = findMin fm_l; 243.36/197.10 243.36/197.10 fmToList :: FiniteMap a b -> [(a,b)]; 243.36/197.10 fmToList fm = foldFM fmToList0 [] fm; 243.36/197.10 243.36/197.10 fmToList0 key elt rest = (key,elt) : rest; 243.36/197.10 243.36/197.10 foldFM :: (a -> b -> c -> c) -> c -> FiniteMap a b -> c; 243.36/197.10 foldFM k z EmptyFM = z; 243.36/197.10 foldFM k z (Branch key elt vyy fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 243.36/197.10 243.36/197.10 glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.10 glueBal EmptyFM fm2 = glueBal4 EmptyFM fm2; 243.36/197.10 glueBal fm1 EmptyFM = glueBal3 fm1 EmptyFM; 243.36/197.10 glueBal fm1 fm2 = glueBal2 fm1 fm2; 243.36/197.10 243.36/197.10 glueBal2 fm1 fm2 = glueBal2GlueBal1 fm2 fm1 fm1 fm2 (sizeFM fm2 > sizeFM fm1); 243.36/197.10 243.36/197.10 glueBal2GlueBal0 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key1 yzy yzz) (glueBal2Mid_elt1 yzy yzz) (deleteMax fm1) fm2; 243.36/197.10 243.36/197.10 glueBal2GlueBal1 yzy yzz fm1 fm2 True = mkBalBranch (glueBal2Mid_key2 yzy yzz) (glueBal2Mid_elt2 yzy yzz) fm1 (deleteMin fm2); 243.36/197.10 glueBal2GlueBal1 yzy yzz fm1 fm2 False = glueBal2GlueBal0 yzy yzz fm1 fm2 otherwise; 243.36/197.10 243.36/197.10 glueBal2Mid_elt1 yzy yzz = glueBal2Mid_elt10 yzy yzz (glueBal2Vv2 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_elt10 yzy yzz (vwv,mid_elt1) = mid_elt1; 243.36/197.10 243.36/197.10 glueBal2Mid_elt2 yzy yzz = glueBal2Mid_elt20 yzy yzz (glueBal2Vv3 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_elt20 yzy yzz (vwu,mid_elt2) = mid_elt2; 243.36/197.10 243.36/197.10 glueBal2Mid_key1 yzy yzz = glueBal2Mid_key10 yzy yzz (glueBal2Vv2 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_key10 yzy yzz (mid_key1,vww) = mid_key1; 243.36/197.10 243.36/197.10 glueBal2Mid_key2 yzy yzz = glueBal2Mid_key20 yzy yzz (glueBal2Vv3 yzy yzz); 243.36/197.10 243.36/197.10 glueBal2Mid_key20 yzy yzz (mid_key2,vwx) = mid_key2; 243.36/197.10 243.36/197.10 glueBal2Vv2 yzy yzz = findMax yzz; 243.36/197.10 243.36/197.10 glueBal2Vv3 yzy yzz = findMin yzy; 243.36/197.10 243.36/197.10 glueBal3 fm1 EmptyFM = fm1; 243.36/197.10 glueBal3 xxu xxv = glueBal2 xxu xxv; 243.36/197.10 243.36/197.10 glueBal4 EmptyFM fm2 = fm2; 243.36/197.10 glueBal4 xxx xxy = glueBal3 xxx xxy; 243.36/197.10 243.36/197.10 glueVBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.10 glueVBal EmptyFM fm2 = glueVBal5 EmptyFM fm2; 243.36/197.10 glueVBal fm1 EmptyFM = glueVBal4 fm1 EmptyFM; 243.36/197.10 glueVBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.10 243.36/197.10 glueVBal3 (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx) = glueVBal3GlueVBal2 vxz vyu vyv vyw vyx vwz vxu vxv vxw vxx vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * glueVBal3Size_l vxz vyu vyv vyw vyx vwz vxu vxv vxw vxx < glueVBal3Size_r vxz vyu vyv vyw vyx vwz vxu vxv vxw vxx); 243.36/197.10 243.36/197.10 glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = glueBal (Branch vwz vxu vxv vxw vxx) (Branch vxz vyu vyv vyw vyx); 243.36/197.10 243.36/197.10 glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vwz vxu vxw (glueVBal vxx (Branch vxz vyu vyv vyw vyx)); 243.36/197.10 glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal3GlueVBal0 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx otherwise; 243.36/197.10 243.36/197.10 glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx True = mkBalBranch vxz vyu (glueVBal (Branch vwz vxu vxv vxw vxx) vyw) vyx; 243.36/197.10 glueVBal3GlueVBal2 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx False = glueVBal3GlueVBal1 zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw vwz vxu vxv vxw vxx vxz vyu vyv vyw vyx (sIZE_RATIO * glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw < glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw); 243.36/197.10 243.36/197.10 glueVBal3Size_l zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zyy zyz zzu zzv zzw); 243.36/197.10 243.36/197.10 glueVBal3Size_r zxz zyu zyv zyw zyx zyy zyz zzu zzv zzw = sizeFM (Branch zxz zyu zyv zyw zyx); 243.36/197.10 243.36/197.10 glueVBal4 fm1 EmptyFM = fm1; 243.36/197.10 glueVBal4 xyw xyx = glueVBal3 xyw xyx; 243.36/197.10 243.36/197.10 glueVBal5 EmptyFM fm2 = fm2; 243.36/197.10 glueVBal5 xyz xzu = glueVBal4 xyz xzu; 243.36/197.10 243.36/197.10 intersectFM :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 243.36/197.10 intersectFM fm1 fm2 = intersectFM_C intersectFM0 fm1 fm2; 243.36/197.10 243.36/197.10 intersectFM0 left right = right; 243.36/197.10 243.36/197.10 intersectFM_C :: Ord c => (b -> d -> a) -> FiniteMap c b -> FiniteMap c d -> FiniteMap c a; 243.36/197.10 intersectFM_C combiner fm1 EmptyFM = intersectFM_C4 combiner fm1 EmptyFM; 243.36/197.10 intersectFM_C combiner EmptyFM fm2 = intersectFM_C3 combiner EmptyFM fm2; 243.36/197.10 intersectFM_C combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right); 243.36/197.10 243.36/197.10 intersectFM_C2 combiner fm1 (Branch split_key elt2 wyx left right) = intersectFM_C2IntersectFM_C1 fm1 split_key combiner fm1 split_key elt2 wyx left right (Maybe.isJust (intersectFM_C2Maybe_elt1 fm1 split_key)); 243.36/197.10 243.36/197.10 intersectFM_C2Elt1 zww zwx = intersectFM_C2Elt10 zww zwx (intersectFM_C2Vv1 zww zwx); 243.36/197.10 243.36/197.10 intersectFM_C2Elt10 zww zwx (Just elt1) = elt1; 243.36/197.10 243.36/197.10 intersectFM_C2Gts zww zwx = splitGT zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right True = glueVBal (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right); 243.36/197.10 243.36/197.10 intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right True = mkVBalBranch split_key (combiner (intersectFM_C2Elt1 zww zwx) elt2) (intersectFM_C combiner (intersectFM_C2Lts zww zwx) left) (intersectFM_C combiner (intersectFM_C2Gts zww zwx) right); 243.36/197.10 intersectFM_C2IntersectFM_C1 zww zwx combiner fm1 split_key elt2 wyx left right False = intersectFM_C2IntersectFM_C0 zww zwx combiner fm1 split_key elt2 wyx left right otherwise; 243.36/197.10 243.36/197.10 intersectFM_C2Lts zww zwx = splitLT zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C2Maybe_elt1 zww zwx = lookupFM zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C2Vv1 zww zwx = intersectFM_C2Maybe_elt1 zww zwx; 243.36/197.10 243.36/197.10 intersectFM_C3 combiner EmptyFM fm2 = emptyFM; 243.36/197.10 intersectFM_C3 yyv yyw yyx = intersectFM_C2 yyv yyw yyx; 243.36/197.10 243.36/197.10 intersectFM_C4 combiner fm1 EmptyFM = emptyFM; 243.36/197.10 intersectFM_C4 yyz yzu yzv = intersectFM_C3 yyz yzu yzv; 243.36/197.10 243.36/197.10 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 243.36/197.10 lookupFM EmptyFM key = lookupFM4 EmptyFM key; 243.36/197.10 lookupFM (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find; 243.36/197.10 243.36/197.10 lookupFM0 key elt vyz fm_l fm_r key_to_find True = Just elt; 243.36/197.10 243.36/197.10 lookupFM1 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 243.36/197.10 lookupFM1 key elt vyz fm_l fm_r key_to_find False = lookupFM0 key elt vyz fm_l fm_r key_to_find otherwise; 243.36/197.10 243.36/197.10 lookupFM2 key elt vyz fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 243.36/197.10 lookupFM2 key elt vyz fm_l fm_r key_to_find False = lookupFM1 key elt vyz fm_l fm_r key_to_find (key_to_find > key); 243.36/197.10 243.36/197.10 lookupFM3 (Branch key elt vyz fm_l fm_r) key_to_find = lookupFM2 key elt vyz fm_l fm_r key_to_find (key_to_find < key); 243.36/197.10 243.36/197.10 lookupFM4 EmptyFM key = Nothing; 243.36/197.10 lookupFM4 xzx xzy = lookupFM3 xzx xzy; 243.36/197.10 243.36/197.10 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.10 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_R fm_L key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_R fm_L + mkBalBranch6Size_r key elt fm_R fm_L < Pos (Succ (Succ Zero))); 243.36/197.10 243.36/197.10 mkBalBranch6Double_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wwx (Branch key_rl elt_rl wwy 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))))))) zvy zvz fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr); 243.36/197.10 243.36/197.10 mkBalBranch6Double_R zvy zvz zwu zwv (Branch key_l elt_l wvy fm_ll (Branch key_lr elt_lr wvz 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))))))))))))) zvy zvz fm_lrr fm_r); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr True = mkBalBranch6Double_L zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr True = mkBalBranch6Single_L zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr False = mkBalBranch6MkBalBranch00 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr otherwise; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch02 zvy zvz zwu zwv fm_L fm_R (Branch wwz wxu wxv fm_rl fm_rr) = mkBalBranch6MkBalBranch01 zvy zvz zwu zwv fm_L fm_R wwz wxu wxv fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr True = mkBalBranch6Double_R zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr True = mkBalBranch6Single_R zvy zvz zwu zwv fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr False = mkBalBranch6MkBalBranch10 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr otherwise; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch12 zvy zvz zwu zwv fm_L fm_R (Branch wwu wwv www fm_ll fm_lr) = mkBalBranch6MkBalBranch11 zvy zvz zwu zwv fm_L fm_R wwu wwv www fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 zvy zvz zwu zwv fm_L fm_R fm_L; 243.36/197.10 mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 zvy zvz zwu zwv key elt fm_L fm_R otherwise; 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 zvy zvz zwu zwv fm_L fm_R fm_R; 243.36/197.10 mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_l zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_r zvy zvz zwu zwv); 243.36/197.10 243.36/197.10 mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R; 243.36/197.10 mkBalBranch6MkBalBranch5 zvy zvz zwu zwv key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 zvy zvz zwu zwv key elt fm_L fm_R (mkBalBranch6Size_r zvy zvz zwu zwv > sIZE_RATIO * mkBalBranch6Size_l zvy zvz zwu zwv); 243.36/197.10 243.36/197.10 mkBalBranch6Single_L zvy zvz zwu zwv fm_l (Branch key_r elt_r wxw fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) zvy zvz fm_l fm_rl) fm_rr; 243.36/197.10 243.36/197.10 mkBalBranch6Single_R zvy zvz zwu zwv (Branch key_l elt_l wvx 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)))))))))) zvy zvz fm_lr fm_r); 243.36/197.10 243.36/197.10 mkBalBranch6Size_l zvy zvz zwu zwv = sizeFM zwv; 243.36/197.10 243.36/197.10 mkBalBranch6Size_r zvy zvz zwu zwv = sizeFM zwu; 243.36/197.10 243.36/197.10 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.10 mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l; 243.36/197.10 243.36/197.10 mkBranchBalance_ok zwy zwz zxu = True; 243.36/197.10 243.36/197.10 mkBranchLeft_ok zwy zwz zxu = mkBranchLeft_ok0 zwy zwz zxu zxu zwz zxu; 243.36/197.10 243.36/197.10 mkBranchLeft_ok0 zwy zwz zxu fm_l key EmptyFM = True; 243.36/197.10 mkBranchLeft_ok0 zwy zwz zxu fm_l key (Branch left_key vuu vuv vuw vux) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 243.36/197.10 243.36/197.10 mkBranchLeft_ok0Biggest_left_key zzy = fst (findMax zzy); 243.36/197.10 243.36/197.10 mkBranchLeft_size zwy zwz zxu = sizeFM zxu; 243.36/197.10 243.36/197.10 mkBranchResult zxv zxw zxx zxy = Branch zxv zxw (mkBranchUnbox zxx zxv zxy (Pos (Succ Zero) + mkBranchLeft_size zxx zxv zxy + mkBranchRight_size zxx zxv zxy)) zxy zxx; 243.36/197.10 243.36/197.10 mkBranchRight_ok zwy zwz zxu = mkBranchRight_ok0 zwy zwz zxu zwy zwz zwy; 243.36/197.10 243.36/197.10 mkBranchRight_ok0 zwy zwz zxu fm_r key EmptyFM = True; 243.36/197.10 mkBranchRight_ok0 zwy zwz zxu fm_r key (Branch right_key vuy vuz vvu vvv) = key < mkBranchRight_ok0Smallest_right_key fm_r; 243.36/197.10 243.36/197.10 mkBranchRight_ok0Smallest_right_key zzx = fst (findMin zzx); 243.36/197.10 243.36/197.10 mkBranchRight_size zwy zwz zxu = sizeFM zwy; 243.36/197.10 243.36/197.10 mkBranchUnbox :: Ord a => -> (FiniteMap a b) ( -> a ( -> (FiniteMap a b) (Int -> Int))); 243.36/197.10 mkBranchUnbox zwy zwz zxu x = x; 243.36/197.10 243.36/197.10 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 243.36/197.10 mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 243.36/197.10 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 243.36/197.10 mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.10 243.36/197.10 mkVBalBranch3 key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz) = mkVBalBranch3MkVBalBranch2 vzv vzw vzx vzy vzz wuv wuw wux wuy wuz key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * mkVBalBranch3Size_l vzv vzw vzx vzy vzz wuv wuw wux wuy wuz < mkVBalBranch3Size_r vzv vzw vzx vzy vzz wuv wuw wux wuy wuz); 243.36/197.10 243.36/197.10 mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))) key elt (Branch vzv vzw vzx vzy vzz) (Branch wuv wuw wux wuy wuz); 243.36/197.10 243.36/197.10 mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch vzv vzw vzy (mkVBalBranch key elt vzz (Branch wuv wuw wux wuy wuz)); 243.36/197.10 mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch3MkVBalBranch0 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz otherwise; 243.36/197.10 243.36/197.10 mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz True = mkBalBranch wuv wuw (mkVBalBranch key elt (Branch vzv vzw vzx vzy vzz) wuy) wuz; 243.36/197.10 mkVBalBranch3MkVBalBranch2 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz False = mkVBalBranch3MkVBalBranch1 zuu zuv zuw zux zuy zuz zvu zvv zvw zvx key elt vzv vzw vzx vzy vzz wuv wuw wux wuy wuz (sIZE_RATIO * mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx < mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx); 243.36/197.10 243.36/197.10 mkVBalBranch3Size_l zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuu zuv zuw zux zuy); 243.36/197.10 243.36/197.10 mkVBalBranch3Size_r zuu zuv zuw zux zuy zuz zvu zvv zvw zvx = sizeFM (Branch zuz zvu zvv zvw zvx); 243.36/197.10 243.36/197.10 mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 243.36/197.10 mkVBalBranch4 yvw yvx yvy yvz = mkVBalBranch3 yvw yvx yvy yvz; 243.36/197.10 243.36/197.10 mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 243.36/197.10 mkVBalBranch5 ywv yww ywx ywy = mkVBalBranch4 ywv yww ywx ywy; 243.36/197.10 243.36/197.10 sIZE_RATIO :: Int; 243.36/197.10 sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero))))); 243.36/197.10 243.36/197.10 sizeFM :: FiniteMap b a -> Int; 243.36/197.10 sizeFM EmptyFM = Pos Zero; 243.36/197.10 sizeFM (Branch wxx wxy size wxz wyu) = size; 243.36/197.10 243.36/197.10 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 243.36/197.10 splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 243.36/197.10 splitGT (Branch key elt wvw fm_l fm_r) split_key = splitGT3 (Branch key elt wvw fm_l fm_r) split_key; 243.36/197.10 243.36/197.10 splitGT0 key elt wvw fm_l fm_r split_key True = fm_r; 243.36/197.10 243.36/197.10 splitGT1 key elt wvw fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 243.36/197.10 splitGT1 key elt wvw fm_l fm_r split_key False = splitGT0 key elt wvw fm_l fm_r split_key otherwise; 243.36/197.10 243.36/197.10 splitGT2 key elt wvw fm_l fm_r split_key True = splitGT fm_r split_key; 243.36/197.10 splitGT2 key elt wvw fm_l fm_r split_key False = splitGT1 key elt wvw fm_l fm_r split_key (split_key < key); 243.36/197.10 243.36/197.10 splitGT3 (Branch key elt wvw fm_l fm_r) split_key = splitGT2 key elt wvw fm_l fm_r split_key (split_key > key); 243.36/197.10 243.36/197.10 splitGT4 EmptyFM split_key = emptyFM; 243.36/197.10 splitGT4 yxv yxw = splitGT3 yxv yxw; 243.36/197.10 243.36/197.10 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 243.36/197.10 splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 243.36/197.10 splitLT (Branch key elt zz fm_l fm_r) split_key = splitLT3 (Branch key elt zz fm_l fm_r) split_key; 243.36/197.10 243.36/197.10 splitLT0 key elt zz fm_l fm_r split_key True = fm_l; 243.36/197.10 243.36/197.10 splitLT1 key elt zz fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 243.36/197.10 splitLT1 key elt zz fm_l fm_r split_key False = splitLT0 key elt zz fm_l fm_r split_key otherwise; 243.36/197.10 243.36/197.10 splitLT2 key elt zz fm_l fm_r split_key True = splitLT fm_l split_key; 243.36/197.10 splitLT2 key elt zz fm_l fm_r split_key False = splitLT1 key elt zz fm_l fm_r split_key (split_key > key); 243.36/197.10 243.36/197.10 splitLT3 (Branch key elt zz fm_l fm_r) split_key = splitLT2 key elt zz fm_l fm_r split_key (split_key < key); 243.36/197.10 243.36/197.10 splitLT4 EmptyFM split_key = emptyFM; 243.36/197.10 splitLT4 xwx xwy = splitLT3 xwx xwy; 243.36/197.10 243.36/197.10 unitFM :: b -> a -> FiniteMap b a; 243.36/197.10 unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM; 243.36/197.10 243.36/197.10 } 243.36/197.10 module Maybe where { 243.36/197.10 import qualified FiniteMap; 243.36/197.10 import qualified Main; 243.36/197.10 import qualified Prelude; 243.36/197.10 isJust :: Maybe a -> Bool; 243.36/197.10 isJust Nothing = False; 243.36/197.10 isJust wzw = True; 243.36/197.10 243.36/197.10 } 243.36/197.10 module Main where { 243.36/197.10 import qualified FiniteMap; 243.36/197.10 import qualified Maybe; 243.36/197.10 import qualified Prelude; 243.36/197.10 } 243.47/197.17 EOF