156.22/122.54 MAYBE 158.92/123.31 proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs 158.92/123.31 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 158.92/123.31 158.92/123.31 158.92/123.31 H-Termination with start terms of the given HASKELL could not be shown: 158.92/123.31 158.92/123.31 (0) HASKELL 158.92/123.31 (1) LR [EQUIVALENT, 0 ms] 158.92/123.31 (2) HASKELL 158.92/123.31 (3) CR [EQUIVALENT, 0 ms] 158.92/123.31 (4) HASKELL 158.92/123.31 (5) IFR [EQUIVALENT, 0 ms] 158.92/123.31 (6) HASKELL 158.92/123.31 (7) BR [EQUIVALENT, 0 ms] 158.92/123.31 (8) HASKELL 158.92/123.31 (9) COR [EQUIVALENT, 0 ms] 158.92/123.31 (10) HASKELL 158.92/123.31 (11) LetRed [EQUIVALENT, 0 ms] 158.92/123.31 (12) HASKELL 158.92/123.31 (13) NumRed [SOUND, 14 ms] 158.92/123.31 (14) HASKELL 158.92/123.31 158.92/123.31 158.92/123.31 ---------------------------------------- 158.92/123.31 158.92/123.31 (0) 158.92/123.31 Obligation: 158.92/123.31 mainModule Main 158.92/123.31 module FiniteMap where { 158.92/123.31 import qualified Main; 158.92/123.31 import qualified Maybe; 158.92/123.31 import qualified Prelude; 158.92/123.31 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 158.92/123.31 158.92/123.31 instance (Eq a, Eq b) => Eq FiniteMap a b where { 158.92/123.31 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 158.92/123.31 } 158.92/123.31 addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b; 158.92/123.31 addToFM fm key elt = addToFM_C (\old new ->new) fm key elt; 158.92/123.31 158.92/123.31 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 158.92/123.31 addToFM_C combiner EmptyFM key elt = unitFM key elt; 158.92/123.31 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 158.92/123.31 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 158.92/123.31 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 158.92/123.31 158.92/123.31 emptyFM :: FiniteMap a b; 158.92/123.31 emptyFM = EmptyFM; 158.92/123.31 158.92/123.31 findMax :: FiniteMap b a -> (b,a); 158.92/123.31 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 158.92/123.31 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 158.92/123.31 158.92/123.31 findMin :: FiniteMap b a -> (b,a); 158.92/123.31 findMin (Branch key elt _ EmptyFM _) = (key,elt); 158.92/123.31 findMin (Branch key elt _ fm_l _) = findMin fm_l; 158.92/123.31 158.92/123.31 fmToList :: FiniteMap a b -> [(a,b)]; 158.92/123.31 fmToList fm = foldFM (\key elt rest ->(key,elt) : rest) [] fm; 158.92/123.31 158.92/123.31 foldFM :: (a -> b -> c -> c) -> c -> FiniteMap a b -> c; 158.92/123.31 foldFM k z EmptyFM = z; 158.92/123.31 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 158.92/123.31 158.92/123.31 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 158.92/123.31 lookupFM EmptyFM key = Nothing; 158.92/123.31 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 158.92/123.31 | key_to_find > key = lookupFM fm_r key_to_find 158.92/123.31 | otherwise = Just elt; 158.92/123.31 158.92/123.31 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 158.92/123.31 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 158.92/123.31 | size_r > sIZE_RATIO * size_l = case fm_R of { 158.92/123.31 Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R 158.92/123.31 | otherwise -> double_L fm_L fm_R; 158.92/123.31 } 158.92/123.31 | size_l > sIZE_RATIO * size_r = case fm_L of { 158.92/123.31 Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R 158.92/123.31 | otherwise -> double_R fm_L fm_R; 158.92/123.31 } 158.92/123.31 | otherwise = mkBranch 2 key elt fm_L fm_R where { 158.92/123.31 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); 158.92/123.31 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); 158.92/123.31 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; 158.92/123.31 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); 158.92/123.31 size_l = sizeFM fm_L; 158.92/123.31 size_r = sizeFM fm_R; 158.92/123.31 }; 158.92/123.31 158.92/123.31 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 158.92/123.31 mkBranch which key elt fm_l fm_r = let { 158.92/123.31 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 158.92/123.31 } in result where { 158.92/123.31 balance_ok = True; 158.92/123.31 left_ok = case fm_l of { 158.92/123.31 EmptyFM-> True; 158.92/123.31 Branch left_key _ _ _ _-> let { 158.92/123.31 biggest_left_key = fst (findMax fm_l); 158.92/123.31 } in biggest_left_key < key; 158.92/123.31 } ; 158.92/123.31 left_size = sizeFM fm_l; 158.92/123.31 right_ok = case fm_r of { 158.92/123.31 EmptyFM-> True; 158.92/123.31 Branch right_key _ _ _ _-> let { 158.92/123.31 smallest_right_key = fst (findMin fm_r); 158.92/123.31 } in key < smallest_right_key; 158.92/123.31 } ; 158.92/123.31 right_size = sizeFM fm_r; 158.92/123.31 unbox :: Int -> Int; 158.92/123.31 unbox x = x; 158.92/123.31 }; 158.92/123.31 158.92/123.31 mkVBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 158.92/123.31 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 158.92/123.31 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 158.92/123.31 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 158.92/123.31 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 158.92/123.31 | otherwise = mkBranch 13 key elt fm_l fm_r where { 158.92/123.31 size_l = sizeFM fm_l; 158.92/123.31 size_r = sizeFM fm_r; 158.92/123.31 }; 158.92/123.31 158.92/123.31 plusFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 158.92/123.31 plusFM_C combiner EmptyFM fm2 = fm2; 158.92/123.31 plusFM_C combiner fm1 EmptyFM = fm1; 158.92/123.31 plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 158.92/123.31 gts = splitGT fm1 split_key; 158.92/123.31 lts = splitLT fm1 split_key; 158.92/123.31 new_elt = case lookupFM fm1 split_key of { 158.92/123.31 Nothing-> elt2; 158.92/123.31 Just elt1-> combiner elt1 elt2; 158.92/123.31 } ; 158.92/123.31 }; 158.92/123.31 158.92/123.31 sIZE_RATIO :: Int; 158.92/123.31 sIZE_RATIO = 5; 158.92/123.31 158.92/123.31 sizeFM :: FiniteMap b a -> Int; 158.92/123.31 sizeFM EmptyFM = 0; 158.92/123.31 sizeFM (Branch _ _ size _ _) = size; 158.92/123.31 158.92/123.31 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 158.92/123.31 splitGT EmptyFM split_key = emptyFM; 158.92/123.31 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 158.92/123.31 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 158.92/123.31 | otherwise = fm_r; 158.92/123.31 158.92/123.31 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 158.92/123.31 splitLT EmptyFM split_key = emptyFM; 158.92/123.31 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 158.92/123.31 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 158.92/123.31 | otherwise = fm_l; 158.92/123.31 158.92/123.31 unitFM :: b -> a -> FiniteMap b a; 158.92/123.31 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 158.92/123.31 158.92/123.31 } 158.92/123.31 module Maybe where { 158.92/123.31 import qualified FiniteMap; 158.92/123.31 import qualified Main; 158.92/123.31 import qualified Prelude; 158.92/123.31 } 158.92/123.31 module Main where { 158.92/123.31 import qualified FiniteMap; 158.92/123.31 import qualified Maybe; 158.92/123.31 import qualified Prelude; 158.92/123.31 } 158.92/123.31 158.92/123.31 ---------------------------------------- 158.92/123.31 158.92/123.31 (1) LR (EQUIVALENT) 158.92/123.31 Lambda Reductions: 158.92/123.31 The following Lambda expression 158.92/123.31 "\oldnew->new" 158.92/123.31 is transformed to 158.92/123.31 "addToFM0 old new = new; 158.92/123.31 " 158.92/123.31 The following Lambda expression 158.92/123.31 "\keyeltrest->(key,elt) : rest" 158.92/123.31 is transformed to 158.92/123.31 "fmToList0 key elt rest = (key,elt) : rest; 158.92/123.31 " 158.92/123.31 158.92/123.31 ---------------------------------------- 158.92/123.31 158.92/123.31 (2) 158.92/123.31 Obligation: 158.92/123.31 mainModule Main 158.92/123.31 module FiniteMap where { 158.92/123.31 import qualified Main; 158.92/123.31 import qualified Maybe; 158.92/123.31 import qualified Prelude; 158.92/123.31 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 158.92/123.31 158.92/123.31 instance (Eq a, Eq b) => Eq FiniteMap a b where { 158.92/123.31 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 158.92/123.31 } 158.92/123.31 addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b; 158.92/123.31 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 158.92/123.31 158.92/123.31 addToFM0 old new = new; 158.92/123.31 158.92/123.31 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 158.92/123.31 addToFM_C combiner EmptyFM key elt = unitFM key elt; 158.92/123.31 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 158.92/123.31 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 158.92/123.31 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 158.92/123.31 158.92/123.31 emptyFM :: FiniteMap b a; 158.92/123.31 emptyFM = EmptyFM; 158.92/123.31 158.92/123.31 findMax :: FiniteMap a b -> (a,b); 158.92/123.31 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 158.92/123.31 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 158.92/123.31 158.92/123.31 findMin :: FiniteMap b a -> (b,a); 158.92/123.31 findMin (Branch key elt _ EmptyFM _) = (key,elt); 158.92/123.31 findMin (Branch key elt _ fm_l _) = findMin fm_l; 158.92/123.31 158.92/123.31 fmToList :: FiniteMap b a -> [(b,a)]; 158.92/123.31 fmToList fm = foldFM fmToList0 [] fm; 158.92/123.31 158.92/123.31 fmToList0 key elt rest = (key,elt) : rest; 158.92/123.31 158.92/123.31 foldFM :: (a -> b -> c -> c) -> c -> FiniteMap a b -> c; 158.92/123.31 foldFM k z EmptyFM = z; 158.92/123.31 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 158.92/123.32 158.92/123.32 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 158.92/123.32 lookupFM EmptyFM key = Nothing; 158.92/123.32 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 158.92/123.32 | key_to_find > key = lookupFM fm_r key_to_find 158.92/123.32 | otherwise = Just elt; 158.92/123.32 158.92/123.32 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 158.92/123.32 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 158.92/123.32 | size_r > sIZE_RATIO * size_l = case fm_R of { 158.92/123.32 Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R 158.92/123.32 | otherwise -> double_L fm_L fm_R; 158.92/123.32 } 158.92/123.32 | size_l > sIZE_RATIO * size_r = case fm_L of { 158.92/123.32 Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R 158.92/123.32 | otherwise -> double_R fm_L fm_R; 158.92/123.32 } 158.92/123.32 | otherwise = mkBranch 2 key elt fm_L fm_R where { 158.92/123.32 double_L fm_l (Branch key_r elt_r _ (Branch key_rl elt_rl _ fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 key elt fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr); 158.92/123.32 double_R (Branch key_l elt_l _ fm_ll (Branch key_lr elt_lr _ fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 key elt fm_lrr fm_r); 158.92/123.32 single_L fm_l (Branch key_r elt_r _ fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 158.92/123.32 single_R (Branch key_l elt_l _ fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 158.92/123.32 size_l = sizeFM fm_L; 158.92/123.32 size_r = sizeFM fm_R; 158.92/123.32 }; 158.92/123.32 158.92/123.32 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 158.92/123.32 mkBranch which key elt fm_l fm_r = let { 158.92/123.32 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 158.92/123.32 } in result where { 158.92/123.32 balance_ok = True; 158.92/123.32 left_ok = case fm_l of { 158.92/123.32 EmptyFM-> True; 158.92/123.32 Branch left_key _ _ _ _-> let { 158.92/123.32 biggest_left_key = fst (findMax fm_l); 158.92/123.32 } in biggest_left_key < key; 158.92/123.32 } ; 158.92/123.32 left_size = sizeFM fm_l; 158.92/123.32 right_ok = case fm_r of { 158.92/123.32 EmptyFM-> True; 158.92/123.32 Branch right_key _ _ _ _-> let { 158.92/123.32 smallest_right_key = fst (findMin fm_r); 158.92/123.32 } in key < smallest_right_key; 158.92/123.32 } ; 158.92/123.32 right_size = sizeFM fm_r; 158.92/123.32 unbox :: Int -> Int; 158.92/123.32 unbox x = x; 158.92/123.32 }; 158.92/123.32 158.92/123.32 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 158.92/123.32 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 158.92/123.32 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 158.92/123.32 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 158.92/123.32 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 158.92/123.32 | otherwise = mkBranch 13 key elt fm_l fm_r where { 158.92/123.32 size_l = sizeFM fm_l; 158.92/123.32 size_r = sizeFM fm_r; 158.92/123.32 }; 158.92/123.32 158.92/123.32 plusFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 158.92/123.32 plusFM_C combiner EmptyFM fm2 = fm2; 158.92/123.32 plusFM_C combiner fm1 EmptyFM = fm1; 158.92/123.32 plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 158.92/123.32 gts = splitGT fm1 split_key; 158.92/123.32 lts = splitLT fm1 split_key; 158.92/123.32 new_elt = case lookupFM fm1 split_key of { 158.92/123.32 Nothing-> elt2; 158.92/123.32 Just elt1-> combiner elt1 elt2; 158.92/123.32 } ; 158.92/123.32 }; 158.92/123.32 158.92/123.32 sIZE_RATIO :: Int; 158.92/123.32 sIZE_RATIO = 5; 158.92/123.32 158.92/123.32 sizeFM :: FiniteMap b a -> Int; 158.92/123.32 sizeFM EmptyFM = 0; 158.92/123.32 sizeFM (Branch _ _ size _ _) = size; 158.92/123.32 158.92/123.32 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 158.92/123.32 splitGT EmptyFM split_key = emptyFM; 158.92/123.32 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 158.92/123.32 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 158.92/123.32 | otherwise = fm_r; 158.92/123.32 158.92/123.32 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 158.92/123.32 splitLT EmptyFM split_key = emptyFM; 158.92/123.32 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 158.92/123.32 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 158.92/123.32 | otherwise = fm_l; 158.92/123.32 158.92/123.32 unitFM :: b -> a -> FiniteMap b a; 158.92/123.32 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 158.92/123.32 158.92/123.32 } 158.92/123.32 module Maybe where { 158.92/123.32 import qualified FiniteMap; 158.92/123.32 import qualified Main; 158.92/123.32 import qualified Prelude; 158.92/123.32 } 158.92/123.32 module Main where { 158.92/123.32 import qualified FiniteMap; 158.92/123.32 import qualified Maybe; 158.92/123.32 import qualified Prelude; 158.92/123.32 } 158.92/123.32 158.92/123.32 ---------------------------------------- 158.92/123.32 158.92/123.32 (3) CR (EQUIVALENT) 158.92/123.32 Case Reductions: 158.92/123.32 The following Case expression 158.92/123.32 "case compare x y of { 158.92/123.32 EQ -> o; 158.92/123.32 LT -> LT; 158.92/123.32 GT -> GT} 158.92/123.32 " 158.92/123.32 is transformed to 158.92/123.32 "primCompAux0 o EQ = o; 158.92/123.32 primCompAux0 o LT = LT; 158.92/123.32 primCompAux0 o GT = GT; 158.92/123.32 " 158.92/123.32 The following Case expression 158.92/123.32 "case lookupFM fm1 split_key of { 158.92/123.32 Nothing -> elt2; 158.92/123.32 Just elt1 -> combiner elt1 elt2} 158.92/123.32 " 158.92/123.32 is transformed to 158.92/123.32 "new_elt0 elt2 combiner Nothing = elt2; 158.92/123.32 new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2; 158.92/123.32 " 158.92/123.32 The following Case expression 158.92/123.32 "case fm_r of { 158.92/123.32 EmptyFM -> True; 158.92/123.32 Branch right_key _ _ _ _ -> let { 158.92/123.32 smallest_right_key = fst (findMin fm_r); 158.92/123.32 } in key < smallest_right_key} 158.92/123.32 " 158.92/123.32 is transformed to 158.92/123.32 "right_ok0 fm_r key EmptyFM = True; 158.92/123.32 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 158.92/123.32 smallest_right_key = fst (findMin fm_r); 158.92/123.32 } in key < smallest_right_key; 158.92/123.32 " 158.92/123.32 The following Case expression 158.92/123.32 "case fm_l of { 158.92/123.32 EmptyFM -> True; 158.92/123.32 Branch left_key _ _ _ _ -> let { 158.92/123.32 biggest_left_key = fst (findMax fm_l); 158.92/123.32 } in biggest_left_key < key} 158.92/123.32 " 158.92/123.32 is transformed to 158.92/123.32 "left_ok0 fm_l key EmptyFM = True; 158.92/123.32 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 158.92/123.32 biggest_left_key = fst (findMax fm_l); 158.92/123.32 } in biggest_left_key < key; 158.92/123.32 " 158.92/123.32 The following Case expression 158.92/123.32 "case fm_R of { 158.92/123.32 Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R} 158.92/123.32 " 158.92/123.32 is transformed to 158.92/123.32 "mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R; 158.92/123.32 " 158.92/123.32 The following Case expression 158.92/123.32 "case fm_L of { 158.92/123.32 Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R} 158.92/123.32 " 158.92/123.32 is transformed to 158.92/123.32 "mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R; 158.92/123.32 " 158.92/123.32 158.92/123.32 ---------------------------------------- 158.92/123.32 158.92/123.32 (4) 158.92/123.32 Obligation: 158.92/123.32 mainModule Main 158.92/123.32 module FiniteMap where { 158.92/123.32 import qualified Main; 158.92/123.32 import qualified Maybe; 158.92/123.32 import qualified Prelude; 158.92/123.32 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 158.92/123.32 158.92/123.32 instance (Eq a, Eq b) => Eq FiniteMap a b where { 158.92/123.32 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 158.92/123.32 } 158.92/123.32 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 158.92/123.32 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 158.92/123.32 158.92/123.32 addToFM0 old new = new; 158.92/123.32 158.92/123.32 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 158.92/123.32 addToFM_C combiner EmptyFM key elt = unitFM key elt; 158.92/123.32 addToFM_C combiner (Branch key elt size fm_l fm_r) new_key new_elt | new_key < key = mkBalBranch key elt (addToFM_C combiner fm_l new_key new_elt) fm_r 158.92/123.32 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 158.92/123.32 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 158.92/123.32 158.92/123.32 emptyFM :: FiniteMap b a; 158.92/123.32 emptyFM = EmptyFM; 158.92/123.32 158.92/123.32 findMax :: FiniteMap a b -> (a,b); 158.92/123.32 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 158.92/123.32 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 158.92/123.32 158.92/123.32 findMin :: FiniteMap a b -> (a,b); 158.92/123.32 findMin (Branch key elt _ EmptyFM _) = (key,elt); 158.92/123.32 findMin (Branch key elt _ fm_l _) = findMin fm_l; 158.92/123.32 158.92/123.32 fmToList :: FiniteMap a b -> [(a,b)]; 158.92/123.32 fmToList fm = foldFM fmToList0 [] fm; 158.92/123.32 158.92/123.32 fmToList0 key elt rest = (key,elt) : rest; 158.92/123.32 158.92/123.32 foldFM :: (c -> b -> a -> a) -> a -> FiniteMap c b -> a; 158.92/123.32 foldFM k z EmptyFM = z; 158.92/123.32 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 158.92/123.32 158.92/123.32 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 158.92/123.32 lookupFM EmptyFM key = Nothing; 158.92/123.32 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 158.92/123.32 | key_to_find > key = lookupFM fm_r key_to_find 158.92/123.32 | otherwise = Just elt; 158.92/123.32 158.92/123.32 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 158.92/123.32 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 158.92/123.32 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 158.92/123.32 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 159.31/123.42 | otherwise = mkBranch 2 key elt fm_L fm_R where { 159.31/123.42 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); 159.31/123.42 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); 159.31/123.42 mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 159.31/123.42 | otherwise = double_L fm_L fm_R; 159.31/123.42 mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 159.31/123.42 | otherwise = double_R fm_L fm_R; 159.31/123.42 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; 159.31/123.42 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); 159.31/123.42 size_l = sizeFM fm_L; 159.31/123.42 size_r = sizeFM fm_R; 159.31/123.42 }; 159.31/123.42 159.31/123.42 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.31/123.42 mkBranch which key elt fm_l fm_r = let { 159.31/123.42 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 159.31/123.42 } in result where { 159.31/123.42 balance_ok = True; 159.31/123.42 left_ok = left_ok0 fm_l key fm_l; 159.31/123.42 left_ok0 fm_l key EmptyFM = True; 159.31/123.42 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 159.31/123.42 biggest_left_key = fst (findMax fm_l); 159.31/123.42 } in biggest_left_key < key; 159.31/123.42 left_size = sizeFM fm_l; 159.31/123.42 right_ok = right_ok0 fm_r key fm_r; 159.31/123.42 right_ok0 fm_r key EmptyFM = True; 159.31/123.42 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 159.31/123.42 smallest_right_key = fst (findMin fm_r); 159.31/123.42 } in key < smallest_right_key; 159.31/123.42 right_size = sizeFM fm_r; 159.31/123.42 unbox :: Int -> Int; 159.31/123.42 unbox x = x; 159.31/123.42 }; 159.31/123.42 159.31/123.42 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.31/123.42 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 159.31/123.42 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 159.31/123.42 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 159.31/123.43 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 159.31/123.43 | otherwise = mkBranch 13 key elt fm_l fm_r where { 159.31/123.43 size_l = sizeFM fm_l; 159.31/123.43 size_r = sizeFM fm_r; 159.31/123.43 }; 159.31/123.43 159.31/123.43 plusFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.31/123.43 plusFM_C combiner EmptyFM fm2 = fm2; 159.31/123.43 plusFM_C combiner fm1 EmptyFM = fm1; 159.31/123.43 plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 159.31/123.43 gts = splitGT fm1 split_key; 159.31/123.43 lts = splitLT fm1 split_key; 159.31/123.43 new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key); 159.31/123.43 new_elt0 elt2 combiner Nothing = elt2; 159.31/123.43 new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2; 159.31/123.43 }; 159.31/123.43 159.31/123.43 sIZE_RATIO :: Int; 159.31/123.43 sIZE_RATIO = 5; 159.31/123.43 159.31/123.43 sizeFM :: FiniteMap a b -> Int; 159.31/123.43 sizeFM EmptyFM = 0; 159.31/123.43 sizeFM (Branch _ _ size _ _) = size; 159.31/123.43 159.31/123.43 splitGT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 159.31/123.43 splitGT EmptyFM split_key = emptyFM; 159.31/123.43 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 159.31/123.43 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 159.31/123.43 | otherwise = fm_r; 159.31/123.43 159.31/123.43 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 159.31/123.43 splitLT EmptyFM split_key = emptyFM; 159.31/123.43 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 159.31/123.43 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 159.31/123.43 | otherwise = fm_l; 159.31/123.43 159.31/123.43 unitFM :: a -> b -> FiniteMap a b; 159.31/123.43 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 159.31/123.43 159.31/123.43 } 159.31/123.43 module Maybe where { 159.31/123.43 import qualified FiniteMap; 159.31/123.43 import qualified Main; 159.31/123.43 import qualified Prelude; 159.31/123.43 } 159.31/123.43 module Main where { 159.31/123.43 import qualified FiniteMap; 159.31/123.43 import qualified Maybe; 159.31/123.43 import qualified Prelude; 159.31/123.43 } 159.31/123.43 159.31/123.43 ---------------------------------------- 159.31/123.43 159.31/123.43 (5) IFR (EQUIVALENT) 159.31/123.43 If Reductions: 159.31/123.43 The following If expression 159.31/123.43 "if primGEqNatS x y then Succ (primDivNatS (primMinusNatS x y) (Succ y)) else Zero" 159.31/123.43 is transformed to 159.31/123.43 "primDivNatS0 x y True = Succ (primDivNatS (primMinusNatS x y) (Succ y)); 159.31/123.43 primDivNatS0 x y False = Zero; 159.31/123.43 " 159.31/123.43 The following If expression 159.31/123.43 "if primGEqNatS x y then primModNatS (primMinusNatS x y) (Succ y) else Succ x" 159.31/123.43 is transformed to 159.31/123.43 "primModNatS0 x y True = primModNatS (primMinusNatS x y) (Succ y); 159.31/123.43 primModNatS0 x y False = Succ x; 159.31/123.43 " 159.31/123.43 159.31/123.43 ---------------------------------------- 159.31/123.43 159.31/123.43 (6) 159.31/123.43 Obligation: 159.31/123.43 mainModule Main 159.31/123.43 module FiniteMap where { 159.31/123.43 import qualified Main; 159.31/123.43 import qualified Maybe; 159.31/123.43 import qualified Prelude; 159.31/123.43 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 159.31/123.43 159.31/123.43 instance (Eq a, Eq b) => Eq FiniteMap a b where { 159.31/123.43 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 159.31/123.43 } 159.31/123.43 addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b; 159.31/123.43 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 159.31/123.43 159.31/123.43 addToFM0 old new = new; 159.31/123.43 159.31/123.43 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 159.31/123.43 addToFM_C combiner EmptyFM key elt = unitFM key elt; 159.31/123.43 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 159.31/123.43 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 159.31/123.43 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 159.31/123.43 159.31/123.43 emptyFM :: FiniteMap b a; 159.31/123.43 emptyFM = EmptyFM; 159.31/123.43 159.31/123.43 findMax :: FiniteMap a b -> (a,b); 159.31/123.43 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 159.31/123.43 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 159.31/123.43 159.31/123.43 findMin :: FiniteMap b a -> (b,a); 159.31/123.43 findMin (Branch key elt _ EmptyFM _) = (key,elt); 159.31/123.43 findMin (Branch key elt _ fm_l _) = findMin fm_l; 159.31/123.43 159.31/123.43 fmToList :: FiniteMap b a -> [(b,a)]; 159.31/123.43 fmToList fm = foldFM fmToList0 [] fm; 159.31/123.43 159.31/123.43 fmToList0 key elt rest = (key,elt) : rest; 159.31/123.43 159.31/123.43 foldFM :: (b -> c -> a -> a) -> a -> FiniteMap b c -> a; 159.31/123.43 foldFM k z EmptyFM = z; 159.31/123.43 foldFM k z (Branch key elt _ fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 159.31/123.43 159.31/123.43 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 159.31/123.43 lookupFM EmptyFM key = Nothing; 159.31/123.43 lookupFM (Branch key elt _ fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 159.31/123.43 | key_to_find > key = lookupFM fm_r key_to_find 159.31/123.43 | otherwise = Just elt; 159.31/123.43 159.31/123.43 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.31/123.43 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 159.31/123.43 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 159.31/123.43 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 159.31/123.43 | otherwise = mkBranch 2 key elt fm_L fm_R where { 159.31/123.43 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); 159.31/123.43 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); 159.31/123.43 mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 159.31/123.43 | otherwise = double_L fm_L fm_R; 159.31/123.43 mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 159.31/123.43 | otherwise = double_R fm_L fm_R; 159.31/123.43 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; 159.31/123.43 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); 159.31/123.43 size_l = sizeFM fm_L; 159.31/123.43 size_r = sizeFM fm_R; 159.31/123.43 }; 159.31/123.43 159.31/123.43 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.31/123.43 mkBranch which key elt fm_l fm_r = let { 159.31/123.43 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 159.31/123.43 } in result where { 159.31/123.43 balance_ok = True; 159.31/123.43 left_ok = left_ok0 fm_l key fm_l; 159.31/123.43 left_ok0 fm_l key EmptyFM = True; 159.31/123.43 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 159.31/123.43 biggest_left_key = fst (findMax fm_l); 159.31/123.43 } in biggest_left_key < key; 159.31/123.43 left_size = sizeFM fm_l; 159.31/123.43 right_ok = right_ok0 fm_r key fm_r; 159.31/123.43 right_ok0 fm_r key EmptyFM = True; 159.31/123.43 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 159.31/123.43 smallest_right_key = fst (findMin fm_r); 159.31/123.43 } in key < smallest_right_key; 159.31/123.43 right_size = sizeFM fm_r; 159.31/123.43 unbox :: Int -> Int; 159.31/123.43 unbox x = x; 159.31/123.43 }; 159.31/123.43 159.31/123.43 mkVBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.31/123.43 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 159.31/123.43 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 159.31/123.43 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 159.31/123.43 | sIZE_RATIO * size_r < size_l = mkBalBranch key_l elt_l fm_ll (mkVBalBranch key elt fm_lr fm_r) 159.31/123.43 | otherwise = mkBranch 13 key elt fm_l fm_r where { 159.31/123.43 size_l = sizeFM fm_l; 159.31/123.43 size_r = sizeFM fm_r; 159.31/123.43 }; 159.31/123.43 159.31/123.43 plusFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.31/123.43 plusFM_C combiner EmptyFM fm2 = fm2; 159.31/123.43 plusFM_C combiner fm1 EmptyFM = fm1; 159.31/123.43 plusFM_C combiner fm1 (Branch split_key elt2 _ left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 159.31/123.43 gts = splitGT fm1 split_key; 159.31/123.43 lts = splitLT fm1 split_key; 159.31/123.43 new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key); 159.31/123.43 new_elt0 elt2 combiner Nothing = elt2; 159.31/123.43 new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2; 159.31/123.43 }; 159.31/123.43 159.31/123.43 sIZE_RATIO :: Int; 159.31/123.43 sIZE_RATIO = 5; 159.31/123.43 159.31/123.43 sizeFM :: FiniteMap a b -> Int; 159.31/123.43 sizeFM EmptyFM = 0; 159.31/123.43 sizeFM (Branch _ _ size _ _) = size; 159.31/123.43 159.31/123.43 splitGT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 159.31/123.43 splitGT EmptyFM split_key = emptyFM; 159.31/123.43 splitGT (Branch key elt _ fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 159.31/123.43 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 159.31/123.43 | otherwise = fm_r; 159.31/123.43 159.31/123.43 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 159.31/123.43 splitLT EmptyFM split_key = emptyFM; 159.31/123.43 splitLT (Branch key elt _ fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 159.31/123.43 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 159.31/123.43 | otherwise = fm_l; 159.31/123.43 159.31/123.43 unitFM :: a -> b -> FiniteMap a b; 159.31/123.43 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 159.31/123.43 159.31/123.43 } 159.31/123.43 module Maybe where { 159.31/123.43 import qualified FiniteMap; 159.31/123.43 import qualified Main; 159.31/123.43 import qualified Prelude; 159.31/123.43 } 159.31/123.43 module Main where { 159.31/123.43 import qualified FiniteMap; 159.31/123.43 import qualified Maybe; 159.31/123.43 import qualified Prelude; 159.31/123.43 } 159.31/123.43 159.31/123.43 ---------------------------------------- 159.31/123.43 159.31/123.43 (7) BR (EQUIVALENT) 159.31/123.43 Replaced joker patterns by fresh variables and removed binding patterns. 159.31/123.43 159.31/123.43 Binding Reductions: 159.31/123.43 The bind variable of the following binding Pattern 159.31/123.43 "fm_l@(Branch vuv vuw vux vuy vuz)" 159.31/123.43 is replaced by the following term 159.31/123.43 "Branch vuv vuw vux vuy vuz" 159.31/123.43 The bind variable of the following binding Pattern 159.31/123.43 "fm_r@(Branch vvv vvw vvx vvy vvz)" 159.31/123.43 is replaced by the following term 159.31/123.43 "Branch vvv vvw vvx vvy vvz" 159.31/123.43 159.31/123.43 ---------------------------------------- 159.31/123.43 159.31/123.43 (8) 159.31/123.43 Obligation: 159.31/123.43 mainModule Main 159.31/123.43 module FiniteMap where { 159.31/123.43 import qualified Main; 159.31/123.43 import qualified Maybe; 159.31/123.43 import qualified Prelude; 159.31/123.43 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 159.31/123.43 159.31/123.43 instance (Eq a, Eq b) => Eq FiniteMap a b where { 159.31/123.43 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 159.31/123.43 } 159.31/123.43 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 159.31/123.43 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 159.31/123.43 159.31/123.43 addToFM0 old new = new; 159.31/123.43 159.31/123.43 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 159.31/123.43 addToFM_C combiner EmptyFM key elt = unitFM key elt; 159.31/123.43 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 159.31/123.43 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 159.31/123.43 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 159.31/123.43 159.31/123.43 emptyFM :: FiniteMap b a; 159.31/123.43 emptyFM = EmptyFM; 159.31/123.43 159.31/123.43 findMax :: FiniteMap b a -> (b,a); 159.31/123.43 findMax (Branch key elt vxy vxz EmptyFM) = (key,elt); 159.31/123.43 findMax (Branch key elt vyu vyv fm_r) = findMax fm_r; 159.31/123.43 159.31/123.43 findMin :: FiniteMap b a -> (b,a); 159.31/123.43 findMin (Branch key elt wvw EmptyFM wvx) = (key,elt); 159.31/123.43 findMin (Branch key elt wvy fm_l wvz) = findMin fm_l; 159.31/123.43 159.31/123.43 fmToList :: FiniteMap b a -> [(b,a)]; 159.31/123.43 fmToList fm = foldFM fmToList0 [] fm; 159.31/123.43 159.31/123.43 fmToList0 key elt rest = (key,elt) : rest; 159.31/123.43 159.31/123.43 foldFM :: (c -> a -> b -> b) -> b -> FiniteMap c a -> b; 159.31/123.43 foldFM k z EmptyFM = z; 159.31/123.43 foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 159.31/123.43 159.31/123.43 lookupFM :: Ord b => FiniteMap b a -> b -> Maybe a; 159.31/123.43 lookupFM EmptyFM key = Nothing; 159.31/123.43 lookupFM (Branch key elt wvv fm_l fm_r) key_to_find | key_to_find < key = lookupFM fm_l key_to_find 159.31/123.43 | key_to_find > key = lookupFM fm_r key_to_find 159.31/123.43 | otherwise = Just elt; 159.31/123.43 159.31/123.43 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.31/123.43 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 159.31/123.43 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 159.31/123.43 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 159.31/123.43 | otherwise = mkBranch 2 key elt fm_L fm_R where { 159.31/123.43 double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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); 159.31/123.43 double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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); 159.31/123.43 mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 159.31/123.43 | otherwise = double_L fm_L fm_R; 159.31/123.43 mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 159.31/123.43 | otherwise = double_R fm_L fm_R; 159.31/123.43 single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 159.31/123.43 single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 159.31/123.43 size_l = sizeFM fm_L; 159.31/123.43 size_r = sizeFM fm_R; 159.31/123.43 }; 159.31/123.43 159.31/123.43 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.31/123.43 mkBranch which key elt fm_l fm_r = let { 159.31/123.43 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 159.31/123.43 } in result where { 159.31/123.43 balance_ok = True; 159.31/123.43 left_ok = left_ok0 fm_l key fm_l; 159.31/123.43 left_ok0 fm_l key EmptyFM = True; 159.31/123.43 left_ok0 fm_l key (Branch left_key vww vwx vwy vwz) = let { 159.31/123.43 biggest_left_key = fst (findMax fm_l); 159.31/123.43 } in biggest_left_key < key; 159.31/123.43 left_size = sizeFM fm_l; 159.31/123.43 right_ok = right_ok0 fm_r key fm_r; 159.31/123.43 right_ok0 fm_r key EmptyFM = True; 159.31/123.43 right_ok0 fm_r key (Branch right_key vxu vxv vxw vxx) = let { 159.31/123.43 smallest_right_key = fst (findMin fm_r); 159.31/123.43 } in key < smallest_right_key; 159.31/123.43 right_size = sizeFM fm_r; 159.31/123.43 unbox :: Int -> Int; 159.31/123.43 unbox x = x; 159.31/123.43 }; 159.31/123.43 159.31/123.43 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.31/123.43 mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 159.31/123.43 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 159.31/123.43 mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) | sIZE_RATIO * size_l < size_r = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz 159.31/123.43 | sIZE_RATIO * size_r < size_l = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz)) 159.31/123.43 | otherwise = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) where { 159.31/123.43 size_l = sizeFM (Branch vuv vuw vux vuy vuz); 159.31/123.43 size_r = sizeFM (Branch vvv vvw vvx vvy vvz); 159.31/123.43 }; 159.31/123.43 159.31/123.43 plusFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.31/123.43 plusFM_C combiner EmptyFM fm2 = fm2; 159.31/123.43 plusFM_C combiner fm1 EmptyFM = fm1; 159.31/123.43 plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 159.31/123.43 gts = splitGT fm1 split_key; 159.31/123.43 lts = splitLT fm1 split_key; 159.31/123.43 new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key); 159.31/123.43 new_elt0 elt2 combiner Nothing = elt2; 159.31/123.43 new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2; 159.31/123.43 }; 159.31/123.43 159.31/123.43 sIZE_RATIO :: Int; 159.31/123.43 sIZE_RATIO = 5; 159.31/123.43 159.31/123.43 sizeFM :: FiniteMap a b -> Int; 159.31/123.43 sizeFM EmptyFM = 0; 159.31/123.43 sizeFM (Branch wux wuy size wuz wvu) = size; 159.31/123.43 159.31/123.43 splitGT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 159.31/123.43 splitGT EmptyFM split_key = emptyFM; 159.31/123.43 splitGT (Branch key elt vwu fm_l fm_r) split_key | split_key > key = splitGT fm_r split_key 159.96/123.54 | split_key < key = mkVBalBranch key elt (splitGT fm_l split_key) fm_r 159.96/123.54 | otherwise = fm_r; 159.96/123.54 159.96/123.54 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 159.96/123.54 splitLT EmptyFM split_key = emptyFM; 159.96/123.54 splitLT (Branch key elt vwv fm_l fm_r) split_key | split_key < key = splitLT fm_l split_key 159.96/123.54 | split_key > key = mkVBalBranch key elt fm_l (splitLT fm_r split_key) 159.96/123.54 | otherwise = fm_l; 159.96/123.54 159.96/123.54 unitFM :: a -> b -> FiniteMap a b; 159.96/123.54 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 159.96/123.54 159.96/123.54 } 159.96/123.54 module Maybe where { 159.96/123.54 import qualified FiniteMap; 159.96/123.54 import qualified Main; 159.96/123.54 import qualified Prelude; 159.96/123.54 } 159.96/123.54 module Main where { 159.96/123.54 import qualified FiniteMap; 159.96/123.54 import qualified Maybe; 159.96/123.54 import qualified Prelude; 159.96/123.54 } 159.96/123.54 159.96/123.54 ---------------------------------------- 159.96/123.54 159.96/123.54 (9) COR (EQUIVALENT) 159.96/123.54 Cond Reductions: 159.96/123.54 The following Function with conditions 159.96/123.54 "compare x y|x == yEQ|x <= yLT|otherwiseGT; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "compare x y = compare3 x y; 159.96/123.54 " 159.96/123.54 "compare0 x y True = GT; 159.96/123.54 " 159.96/123.54 "compare1 x y True = LT; 159.96/123.54 compare1 x y False = compare0 x y otherwise; 159.96/123.54 " 159.96/123.54 "compare2 x y True = EQ; 159.96/123.54 compare2 x y False = compare1 x y (x <= y); 159.96/123.54 " 159.96/123.54 "compare3 x y = compare2 x y (x == y); 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "absReal x|x >= 0x|otherwise`negate` x; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "absReal x = absReal2 x; 159.96/123.54 " 159.96/123.54 "absReal0 x True = `negate` x; 159.96/123.54 " 159.96/123.54 "absReal1 x True = x; 159.96/123.54 absReal1 x False = absReal0 x otherwise; 159.96/123.54 " 159.96/123.54 "absReal2 x = absReal1 x (x >= 0); 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "gcd' x 0 = x; 159.96/123.54 gcd' x y = gcd' y (x `rem` y); 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "gcd' x wwu = gcd'2 x wwu; 159.96/123.54 gcd' x y = gcd'0 x y; 159.96/123.54 " 159.96/123.54 "gcd'0 x y = gcd' y (x `rem` y); 159.96/123.54 " 159.96/123.54 "gcd'1 True x wwu = x; 159.96/123.54 gcd'1 wwv www wwx = gcd'0 www wwx; 159.96/123.54 " 159.96/123.54 "gcd'2 x wwu = gcd'1 (wwu == 0) x wwu; 159.96/123.54 gcd'2 wwy wwz = gcd'0 wwy wwz; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "gcd 0 0 = error []; 159.96/123.54 gcd x y = gcd' (abs x) (abs y) where { 159.96/123.54 gcd' x 0 = x; 159.96/123.54 gcd' x y = gcd' y (x `rem` y); 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "gcd wxu wxv = gcd3 wxu wxv; 159.96/123.54 gcd x y = gcd0 x y; 159.96/123.54 " 159.96/123.54 "gcd0 x y = gcd' (abs x) (abs y) where { 159.96/123.54 gcd' x wwu = gcd'2 x wwu; 159.96/123.54 gcd' x y = gcd'0 x y; 159.96/123.54 ; 159.96/123.54 gcd'0 x y = gcd' y (x `rem` y); 159.96/123.54 ; 159.96/123.54 gcd'1 True x wwu = x; 159.96/123.54 gcd'1 wwv www wwx = gcd'0 www wwx; 159.96/123.54 ; 159.96/123.54 gcd'2 x wwu = gcd'1 (wwu == 0) x wwu; 159.96/123.54 gcd'2 wwy wwz = gcd'0 wwy wwz; 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 "gcd1 True wxu wxv = error []; 159.96/123.54 gcd1 wxw wxx wxy = gcd0 wxx wxy; 159.96/123.54 " 159.96/123.54 "gcd2 True wxu wxv = gcd1 (wxv == 0) wxu wxv; 159.96/123.54 gcd2 wxz wyu wyv = gcd0 wyu wyv; 159.96/123.54 " 159.96/123.54 "gcd3 wxu wxv = gcd2 (wxu == 0) wxu wxv; 159.96/123.54 gcd3 wyw wyx = gcd0 wyw wyx; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "undefined |Falseundefined; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "undefined = undefined1; 159.96/123.54 " 159.96/123.54 "undefined0 True = undefined; 159.96/123.54 " 159.96/123.54 "undefined1 = undefined0 False; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "reduce x y|y == 0error []|otherwisex `quot` d :% (y `quot` d) where { 159.96/123.54 d = gcd x y; 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "reduce x y = reduce2 x y; 159.96/123.54 " 159.96/123.54 "reduce2 x y = reduce1 x y (y == 0) where { 159.96/123.54 d = gcd x y; 159.96/123.54 ; 159.96/123.54 reduce0 x y True = x `quot` d :% (y `quot` d); 159.96/123.54 ; 159.96/123.54 reduce1 x y True = error []; 159.96/123.54 reduce1 x y False = reduce0 x y otherwise; 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "addToFM_C combiner EmptyFM key elt = unitFM key elt; 159.96/123.54 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; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 159.96/123.54 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; 159.96/123.54 " 159.96/123.54 "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; 159.96/123.54 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); 159.96/123.54 " 159.96/123.54 "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; 159.96/123.54 " 159.96/123.54 "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); 159.96/123.54 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; 159.96/123.54 " 159.96/123.54 "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); 159.96/123.54 " 159.96/123.54 "addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 159.96/123.54 addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "mkVBalBranch key elt EmptyFM fm_r = addToFM fm_r key elt; 159.96/123.54 mkVBalBranch key elt fm_l EmptyFM = addToFM fm_l key elt; 159.96/123.54 mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz)|sIZE_RATIO * size_l < size_rmkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz|sIZE_RATIO * size_r < size_lmkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz))|otherwisemkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) where { 159.96/123.54 size_l = sizeFM (Branch vuv vuw vux vuy vuz); 159.96/123.54 ; 159.96/123.54 size_r = sizeFM (Branch vvv vvw vvx vvy vvz); 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 159.96/123.54 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 159.96/123.54 mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.54 " 159.96/123.54 "mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_l < size_r) where { 159.96/123.54 mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.54 ; 159.96/123.54 mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz)); 159.96/123.54 mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise; 159.96/123.54 ; 159.96/123.54 mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz; 159.96/123.54 mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_r < size_l); 159.96/123.54 ; 159.96/123.54 size_l = sizeFM (Branch vuv vuw vux vuy vuz); 159.96/123.54 ; 159.96/123.54 size_r = sizeFM (Branch vvv vvw vvx vvy vvz); 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 "mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 159.96/123.54 mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy; 159.96/123.54 " 159.96/123.54 "mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 159.96/123.54 mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "splitGT EmptyFM split_key = emptyFM; 159.96/123.54 splitGT (Branch key elt vwu 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; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 159.96/123.54 splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key; 159.96/123.54 " 159.96/123.54 "splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key; 159.96/123.54 splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key); 159.96/123.54 " 159.96/123.54 "splitGT0 key elt vwu fm_l fm_r split_key True = fm_r; 159.96/123.54 " 159.96/123.54 "splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 159.96/123.54 splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise; 159.96/123.54 " 159.96/123.54 "splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key); 159.96/123.54 " 159.96/123.54 "splitGT4 EmptyFM split_key = emptyFM; 159.96/123.54 splitGT4 xwu xwv = splitGT3 xwu xwv; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "splitLT EmptyFM split_key = emptyFM; 159.96/123.54 splitLT (Branch key elt vwv 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; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 159.96/123.54 splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key; 159.96/123.54 " 159.96/123.54 "splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 159.96/123.54 splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise; 159.96/123.54 " 159.96/123.54 "splitLT0 key elt vwv fm_l fm_r split_key True = fm_l; 159.96/123.54 " 159.96/123.54 "splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key; 159.96/123.54 splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key); 159.96/123.54 " 159.96/123.54 "splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key); 159.96/123.54 " 159.96/123.54 "splitLT4 EmptyFM split_key = emptyFM; 159.96/123.54 splitLT4 xwy xwz = splitLT3 xwy xwz; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr); 159.96/123.54 " 159.96/123.54 "mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R; 159.96/123.54 mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise; 159.96/123.54 " 159.96/123.54 "mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R; 159.96/123.54 " 159.96/123.54 "mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr); 159.96/123.54 " 159.96/123.54 "mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R; 159.96/123.54 " 159.96/123.54 "mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R; 159.96/123.54 mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise; 159.96/123.54 " 159.96/123.54 "mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "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 { 159.96/123.54 double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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); 159.96/123.54 ; 159.96/123.54 double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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); 159.96/123.54 ; 159.96/123.54 mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R; 159.96/123.54 ; 159.96/123.54 mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R; 159.96/123.54 ; 159.96/123.54 single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 159.96/123.54 ; 159.96/123.54 single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 159.96/123.54 ; 159.96/123.54 size_l = sizeFM fm_L; 159.96/123.54 ; 159.96/123.54 size_r = sizeFM fm_R; 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 159.96/123.54 " 159.96/123.54 "mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 159.96/123.54 double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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); 159.96/123.54 ; 159.96/123.54 double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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); 159.96/123.54 ; 159.96/123.54 mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr); 159.96/123.54 ; 159.96/123.54 mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R; 159.96/123.54 ; 159.96/123.54 mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R; 159.96/123.54 mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise; 159.96/123.54 ; 159.96/123.54 mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 159.96/123.54 ; 159.96/123.54 mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr); 159.96/123.54 ; 159.96/123.54 mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R; 159.96/123.54 ; 159.96/123.54 mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R; 159.96/123.54 mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise; 159.96/123.54 ; 159.96/123.54 mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 159.96/123.54 ; 159.96/123.54 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 159.96/123.54 ; 159.96/123.54 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 159.96/123.54 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 159.96/123.54 ; 159.96/123.54 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 159.96/123.54 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 159.96/123.54 ; 159.96/123.54 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 159.96/123.54 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 159.96/123.54 ; 159.96/123.54 single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 159.96/123.54 ; 159.96/123.54 single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 159.96/123.54 ; 159.96/123.54 size_l = sizeFM fm_L; 159.96/123.54 ; 159.96/123.54 size_r = sizeFM fm_R; 159.96/123.54 } 159.96/123.54 ; 159.96/123.54 " 159.96/123.54 The following Function with conditions 159.96/123.54 "lookupFM EmptyFM key = Nothing; 159.96/123.54 lookupFM (Branch key elt wvv 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; 159.96/123.54 " 159.96/123.54 is transformed to 159.96/123.54 "lookupFM EmptyFM key = lookupFM4 EmptyFM key; 159.96/123.54 lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find; 159.96/123.54 " 159.96/123.54 "lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 159.96/123.54 lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise; 159.96/123.54 " 159.96/123.54 "lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt; 159.96/123.54 " 159.96/123.54 "lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 159.96/123.54 lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key); 159.96/123.54 " 159.96/123.54 "lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key); 159.96/123.54 " 159.96/123.54 "lookupFM4 EmptyFM key = Nothing; 159.96/123.54 lookupFM4 xxy xxz = lookupFM3 xxy xxz; 159.96/123.54 " 159.96/123.54 159.96/123.54 ---------------------------------------- 159.96/123.54 159.96/123.54 (10) 159.96/123.54 Obligation: 159.96/123.54 mainModule Main 159.96/123.54 module FiniteMap where { 159.96/123.54 import qualified Main; 159.96/123.54 import qualified Maybe; 159.96/123.54 import qualified Prelude; 159.96/123.54 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 159.96/123.54 159.96/123.54 instance (Eq a, Eq b) => Eq FiniteMap a b where { 159.96/123.54 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 159.96/123.54 } 159.96/123.54 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 159.96/123.54 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 159.96/123.54 159.96/123.54 addToFM0 old new = new; 159.96/123.54 159.96/123.54 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 159.96/123.54 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 159.96/123.54 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; 159.96/123.54 159.96/123.54 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; 159.96/123.54 159.96/123.54 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); 159.96/123.54 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; 159.96/123.54 159.96/123.54 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; 159.96/123.54 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); 159.96/123.54 159.96/123.54 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); 159.96/123.54 159.96/123.54 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 159.96/123.54 addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx; 159.96/123.54 159.96/123.54 emptyFM :: FiniteMap a b; 159.96/123.54 emptyFM = EmptyFM; 159.96/123.54 159.96/123.54 findMax :: FiniteMap a b -> (a,b); 159.96/123.54 findMax (Branch key elt vxy vxz EmptyFM) = (key,elt); 159.96/123.54 findMax (Branch key elt vyu vyv fm_r) = findMax fm_r; 159.96/123.54 159.96/123.54 findMin :: FiniteMap a b -> (a,b); 159.96/123.54 findMin (Branch key elt wvw EmptyFM wvx) = (key,elt); 159.96/123.54 findMin (Branch key elt wvy fm_l wvz) = findMin fm_l; 159.96/123.54 159.96/123.54 fmToList :: FiniteMap b a -> [(b,a)]; 159.96/123.54 fmToList fm = foldFM fmToList0 [] fm; 159.96/123.54 159.96/123.54 fmToList0 key elt rest = (key,elt) : rest; 159.96/123.54 159.96/123.54 foldFM :: (a -> b -> c -> c) -> c -> FiniteMap a b -> c; 159.96/123.54 foldFM k z EmptyFM = z; 159.96/123.54 foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 159.96/123.54 159.96/123.54 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 159.96/123.54 lookupFM EmptyFM key = lookupFM4 EmptyFM key; 159.96/123.54 lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find; 159.96/123.54 159.96/123.54 lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt; 159.96/123.54 159.96/123.54 lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 159.96/123.54 lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise; 159.96/123.54 159.96/123.54 lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 159.96/123.54 lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key); 159.96/123.54 159.96/123.54 lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key); 159.96/123.54 159.96/123.54 lookupFM4 EmptyFM key = Nothing; 159.96/123.54 lookupFM4 xxy xxz = lookupFM3 xxy xxz; 159.96/123.54 159.96/123.54 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.96/123.54 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 159.96/123.54 159.96/123.54 mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 159.96/123.54 double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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); 159.96/123.54 double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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); 159.96/123.54 mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr); 159.96/123.54 mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R; 159.96/123.54 mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R; 159.96/123.54 mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise; 159.96/123.54 mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 159.96/123.54 mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr); 159.96/123.54 mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R; 159.96/123.54 mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R; 159.96/123.54 mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise; 159.96/123.54 mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 159.96/123.54 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 159.96/123.54 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 159.96/123.54 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 159.96/123.54 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 159.96/123.54 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 159.96/123.54 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 159.96/123.54 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 159.96/123.54 single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 159.96/123.54 single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 159.96/123.54 size_l = sizeFM fm_L; 159.96/123.54 size_r = sizeFM fm_R; 159.96/123.54 }; 159.96/123.54 159.96/123.54 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.96/123.54 mkBranch which key elt fm_l fm_r = let { 159.96/123.54 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 159.96/123.54 } in result where { 159.96/123.54 balance_ok = True; 159.96/123.54 left_ok = left_ok0 fm_l key fm_l; 159.96/123.54 left_ok0 fm_l key EmptyFM = True; 159.96/123.54 left_ok0 fm_l key (Branch left_key vww vwx vwy vwz) = let { 159.96/123.54 biggest_left_key = fst (findMax fm_l); 159.96/123.54 } in biggest_left_key < key; 159.96/123.54 left_size = sizeFM fm_l; 159.96/123.54 right_ok = right_ok0 fm_r key fm_r; 159.96/123.54 right_ok0 fm_r key EmptyFM = True; 159.96/123.54 right_ok0 fm_r key (Branch right_key vxu vxv vxw vxx) = let { 159.96/123.54 smallest_right_key = fst (findMin fm_r); 159.96/123.54 } in key < smallest_right_key; 159.96/123.54 right_size = sizeFM fm_r; 159.96/123.54 unbox :: Int -> Int; 159.96/123.54 unbox x = x; 159.96/123.54 }; 159.96/123.54 159.96/123.54 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.96/123.54 mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 159.96/123.54 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 159.96/123.54 mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.54 159.96/123.54 mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_l < size_r) where { 159.96/123.54 mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.54 mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz)); 159.96/123.54 mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise; 159.96/123.54 mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz; 159.96/123.54 mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_r < size_l); 159.96/123.54 size_l = sizeFM (Branch vuv vuw vux vuy vuz); 159.96/123.54 size_r = sizeFM (Branch vvv vvw vvx vvy vvz); 159.96/123.54 }; 159.96/123.54 159.96/123.54 mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 159.96/123.54 mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy; 159.96/123.54 159.96/123.54 mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 159.96/123.54 mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx; 159.96/123.54 159.96/123.54 plusFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.96/123.54 plusFM_C combiner EmptyFM fm2 = fm2; 159.96/123.54 plusFM_C combiner fm1 EmptyFM = fm1; 159.96/123.54 plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 159.96/123.54 gts = splitGT fm1 split_key; 159.96/123.54 lts = splitLT fm1 split_key; 159.96/123.54 new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key); 159.96/123.54 new_elt0 elt2 combiner Nothing = elt2; 159.96/123.54 new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2; 159.96/123.54 }; 159.96/123.54 159.96/123.54 sIZE_RATIO :: Int; 159.96/123.54 sIZE_RATIO = 5; 159.96/123.54 159.96/123.54 sizeFM :: FiniteMap a b -> Int; 159.96/123.54 sizeFM EmptyFM = 0; 159.96/123.54 sizeFM (Branch wux wuy size wuz wvu) = size; 159.96/123.54 159.96/123.54 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 159.96/123.54 splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 159.96/123.54 splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key; 159.96/123.54 159.96/123.54 splitGT0 key elt vwu fm_l fm_r split_key True = fm_r; 159.96/123.54 159.96/123.54 splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 159.96/123.54 splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise; 159.96/123.54 159.96/123.54 splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key; 159.96/123.54 splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key); 159.96/123.54 159.96/123.54 splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key); 159.96/123.54 159.96/123.54 splitGT4 EmptyFM split_key = emptyFM; 159.96/123.54 splitGT4 xwu xwv = splitGT3 xwu xwv; 159.96/123.54 159.96/123.54 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 159.96/123.54 splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 159.96/123.54 splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key; 159.96/123.54 159.96/123.54 splitLT0 key elt vwv fm_l fm_r split_key True = fm_l; 159.96/123.54 159.96/123.54 splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 159.96/123.54 splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise; 159.96/123.54 159.96/123.54 splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key; 159.96/123.54 splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key); 159.96/123.54 159.96/123.54 splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key); 159.96/123.54 159.96/123.54 splitLT4 EmptyFM split_key = emptyFM; 159.96/123.54 splitLT4 xwy xwz = splitLT3 xwy xwz; 159.96/123.54 159.96/123.54 unitFM :: a -> b -> FiniteMap a b; 159.96/123.54 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 159.96/123.54 159.96/123.54 } 159.96/123.54 module Maybe where { 159.96/123.54 import qualified FiniteMap; 159.96/123.54 import qualified Main; 159.96/123.54 import qualified Prelude; 159.96/123.54 } 159.96/123.54 module Main where { 159.96/123.54 import qualified FiniteMap; 159.96/123.54 import qualified Maybe; 159.96/123.54 import qualified Prelude; 159.96/123.54 } 159.96/123.54 159.96/123.54 ---------------------------------------- 159.96/123.54 159.96/123.54 (11) LetRed (EQUIVALENT) 159.96/123.54 Let/Where Reductions: 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "gcd' (abs x) (abs y) where { 159.96/123.54 gcd' x wwu = gcd'2 x wwu; 159.96/123.54 gcd' x y = gcd'0 x y; 159.96/123.54 ; 159.96/123.54 gcd'0 x y = gcd' y (x `rem` y); 159.96/123.54 ; 159.96/123.54 gcd'1 True x wwu = x; 159.96/123.54 gcd'1 wwv www wwx = gcd'0 www wwx; 159.96/123.54 ; 159.96/123.54 gcd'2 x wwu = gcd'1 (wwu == 0) x wwu; 159.96/123.54 gcd'2 wwy wwz = gcd'0 wwy wwz; 159.96/123.54 } 159.96/123.54 " 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "gcd0Gcd' x wwu = gcd0Gcd'2 x wwu; 159.96/123.54 gcd0Gcd' x y = gcd0Gcd'0 x y; 159.96/123.54 " 159.96/123.54 "gcd0Gcd'1 True x wwu = x; 159.96/123.54 gcd0Gcd'1 wwv www wwx = gcd0Gcd'0 www wwx; 159.96/123.54 " 159.96/123.54 "gcd0Gcd'0 x y = gcd0Gcd' y (x `rem` y); 159.96/123.54 " 159.96/123.54 "gcd0Gcd'2 x wwu = gcd0Gcd'1 (wwu == 0) x wwu; 159.96/123.54 gcd0Gcd'2 wwy wwz = gcd0Gcd'0 wwy wwz; 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "reduce1 x y (y == 0) where { 159.96/123.54 d = gcd x y; 159.96/123.54 ; 159.96/123.54 reduce0 x y True = x `quot` d :% (y `quot` d); 159.96/123.54 ; 159.96/123.54 reduce1 x y True = error []; 159.96/123.54 reduce1 x y False = reduce0 x y otherwise; 159.96/123.54 } 159.96/123.54 " 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "reduce2Reduce0 xyu xyv x y True = x `quot` reduce2D xyu xyv :% (y `quot` reduce2D xyu xyv); 159.96/123.54 " 159.96/123.54 "reduce2D xyu xyv = gcd xyu xyv; 159.96/123.54 " 159.96/123.54 "reduce2Reduce1 xyu xyv x y True = error []; 159.96/123.54 reduce2Reduce1 xyu xyv x y False = reduce2Reduce0 xyu xyv x y otherwise; 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 159.96/123.54 double_L fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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); 159.96/123.54 ; 159.96/123.54 double_R (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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); 159.96/123.54 ; 159.96/123.54 mkBalBranch0 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr); 159.96/123.54 ; 159.96/123.54 mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = double_L fm_L fm_R; 159.96/123.54 ; 159.96/123.54 mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr True = single_L fm_L fm_R; 159.96/123.54 mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch00 fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise; 159.96/123.54 ; 159.96/123.54 mkBalBranch02 fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch01 fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 159.96/123.54 ; 159.96/123.54 mkBalBranch1 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr); 159.96/123.54 ; 159.96/123.54 mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = double_R fm_L fm_R; 159.96/123.54 ; 159.96/123.54 mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr True = single_R fm_L fm_R; 159.96/123.54 mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch10 fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise; 159.96/123.54 ; 159.96/123.54 mkBalBranch12 fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch11 fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 159.96/123.54 ; 159.96/123.54 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 159.96/123.54 ; 159.96/123.54 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 159.96/123.54 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 159.96/123.54 ; 159.96/123.54 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 159.96/123.54 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 159.96/123.54 ; 159.96/123.54 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 159.96/123.54 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 159.96/123.54 ; 159.96/123.54 single_L fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 159.96/123.54 ; 159.96/123.54 single_R (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 159.96/123.54 ; 159.96/123.54 size_l = sizeFM fm_L; 159.96/123.54 ; 159.96/123.54 size_r = sizeFM fm_R; 159.96/123.54 } 159.96/123.54 " 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "mkBalBranch6Single_L xyw xyx xyy xyz fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 xyw xyx fm_l fm_rl) fm_rr; 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr); 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Double_R xyw xyx xyy xyz fm_L fm_R; 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr); 159.96/123.54 " 159.96/123.54 "mkBalBranch6Single_R xyw xyx xyy xyz (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 xyw xyx fm_lr fm_r); 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Single_R xyw xyx xyy xyz fm_L fm_R; 159.96/123.54 mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise; 159.96/123.54 " 159.96/123.54 "mkBalBranch6Size_l xyw xyx xyy xyz = sizeFM xyy; 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R fm_R; 159.96/123.54 mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_l xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_r xyw xyx xyy xyz); 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Double_L xyw xyx xyy xyz fm_L fm_R; 159.96/123.54 " 159.96/123.54 "mkBalBranch6Double_R xyw xyx xyy xyz (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 xyw xyx fm_lrr fm_r); 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R fm_L; 159.96/123.54 mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R otherwise; 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Single_L xyw xyx xyy xyz fm_L fm_R; 159.96/123.54 mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise; 159.96/123.54 " 159.96/123.54 "mkBalBranch6Double_L xyw xyx xyy xyz fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 xyw xyx fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr); 159.96/123.54 " 159.96/123.54 "mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 159.96/123.54 mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_r xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_l xyw xyx xyy xyz); 159.96/123.54 " 159.96/123.54 "mkBalBranch6Size_r xyw xyx xyy xyz = sizeFM xyz; 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "let { 159.96/123.54 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 159.96/123.54 } in result where { 159.96/123.54 balance_ok = True; 159.96/123.54 ; 159.96/123.54 left_ok = left_ok0 fm_l key fm_l; 159.96/123.54 ; 159.96/123.54 left_ok0 fm_l key EmptyFM = True; 159.96/123.54 left_ok0 fm_l key (Branch left_key vww vwx vwy vwz) = let { 159.96/123.54 biggest_left_key = fst (findMax fm_l); 159.96/123.54 } in biggest_left_key < key; 159.96/123.54 ; 159.96/123.54 left_size = sizeFM fm_l; 159.96/123.54 ; 159.96/123.54 right_ok = right_ok0 fm_r key fm_r; 159.96/123.54 ; 159.96/123.54 right_ok0 fm_r key EmptyFM = True; 159.96/123.54 right_ok0 fm_r key (Branch right_key vxu vxv vxw vxx) = let { 159.96/123.54 smallest_right_key = fst (findMin fm_r); 159.96/123.54 } in key < smallest_right_key; 159.96/123.54 ; 159.96/123.54 right_size = sizeFM fm_r; 159.96/123.54 ; 159.96/123.54 unbox x = x; 159.96/123.54 } 159.96/123.54 " 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "mkBranchLeft_ok0 xzu xzv xzw fm_l key EmptyFM = True; 159.96/123.54 mkBranchLeft_ok0 xzu xzv xzw fm_l key (Branch left_key vww vwx vwy vwz) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 159.96/123.54 " 159.96/123.54 "mkBranchRight_size xzu xzv xzw = sizeFM xzu; 159.96/123.54 " 159.96/123.54 "mkBranchBalance_ok xzu xzv xzw = True; 159.96/123.54 " 159.96/123.54 "mkBranchRight_ok xzu xzv xzw = mkBranchRight_ok0 xzu xzv xzw xzu xzv xzu; 159.96/123.54 " 159.96/123.54 "mkBranchUnbox xzu xzv xzw x = x; 159.96/123.54 " 159.96/123.54 "mkBranchLeft_ok xzu xzv xzw = mkBranchLeft_ok0 xzu xzv xzw xzw xzv xzw; 159.96/123.54 " 159.96/123.54 "mkBranchRight_ok0 xzu xzv xzw fm_r key EmptyFM = True; 159.96/123.54 mkBranchRight_ok0 xzu xzv xzw fm_r key (Branch right_key vxu vxv vxw vxx) = key < mkBranchRight_ok0Smallest_right_key fm_r; 159.96/123.54 " 159.96/123.54 "mkBranchLeft_size xzu xzv xzw = sizeFM xzw; 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "let { 159.96/123.54 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 159.96/123.54 } in result" 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "mkBranchResult xzx xzy xzz yuu = Branch xzx xzy (mkBranchUnbox xzz xzx yuu (1 + mkBranchLeft_size xzz xzx yuu + mkBranchRight_size xzz xzx yuu)) yuu xzz; 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "mkVBalBranch split_key new_elt (plusFM_C combiner lts left) (plusFM_C combiner gts right) where { 159.96/123.54 gts = splitGT fm1 split_key; 159.96/123.54 ; 159.96/123.54 lts = splitLT fm1 split_key; 159.96/123.54 ; 159.96/123.54 new_elt = new_elt0 elt2 combiner (lookupFM fm1 split_key); 159.96/123.54 ; 159.96/123.54 new_elt0 elt2 combiner Nothing = elt2; 159.96/123.54 new_elt0 elt2 combiner (Just elt1) = combiner elt1 elt2; 159.96/123.54 } 159.96/123.54 " 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "plusFM_CNew_elt yuv yuw yux yuy = plusFM_CNew_elt0 yuv yuw yux yuy yuv yuw (lookupFM yux yuy); 159.96/123.54 " 159.96/123.54 "plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner Nothing = elt2; 159.96/123.54 plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner (Just elt1) = combiner elt1 elt2; 159.96/123.54 " 159.96/123.54 "plusFM_CLts yuv yuw yux yuy = splitLT yux yuy; 159.96/123.54 " 159.96/123.54 "plusFM_CGts yuv yuw yux yuy = splitGT yux yuy; 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_l < size_r) where { 159.96/123.54 mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.54 ; 159.96/123.54 mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz)); 159.96/123.54 mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch0 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise; 159.96/123.54 ; 159.96/123.54 mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz; 159.96/123.54 mkVBalBranch2 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch1 key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * size_r < size_l); 159.96/123.54 ; 159.96/123.54 size_l = sizeFM (Branch vuv vuw vux vuy vuz); 159.96/123.54 ; 159.96/123.54 size_r = sizeFM (Branch vvv vvw vvx vvy vvz); 159.96/123.54 } 159.96/123.54 " 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yuz yvu yvv yvw yvx); 159.96/123.54 " 159.96/123.54 "mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.54 " 159.96/123.54 "mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz)); 159.96/123.54 mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise; 159.96/123.54 " 159.96/123.54 "mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yvy yvz ywu ywv yww); 159.96/123.54 " 159.96/123.54 "mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz; 159.96/123.54 mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww < mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww); 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "let { 159.96/123.54 biggest_left_key = fst (findMax fm_l); 159.96/123.54 } in biggest_left_key < key" 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "mkBranchLeft_ok0Biggest_left_key ywx = fst (findMax ywx); 159.96/123.54 " 159.96/123.54 The bindings of the following Let/Where expression 159.96/123.54 "let { 159.96/123.54 smallest_right_key = fst (findMin fm_r); 159.96/123.54 } in key < smallest_right_key" 159.96/123.54 are unpacked to the following functions on top level 159.96/123.54 "mkBranchRight_ok0Smallest_right_key ywy = fst (findMin ywy); 159.96/123.54 " 159.96/123.54 159.96/123.54 ---------------------------------------- 159.96/123.54 159.96/123.54 (12) 159.96/123.54 Obligation: 159.96/123.54 mainModule Main 159.96/123.54 module FiniteMap where { 159.96/123.54 import qualified Main; 159.96/123.54 import qualified Maybe; 159.96/123.54 import qualified Prelude; 159.96/123.54 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 159.96/123.54 159.96/123.54 instance (Eq a, Eq b) => Eq FiniteMap a b where { 159.96/123.54 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 159.96/123.54 } 159.96/123.54 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 159.96/123.54 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 159.96/123.54 159.96/123.54 addToFM0 old new = new; 159.96/123.54 159.96/123.54 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 159.96/123.54 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 159.96/123.54 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; 159.96/123.54 159.96/123.54 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; 159.96/123.54 159.96/123.54 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); 159.96/123.54 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; 159.96/123.54 159.96/123.54 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; 159.96/123.54 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); 159.96/123.54 159.96/123.54 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); 159.96/123.54 159.96/123.54 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 159.96/123.54 addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx; 159.96/123.54 159.96/123.54 emptyFM :: FiniteMap b a; 159.96/123.54 emptyFM = EmptyFM; 159.96/123.54 159.96/123.54 findMax :: FiniteMap a b -> (a,b); 159.96/123.54 findMax (Branch key elt vxy vxz EmptyFM) = (key,elt); 159.96/123.54 findMax (Branch key elt vyu vyv fm_r) = findMax fm_r; 159.96/123.54 159.96/123.54 findMin :: FiniteMap a b -> (a,b); 159.96/123.54 findMin (Branch key elt wvw EmptyFM wvx) = (key,elt); 159.96/123.54 findMin (Branch key elt wvy fm_l wvz) = findMin fm_l; 159.96/123.54 159.96/123.54 fmToList :: FiniteMap b a -> [(b,a)]; 159.96/123.54 fmToList fm = foldFM fmToList0 [] fm; 159.96/123.54 159.96/123.54 fmToList0 key elt rest = (key,elt) : rest; 159.96/123.54 159.96/123.54 foldFM :: (a -> c -> b -> b) -> b -> FiniteMap a c -> b; 159.96/123.55 foldFM k z EmptyFM = z; 159.96/123.55 foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 159.96/123.55 159.96/123.55 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 159.96/123.55 lookupFM EmptyFM key = lookupFM4 EmptyFM key; 159.96/123.55 lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find; 159.96/123.55 159.96/123.55 lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt; 159.96/123.55 159.96/123.55 lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 159.96/123.55 lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise; 159.96/123.55 159.96/123.55 lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 159.96/123.55 lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key); 159.96/123.55 159.96/123.55 lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key); 159.96/123.55 159.96/123.55 lookupFM4 EmptyFM key = Nothing; 159.96/123.55 lookupFM4 xxy xxz = lookupFM3 xxy xxz; 159.96/123.55 159.96/123.55 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.96/123.55 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_L fm_R key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_L fm_R + mkBalBranch6Size_r key elt fm_L fm_R < 2); 159.96/123.55 159.96/123.55 mkBalBranch6Double_L xyw xyx xyy xyz fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 xyw xyx fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr); 159.96/123.55 159.96/123.55 mkBalBranch6Double_R xyw xyx xyy xyz (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 xyw xyx fm_lrr fm_r); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Double_L xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Single_L xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Double_R xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Single_R xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R fm_L; 159.96/123.55 mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R otherwise; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R fm_R; 159.96/123.55 mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_l xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_r xyw xyx xyy xyz); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 159.96/123.55 mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_r xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_l xyw xyx xyy xyz); 159.96/123.55 159.96/123.55 mkBalBranch6Single_L xyw xyx xyy xyz fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 xyw xyx fm_l fm_rl) fm_rr; 159.96/123.55 159.96/123.55 mkBalBranch6Single_R xyw xyx xyy xyz (Branch key_l elt_l vyw fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 xyw xyx fm_lr fm_r); 159.96/123.55 159.96/123.55 mkBalBranch6Size_l xyw xyx xyy xyz = sizeFM xyy; 159.96/123.55 159.96/123.55 mkBalBranch6Size_r xyw xyx xyy xyz = sizeFM xyz; 159.96/123.55 159.96/123.55 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.96/123.55 mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l; 159.96/123.55 159.96/123.55 mkBranchBalance_ok xzu xzv xzw = True; 159.96/123.55 159.96/123.55 mkBranchLeft_ok xzu xzv xzw = mkBranchLeft_ok0 xzu xzv xzw xzw xzv xzw; 159.96/123.55 159.96/123.55 mkBranchLeft_ok0 xzu xzv xzw fm_l key EmptyFM = True; 159.96/123.55 mkBranchLeft_ok0 xzu xzv xzw fm_l key (Branch left_key vww vwx vwy vwz) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 159.96/123.55 159.96/123.55 mkBranchLeft_ok0Biggest_left_key ywx = fst (findMax ywx); 159.96/123.55 159.96/123.55 mkBranchLeft_size xzu xzv xzw = sizeFM xzw; 159.96/123.55 159.96/123.55 mkBranchResult xzx xzy xzz yuu = Branch xzx xzy (mkBranchUnbox xzz xzx yuu (1 + mkBranchLeft_size xzz xzx yuu + mkBranchRight_size xzz xzx yuu)) yuu xzz; 159.96/123.55 159.96/123.55 mkBranchRight_ok xzu xzv xzw = mkBranchRight_ok0 xzu xzv xzw xzu xzv xzu; 159.96/123.55 159.96/123.55 mkBranchRight_ok0 xzu xzv xzw fm_r key EmptyFM = True; 159.96/123.55 mkBranchRight_ok0 xzu xzv xzw fm_r key (Branch right_key vxu vxv vxw vxx) = key < mkBranchRight_ok0Smallest_right_key fm_r; 159.96/123.55 159.96/123.55 mkBranchRight_ok0Smallest_right_key ywy = fst (findMin ywy); 159.96/123.55 159.96/123.55 mkBranchRight_size xzu xzv xzw = sizeFM xzu; 159.96/123.55 159.96/123.55 mkBranchUnbox :: Ord a => -> (FiniteMap a b) ( -> a ( -> (FiniteMap a b) (Int -> Int))); 159.96/123.55 mkBranchUnbox xzu xzv xzw x = x; 159.96/123.55 159.96/123.55 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.96/123.55 mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 159.96/123.55 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 159.96/123.55 mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.55 159.96/123.55 mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3MkVBalBranch2 vuv vuw vux vuy vuz vvv vvw vvx vvy vvz key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_l vuv vuw vux vuy vuz vvv vvw vvx vvy vvz < mkVBalBranch3Size_r vuv vuw vux vuy vuz vvv vvw vvx vvy vvz); 159.96/123.55 159.96/123.55 mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch 13 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.55 159.96/123.55 mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz)); 159.96/123.55 mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise; 159.96/123.55 159.96/123.55 mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz; 159.96/123.55 mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww < mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww); 159.96/123.55 159.96/123.55 mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yuz yvu yvv yvw yvx); 159.96/123.55 159.96/123.55 mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yvy yvz ywu ywv yww); 159.96/123.55 159.96/123.55 mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 159.96/123.55 mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy; 159.96/123.55 159.96/123.55 mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 159.96/123.55 mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx; 159.96/123.55 159.96/123.55 plusFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.96/123.55 plusFM_C combiner EmptyFM fm2 = fm2; 159.96/123.55 plusFM_C combiner fm1 EmptyFM = fm1; 159.96/123.55 plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key (plusFM_CNew_elt elt2 combiner fm1 split_key) (plusFM_C combiner (plusFM_CLts elt2 combiner fm1 split_key) left) (plusFM_C combiner (plusFM_CGts elt2 combiner fm1 split_key) right); 159.96/123.55 159.96/123.55 plusFM_CGts yuv yuw yux yuy = splitGT yux yuy; 159.96/123.55 159.96/123.55 plusFM_CLts yuv yuw yux yuy = splitLT yux yuy; 159.96/123.55 159.96/123.55 plusFM_CNew_elt yuv yuw yux yuy = plusFM_CNew_elt0 yuv yuw yux yuy yuv yuw (lookupFM yux yuy); 159.96/123.55 159.96/123.55 plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner Nothing = elt2; 159.96/123.55 plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner (Just elt1) = combiner elt1 elt2; 159.96/123.55 159.96/123.55 sIZE_RATIO :: Int; 159.96/123.55 sIZE_RATIO = 5; 159.96/123.55 159.96/123.55 sizeFM :: FiniteMap b a -> Int; 159.96/123.55 sizeFM EmptyFM = 0; 159.96/123.55 sizeFM (Branch wux wuy size wuz wvu) = size; 159.96/123.55 159.96/123.55 splitGT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 159.96/123.55 splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 159.96/123.55 splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key; 159.96/123.55 159.96/123.55 splitGT0 key elt vwu fm_l fm_r split_key True = fm_r; 159.96/123.55 159.96/123.55 splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 159.96/123.55 splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise; 159.96/123.55 159.96/123.55 splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key; 159.96/123.55 splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key); 159.96/123.55 159.96/123.55 splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key); 159.96/123.55 159.96/123.55 splitGT4 EmptyFM split_key = emptyFM; 159.96/123.55 splitGT4 xwu xwv = splitGT3 xwu xwv; 159.96/123.55 159.96/123.55 splitLT :: Ord b => FiniteMap b a -> b -> FiniteMap b a; 159.96/123.55 splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 159.96/123.55 splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key; 159.96/123.55 159.96/123.55 splitLT0 key elt vwv fm_l fm_r split_key True = fm_l; 159.96/123.55 159.96/123.55 splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 159.96/123.55 splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise; 159.96/123.55 159.96/123.55 splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key; 159.96/123.55 splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key); 159.96/123.55 159.96/123.55 splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key); 159.96/123.55 159.96/123.55 splitLT4 EmptyFM split_key = emptyFM; 159.96/123.55 splitLT4 xwy xwz = splitLT3 xwy xwz; 159.96/123.55 159.96/123.55 unitFM :: b -> a -> FiniteMap b a; 159.96/123.55 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 159.96/123.55 159.96/123.55 } 159.96/123.55 module Maybe where { 159.96/123.55 import qualified FiniteMap; 159.96/123.55 import qualified Main; 159.96/123.55 import qualified Prelude; 159.96/123.55 } 159.96/123.55 module Main where { 159.96/123.55 import qualified FiniteMap; 159.96/123.55 import qualified Maybe; 159.96/123.55 import qualified Prelude; 159.96/123.55 } 159.96/123.55 159.96/123.55 ---------------------------------------- 159.96/123.55 159.96/123.55 (13) NumRed (SOUND) 159.96/123.55 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 159.96/123.55 ---------------------------------------- 159.96/123.55 159.96/123.55 (14) 159.96/123.55 Obligation: 159.96/123.55 mainModule Main 159.96/123.55 module FiniteMap where { 159.96/123.55 import qualified Main; 159.96/123.55 import qualified Maybe; 159.96/123.55 import qualified Prelude; 159.96/123.55 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 159.96/123.55 159.96/123.55 instance (Eq a, Eq b) => Eq FiniteMap b a where { 159.96/123.55 (==) fm_1 fm_2 = sizeFM fm_1 == sizeFM fm_2 && fmToList fm_1 == fmToList fm_2; 159.96/123.55 } 159.96/123.55 addToFM :: Ord b => FiniteMap b a -> b -> a -> FiniteMap b a; 159.96/123.55 addToFM fm key elt = addToFM_C addToFM0 fm key elt; 159.96/123.55 159.96/123.55 addToFM0 old new = new; 159.96/123.55 159.96/123.55 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 159.96/123.55 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 159.96/123.55 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; 159.96/123.55 159.96/123.55 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; 159.96/123.55 159.96/123.55 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); 159.96/123.55 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; 159.96/123.55 159.96/123.55 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; 159.96/123.55 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); 159.96/123.55 159.96/123.55 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); 159.96/123.55 159.96/123.55 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 159.96/123.55 addToFM_C4 wzu wzv wzw wzx = addToFM_C3 wzu wzv wzw wzx; 159.96/123.55 159.96/123.55 emptyFM :: FiniteMap b a; 159.96/123.55 emptyFM = EmptyFM; 159.96/123.55 159.96/123.55 findMax :: FiniteMap a b -> (a,b); 159.96/123.55 findMax (Branch key elt vxy vxz EmptyFM) = (key,elt); 159.96/123.55 findMax (Branch key elt vyu vyv fm_r) = findMax fm_r; 159.96/123.55 159.96/123.55 findMin :: FiniteMap a b -> (a,b); 159.96/123.55 findMin (Branch key elt wvw EmptyFM wvx) = (key,elt); 159.96/123.55 findMin (Branch key elt wvy fm_l wvz) = findMin fm_l; 159.96/123.55 159.96/123.55 fmToList :: FiniteMap b a -> [(b,a)]; 159.96/123.55 fmToList fm = foldFM fmToList0 [] fm; 159.96/123.55 159.96/123.55 fmToList0 key elt rest = (key,elt) : rest; 159.96/123.55 159.96/123.55 foldFM :: (c -> b -> a -> a) -> a -> FiniteMap c b -> a; 159.96/123.55 foldFM k z EmptyFM = z; 159.96/123.55 foldFM k z (Branch key elt wuw fm_l fm_r) = foldFM k (k key elt (foldFM k z fm_r)) fm_l; 159.96/123.55 159.96/123.55 lookupFM :: Ord a => FiniteMap a b -> a -> Maybe b; 159.96/123.55 lookupFM EmptyFM key = lookupFM4 EmptyFM key; 159.96/123.55 lookupFM (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find; 159.96/123.55 159.96/123.55 lookupFM0 key elt wvv fm_l fm_r key_to_find True = Just elt; 159.96/123.55 159.96/123.55 lookupFM1 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_r key_to_find; 159.96/123.55 lookupFM1 key elt wvv fm_l fm_r key_to_find False = lookupFM0 key elt wvv fm_l fm_r key_to_find otherwise; 159.96/123.55 159.96/123.55 lookupFM2 key elt wvv fm_l fm_r key_to_find True = lookupFM fm_l key_to_find; 159.96/123.55 lookupFM2 key elt wvv fm_l fm_r key_to_find False = lookupFM1 key elt wvv fm_l fm_r key_to_find (key_to_find > key); 159.96/123.55 159.96/123.55 lookupFM3 (Branch key elt wvv fm_l fm_r) key_to_find = lookupFM2 key elt wvv fm_l fm_r key_to_find (key_to_find < key); 159.96/123.55 159.96/123.55 lookupFM4 EmptyFM key = Nothing; 159.96/123.55 lookupFM4 xxy xxz = lookupFM3 xxy xxz; 159.96/123.55 159.96/123.55 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.96/123.55 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 key elt fm_L fm_R key elt fm_L fm_R (mkBalBranch6Size_l key elt fm_L fm_R + mkBalBranch6Size_r key elt fm_L fm_R < Pos (Succ (Succ Zero))); 159.96/123.55 159.96/123.55 mkBalBranch6Double_L xyw xyx xyy xyz fm_l (Branch key_r elt_r vzw (Branch key_rl elt_rl vzx 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))))))) xyw xyx fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr); 159.96/123.55 159.96/123.55 mkBalBranch6Double_R xyw xyx xyy xyz (Branch key_l elt_l vyx fm_ll (Branch key_lr elt_lr vyy 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))))))))))))) xyw xyx fm_lrr fm_r); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Double_L xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr True = mkBalBranch6Single_L xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr False = mkBalBranch6MkBalBranch00 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr otherwise; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch02 xyw xyx xyy xyz fm_L fm_R (Branch vzy vzz wuu fm_rl fm_rr) = mkBalBranch6MkBalBranch01 xyw xyx xyy xyz fm_L fm_R vzy vzz wuu fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Double_R xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr True = mkBalBranch6Single_R xyw xyx xyy xyz fm_L fm_R; 159.96/123.55 mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr False = mkBalBranch6MkBalBranch10 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr otherwise; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch12 xyw xyx xyy xyz fm_L fm_R (Branch vyz vzu vzv fm_ll fm_lr) = mkBalBranch6MkBalBranch11 xyw xyx xyy xyz fm_L fm_R vyz vzu vzv fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 xyw xyx xyy xyz fm_L fm_R fm_L; 159.96/123.55 mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 xyw xyx xyy xyz key elt fm_L fm_R otherwise; 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 xyw xyx xyy xyz fm_L fm_R fm_R; 159.96/123.55 mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_l xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_r xyw xyx xyy xyz); 159.96/123.55 159.96/123.55 mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R; 159.96/123.55 mkBalBranch6MkBalBranch5 xyw xyx xyy xyz key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 xyw xyx xyy xyz key elt fm_L fm_R (mkBalBranch6Size_r xyw xyx xyy xyz > sIZE_RATIO * mkBalBranch6Size_l xyw xyx xyy xyz); 159.96/123.55 159.96/123.55 mkBalBranch6Single_L xyw xyx xyy xyz fm_l (Branch key_r elt_r wuv fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) xyw xyx fm_l fm_rl) fm_rr; 159.96/123.55 159.96/123.55 mkBalBranch6Single_R xyw xyx xyy xyz (Branch key_l elt_l vyw 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)))))))))) xyw xyx fm_lr fm_r); 159.96/123.55 159.96/123.55 mkBalBranch6Size_l xyw xyx xyy xyz = sizeFM xyy; 159.96/123.55 159.96/123.55 mkBalBranch6Size_r xyw xyx xyy xyz = sizeFM xyz; 159.96/123.55 159.96/123.55 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 159.96/123.55 mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_r fm_l; 159.96/123.55 159.96/123.55 mkBranchBalance_ok xzu xzv xzw = True; 159.96/123.55 159.96/123.55 mkBranchLeft_ok xzu xzv xzw = mkBranchLeft_ok0 xzu xzv xzw xzw xzv xzw; 159.96/123.55 159.96/123.55 mkBranchLeft_ok0 xzu xzv xzw fm_l key EmptyFM = True; 159.96/123.55 mkBranchLeft_ok0 xzu xzv xzw fm_l key (Branch left_key vww vwx vwy vwz) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 159.96/123.55 159.96/123.55 mkBranchLeft_ok0Biggest_left_key ywx = fst (findMax ywx); 159.96/123.55 159.96/123.55 mkBranchLeft_size xzu xzv xzw = sizeFM xzw; 159.96/123.55 159.96/123.55 mkBranchResult xzx xzy xzz yuu = Branch xzx xzy (mkBranchUnbox xzz xzx yuu (Pos (Succ Zero) + mkBranchLeft_size xzz xzx yuu + mkBranchRight_size xzz xzx yuu)) yuu xzz; 159.96/123.55 159.96/123.55 mkBranchRight_ok xzu xzv xzw = mkBranchRight_ok0 xzu xzv xzw xzu xzv xzu; 159.96/123.55 159.96/123.55 mkBranchRight_ok0 xzu xzv xzw fm_r key EmptyFM = True; 159.96/123.55 mkBranchRight_ok0 xzu xzv xzw fm_r key (Branch right_key vxu vxv vxw vxx) = key < mkBranchRight_ok0Smallest_right_key fm_r; 159.96/123.55 159.96/123.55 mkBranchRight_ok0Smallest_right_key ywy = fst (findMin ywy); 159.96/123.55 159.96/123.55 mkBranchRight_size xzu xzv xzw = sizeFM xzu; 159.96/123.55 159.96/123.55 mkBranchUnbox :: Ord a => -> (FiniteMap a b) ( -> a ( -> (FiniteMap a b) (Int -> Int))); 159.96/123.55 mkBranchUnbox xzu xzv xzw x = x; 159.96/123.55 159.96/123.55 mkVBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.96/123.55 mkVBalBranch key elt EmptyFM fm_r = mkVBalBranch5 key elt EmptyFM fm_r; 159.96/123.55 mkVBalBranch key elt fm_l EmptyFM = mkVBalBranch4 key elt fm_l EmptyFM; 159.96/123.55 mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.55 159.96/123.55 mkVBalBranch3 key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz) = mkVBalBranch3MkVBalBranch2 vuv vuw vux vuy vuz vvv vvw vvx vvy vvz key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_l vuv vuw vux vuy vuz vvv vvw vvx vvy vvz < mkVBalBranch3Size_r vuv vuw vux vuy vuz vvv vvw vvx vvy vvz); 159.96/123.55 159.96/123.55 mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))))) key elt (Branch vuv vuw vux vuy vuz) (Branch vvv vvw vvx vvy vvz); 159.96/123.55 159.96/123.55 mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vuv vuw vuy (mkVBalBranch key elt vuz (Branch vvv vvw vvx vvy vvz)); 159.96/123.55 mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch0 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz otherwise; 159.96/123.55 159.96/123.55 mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz True = mkBalBranch vvv vvw (mkVBalBranch key elt (Branch vuv vuw vux vuy vuz) vvy) vvz; 159.96/123.55 mkVBalBranch3MkVBalBranch2 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz False = mkVBalBranch3MkVBalBranch1 yuz yvu yvv yvw yvx yvy yvz ywu ywv yww key elt vuv vuw vux vuy vuz vvv vvw vvx vvy vvz (sIZE_RATIO * mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww < mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww); 159.96/123.55 159.96/123.55 mkVBalBranch3Size_l yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yuz yvu yvv yvw yvx); 159.96/123.55 159.96/123.55 mkVBalBranch3Size_r yuz yvu yvv yvw yvx yvy yvz ywu ywv yww = sizeFM (Branch yvy yvz ywu ywv yww); 159.96/123.55 159.96/123.55 mkVBalBranch4 key elt fm_l EmptyFM = addToFM fm_l key elt; 159.96/123.55 mkVBalBranch4 xuv xuw xux xuy = mkVBalBranch3 xuv xuw xux xuy; 159.96/123.55 159.96/123.55 mkVBalBranch5 key elt EmptyFM fm_r = addToFM fm_r key elt; 159.96/123.55 mkVBalBranch5 xvu xvv xvw xvx = mkVBalBranch4 xvu xvv xvw xvx; 159.96/123.55 159.96/123.55 plusFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 159.96/123.55 plusFM_C combiner EmptyFM fm2 = fm2; 159.96/123.55 plusFM_C combiner fm1 EmptyFM = fm1; 159.96/123.55 plusFM_C combiner fm1 (Branch split_key elt2 zz left right) = mkVBalBranch split_key (plusFM_CNew_elt elt2 combiner fm1 split_key) (plusFM_C combiner (plusFM_CLts elt2 combiner fm1 split_key) left) (plusFM_C combiner (plusFM_CGts elt2 combiner fm1 split_key) right); 159.96/123.55 159.96/123.55 plusFM_CGts yuv yuw yux yuy = splitGT yux yuy; 159.96/123.55 159.96/123.55 plusFM_CLts yuv yuw yux yuy = splitLT yux yuy; 159.96/123.55 159.96/123.55 plusFM_CNew_elt yuv yuw yux yuy = plusFM_CNew_elt0 yuv yuw yux yuy yuv yuw (lookupFM yux yuy); 159.96/123.55 159.96/123.55 plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner Nothing = elt2; 159.96/123.55 plusFM_CNew_elt0 yuv yuw yux yuy elt2 combiner (Just elt1) = combiner elt1 elt2; 159.96/123.55 159.96/123.55 sIZE_RATIO :: Int; 159.96/123.55 sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero))))); 159.96/123.55 159.96/123.55 sizeFM :: FiniteMap a b -> Int; 159.96/123.55 sizeFM EmptyFM = Pos Zero; 159.96/123.55 sizeFM (Branch wux wuy size wuz wvu) = size; 159.96/123.55 159.96/123.55 splitGT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 159.96/123.55 splitGT EmptyFM split_key = splitGT4 EmptyFM split_key; 159.96/123.55 splitGT (Branch key elt vwu fm_l fm_r) split_key = splitGT3 (Branch key elt vwu fm_l fm_r) split_key; 159.96/123.55 159.96/123.55 splitGT0 key elt vwu fm_l fm_r split_key True = fm_r; 159.96/123.55 159.96/123.55 splitGT1 key elt vwu fm_l fm_r split_key True = mkVBalBranch key elt (splitGT fm_l split_key) fm_r; 159.96/123.55 splitGT1 key elt vwu fm_l fm_r split_key False = splitGT0 key elt vwu fm_l fm_r split_key otherwise; 159.96/123.55 159.96/123.55 splitGT2 key elt vwu fm_l fm_r split_key True = splitGT fm_r split_key; 159.96/123.55 splitGT2 key elt vwu fm_l fm_r split_key False = splitGT1 key elt vwu fm_l fm_r split_key (split_key < key); 159.96/123.55 159.96/123.55 splitGT3 (Branch key elt vwu fm_l fm_r) split_key = splitGT2 key elt vwu fm_l fm_r split_key (split_key > key); 159.96/123.55 159.96/123.55 splitGT4 EmptyFM split_key = emptyFM; 159.96/123.55 splitGT4 xwu xwv = splitGT3 xwu xwv; 159.96/123.55 159.96/123.55 splitLT :: Ord a => FiniteMap a b -> a -> FiniteMap a b; 159.96/123.55 splitLT EmptyFM split_key = splitLT4 EmptyFM split_key; 159.96/123.55 splitLT (Branch key elt vwv fm_l fm_r) split_key = splitLT3 (Branch key elt vwv fm_l fm_r) split_key; 159.96/123.55 159.96/123.55 splitLT0 key elt vwv fm_l fm_r split_key True = fm_l; 159.96/123.55 159.96/123.55 splitLT1 key elt vwv fm_l fm_r split_key True = mkVBalBranch key elt fm_l (splitLT fm_r split_key); 159.96/123.55 splitLT1 key elt vwv fm_l fm_r split_key False = splitLT0 key elt vwv fm_l fm_r split_key otherwise; 159.96/123.55 159.96/123.55 splitLT2 key elt vwv fm_l fm_r split_key True = splitLT fm_l split_key; 159.96/123.55 splitLT2 key elt vwv fm_l fm_r split_key False = splitLT1 key elt vwv fm_l fm_r split_key (split_key > key); 159.96/123.55 159.96/123.55 splitLT3 (Branch key elt vwv fm_l fm_r) split_key = splitLT2 key elt vwv fm_l fm_r split_key (split_key < key); 159.96/123.55 159.96/123.55 splitLT4 EmptyFM split_key = emptyFM; 159.96/123.55 splitLT4 xwy xwz = splitLT3 xwy xwz; 159.96/123.55 159.96/123.55 unitFM :: b -> a -> FiniteMap b a; 159.96/123.55 unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM; 159.96/123.55 159.96/123.55 } 159.96/123.55 module Maybe where { 159.96/123.55 import qualified FiniteMap; 159.96/123.55 import qualified Main; 159.96/123.55 import qualified Prelude; 159.96/123.55 } 159.96/123.55 module Main where { 159.96/123.55 import qualified FiniteMap; 159.96/123.55 import qualified Maybe; 159.96/123.55 import qualified Prelude; 159.96/123.55 } 160.04/123.59 EOF