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