10.44/4.59 YES 13.00/5.28 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 13.00/5.28 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.00/5.28 13.00/5.28 13.00/5.28 H-Termination with start terms of the given HASKELL could be proven: 13.00/5.28 13.00/5.28 (0) HASKELL 13.00/5.28 (1) LR [EQUIVALENT, 0 ms] 13.00/5.28 (2) HASKELL 13.00/5.28 (3) CR [EQUIVALENT, 0 ms] 13.00/5.28 (4) HASKELL 13.00/5.28 (5) BR [EQUIVALENT, 0 ms] 13.00/5.28 (6) HASKELL 13.00/5.28 (7) COR [EQUIVALENT, 20 ms] 13.00/5.28 (8) HASKELL 13.00/5.28 (9) LetRed [EQUIVALENT, 0 ms] 13.00/5.28 (10) HASKELL 13.00/5.28 (11) NumRed [SOUND, 0 ms] 13.00/5.28 (12) HASKELL 13.00/5.28 (13) Narrow [SOUND, 0 ms] 13.00/5.28 (14) QDP 13.00/5.28 (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.00/5.28 (16) YES 13.00/5.28 13.00/5.28 13.00/5.28 ---------------------------------------- 13.00/5.28 13.00/5.28 (0) 13.00/5.28 Obligation: 13.00/5.28 mainModule Main 13.00/5.28 module FiniteMap where { 13.00/5.28 import qualified Main; 13.00/5.28 import qualified Maybe; 13.00/5.28 import qualified Prelude; 13.00/5.28 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 13.00/5.28 13.00/5.28 instance (Eq a, Eq b) => Eq FiniteMap a b where { 13.00/5.28 } 13.00/5.28 addListToFM :: Ord b => FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.00/5.28 addListToFM fm key_elt_pairs = addListToFM_C (\old new ->new) fm key_elt_pairs; 13.00/5.28 13.00/5.28 addListToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> [(a,b)] -> FiniteMap a b; 13.00/5.28 addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 13.00/5.28 add fmap (key,elt) = addToFM_C combiner fmap key elt; 13.00/5.28 }; 13.00/5.28 13.00/5.28 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 13.00/5.28 addToFM_C combiner EmptyFM key elt = unitFM key elt; 13.00/5.28 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 13.00/5.28 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 13.00/5.28 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 13.00/5.28 13.00/5.28 emptyFM :: FiniteMap b a; 13.00/5.28 emptyFM = EmptyFM; 13.00/5.28 13.00/5.28 findMax :: FiniteMap a b -> (a,b); 13.00/5.28 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 13.00/5.28 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 13.00/5.28 13.00/5.28 findMin :: FiniteMap a b -> (a,b); 13.00/5.28 findMin (Branch key elt _ EmptyFM _) = (key,elt); 13.00/5.28 findMin (Branch key elt _ fm_l _) = findMin fm_l; 13.00/5.28 13.00/5.28 listToFM :: Ord b => [(b,a)] -> FiniteMap b a; 13.00/5.28 listToFM = addListToFM emptyFM; 13.00/5.28 13.00/5.28 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.00/5.28 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 13.00/5.28 | size_r > sIZE_RATIO * size_l = case fm_R of { 13.00/5.28 Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R 13.00/5.28 | otherwise -> double_L fm_L fm_R; 13.00/5.28 } 13.00/5.28 | size_l > sIZE_RATIO * size_r = case fm_L of { 13.00/5.28 Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R 13.00/5.28 | otherwise -> double_R fm_L fm_R; 13.00/5.28 } 13.00/5.28 | otherwise = mkBranch 2 key elt fm_L fm_R where { 13.00/5.28 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); 13.00/5.28 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); 13.00/5.28 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; 13.00/5.28 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); 13.00/5.28 size_l = sizeFM fm_L; 13.00/5.28 size_r = sizeFM fm_R; 13.00/5.28 }; 13.00/5.28 13.00/5.28 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 13.00/5.28 mkBranch which key elt fm_l fm_r = let { 13.00/5.28 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 13.00/5.28 } in result where { 13.00/5.28 balance_ok = True; 13.00/5.28 left_ok = case fm_l of { 13.00/5.28 EmptyFM-> True; 13.00/5.28 Branch left_key _ _ _ _-> let { 13.00/5.28 biggest_left_key = fst (findMax fm_l); 13.00/5.28 } in biggest_left_key < key; 13.00/5.28 } ; 13.00/5.28 left_size = sizeFM fm_l; 13.00/5.28 right_ok = case fm_r of { 13.00/5.28 EmptyFM-> True; 13.00/5.28 Branch right_key _ _ _ _-> let { 13.00/5.28 smallest_right_key = fst (findMin fm_r); 13.00/5.28 } in key < smallest_right_key; 13.00/5.28 } ; 13.00/5.28 right_size = sizeFM fm_r; 13.00/5.28 unbox :: Int -> Int; 13.00/5.28 unbox x = x; 13.00/5.28 }; 13.00/5.28 13.00/5.28 sIZE_RATIO :: Int; 13.00/5.28 sIZE_RATIO = 5; 13.00/5.28 13.00/5.28 sizeFM :: FiniteMap a b -> Int; 13.00/5.28 sizeFM EmptyFM = 0; 13.00/5.28 sizeFM (Branch _ _ size _ _) = size; 13.00/5.28 13.00/5.28 unitFM :: b -> a -> FiniteMap b a; 13.00/5.28 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 13.00/5.28 13.00/5.28 } 13.00/5.28 module Maybe where { 13.00/5.28 import qualified FiniteMap; 13.00/5.28 import qualified Main; 13.00/5.28 import qualified Prelude; 13.00/5.28 } 13.00/5.28 module Main where { 13.00/5.28 import qualified FiniteMap; 13.00/5.28 import qualified Maybe; 13.00/5.28 import qualified Prelude; 13.00/5.28 } 13.00/5.28 13.00/5.28 ---------------------------------------- 13.00/5.28 13.00/5.28 (1) LR (EQUIVALENT) 13.00/5.28 Lambda Reductions: 13.00/5.28 The following Lambda expression 13.00/5.28 "\oldnew->new" 13.00/5.28 is transformed to 13.00/5.28 "addListToFM0 old new = new; 13.00/5.28 " 13.00/5.28 13.00/5.28 ---------------------------------------- 13.00/5.28 13.00/5.28 (2) 13.00/5.28 Obligation: 13.00/5.28 mainModule Main 13.00/5.28 module FiniteMap where { 13.00/5.28 import qualified Main; 13.00/5.28 import qualified Maybe; 13.00/5.28 import qualified Prelude; 13.00/5.28 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 13.00/5.28 13.00/5.28 instance (Eq a, Eq b) => Eq FiniteMap b a where { 13.00/5.28 } 13.00/5.28 addListToFM :: Ord a => FiniteMap a b -> [(a,b)] -> FiniteMap a b; 13.00/5.28 addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs; 13.00/5.28 13.00/5.28 addListToFM0 old new = new; 13.00/5.28 13.00/5.28 addListToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.00/5.28 addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 13.00/5.28 add fmap (key,elt) = addToFM_C combiner fmap key elt; 13.00/5.28 }; 13.00/5.28 13.00/5.28 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 13.00/5.28 addToFM_C combiner EmptyFM key elt = unitFM key elt; 13.00/5.28 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 13.00/5.28 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 13.00/5.28 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 13.00/5.28 13.00/5.28 emptyFM :: FiniteMap b a; 13.00/5.28 emptyFM = EmptyFM; 13.00/5.28 13.00/5.28 findMax :: FiniteMap a b -> (a,b); 13.00/5.28 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 13.00/5.28 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 13.00/5.28 13.00/5.28 findMin :: FiniteMap a b -> (a,b); 13.00/5.28 findMin (Branch key elt _ EmptyFM _) = (key,elt); 13.00/5.28 findMin (Branch key elt _ fm_l _) = findMin fm_l; 13.00/5.28 13.00/5.28 listToFM :: Ord a => [(a,b)] -> FiniteMap a b; 13.00/5.28 listToFM = addListToFM emptyFM; 13.00/5.28 13.00/5.28 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.00/5.28 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 13.00/5.28 | size_r > sIZE_RATIO * size_l = case fm_R of { 13.00/5.28 Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R 13.00/5.28 | otherwise -> double_L fm_L fm_R; 13.00/5.28 } 13.00/5.28 | size_l > sIZE_RATIO * size_r = case fm_L of { 13.00/5.28 Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R 13.00/5.28 | otherwise -> double_R fm_L fm_R; 13.00/5.28 } 13.00/5.28 | otherwise = mkBranch 2 key elt fm_L fm_R where { 13.00/5.28 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); 13.00/5.28 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); 13.00/5.28 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; 13.00/5.28 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); 13.00/5.28 size_l = sizeFM fm_L; 13.00/5.28 size_r = sizeFM fm_R; 13.00/5.28 }; 13.00/5.28 13.00/5.28 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 13.00/5.28 mkBranch which key elt fm_l fm_r = let { 13.00/5.28 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 13.00/5.28 } in result where { 13.00/5.28 balance_ok = True; 13.00/5.28 left_ok = case fm_l of { 13.00/5.28 EmptyFM-> True; 13.00/5.28 Branch left_key _ _ _ _-> let { 13.00/5.28 biggest_left_key = fst (findMax fm_l); 13.00/5.28 } in biggest_left_key < key; 13.00/5.28 } ; 13.00/5.28 left_size = sizeFM fm_l; 13.00/5.28 right_ok = case fm_r of { 13.00/5.28 EmptyFM-> True; 13.00/5.28 Branch right_key _ _ _ _-> let { 13.00/5.28 smallest_right_key = fst (findMin fm_r); 13.00/5.28 } in key < smallest_right_key; 13.00/5.28 } ; 13.00/5.28 right_size = sizeFM fm_r; 13.00/5.28 unbox :: Int -> Int; 13.00/5.28 unbox x = x; 13.00/5.28 }; 13.00/5.28 13.00/5.28 sIZE_RATIO :: Int; 13.00/5.28 sIZE_RATIO = 5; 13.00/5.28 13.00/5.28 sizeFM :: FiniteMap b a -> Int; 13.00/5.28 sizeFM EmptyFM = 0; 13.00/5.28 sizeFM (Branch _ _ size _ _) = size; 13.00/5.28 13.00/5.28 unitFM :: b -> a -> FiniteMap b a; 13.00/5.28 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 13.00/5.28 13.00/5.28 } 13.00/5.28 module Maybe where { 13.00/5.28 import qualified FiniteMap; 13.00/5.28 import qualified Main; 13.00/5.28 import qualified Prelude; 13.00/5.28 } 13.00/5.28 module Main where { 13.00/5.28 import qualified FiniteMap; 13.00/5.28 import qualified Maybe; 13.00/5.28 import qualified Prelude; 13.00/5.28 } 13.00/5.28 13.00/5.28 ---------------------------------------- 13.00/5.28 13.00/5.28 (3) CR (EQUIVALENT) 13.00/5.28 Case Reductions: 13.00/5.28 The following Case expression 13.00/5.28 "case fm_r of { 13.00/5.28 EmptyFM -> True; 13.00/5.28 Branch right_key _ _ _ _ -> let { 13.00/5.28 smallest_right_key = fst (findMin fm_r); 13.00/5.28 } in key < smallest_right_key} 13.00/5.28 " 13.00/5.28 is transformed to 13.00/5.28 "right_ok0 fm_r key EmptyFM = True; 13.00/5.28 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 13.00/5.28 smallest_right_key = fst (findMin fm_r); 13.00/5.28 } in key < smallest_right_key; 13.00/5.28 " 13.00/5.28 The following Case expression 13.00/5.28 "case fm_l of { 13.00/5.28 EmptyFM -> True; 13.00/5.28 Branch left_key _ _ _ _ -> let { 13.00/5.28 biggest_left_key = fst (findMax fm_l); 13.00/5.28 } in biggest_left_key < key} 13.00/5.28 " 13.00/5.28 is transformed to 13.00/5.28 "left_ok0 fm_l key EmptyFM = True; 13.00/5.28 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 13.00/5.28 biggest_left_key = fst (findMax fm_l); 13.00/5.28 } in biggest_left_key < key; 13.00/5.28 " 13.00/5.28 The following Case expression 13.00/5.28 "case fm_R of { 13.00/5.28 Branch _ _ _ fm_rl fm_rr |sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R} 13.00/5.28 " 13.00/5.28 is transformed to 13.00/5.28 "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; 13.00/5.28 " 13.00/5.28 The following Case expression 13.00/5.28 "case fm_L of { 13.00/5.28 Branch _ _ _ fm_ll fm_lr |sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R} 13.00/5.28 " 13.00/5.28 is transformed to 13.00/5.28 "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; 13.00/5.28 " 13.00/5.28 13.00/5.28 ---------------------------------------- 13.00/5.28 13.00/5.28 (4) 13.00/5.28 Obligation: 13.00/5.28 mainModule Main 13.00/5.28 module FiniteMap where { 13.00/5.28 import qualified Main; 13.00/5.28 import qualified Maybe; 13.00/5.28 import qualified Prelude; 13.00/5.28 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 13.00/5.28 13.00/5.28 instance (Eq a, Eq b) => Eq FiniteMap a b where { 13.00/5.28 } 13.00/5.28 addListToFM :: Ord a => FiniteMap a b -> [(a,b)] -> FiniteMap a b; 13.00/5.28 addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs; 13.00/5.28 13.00/5.28 addListToFM0 old new = new; 13.00/5.28 13.00/5.28 addListToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.00/5.28 addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 13.00/5.28 add fmap (key,elt) = addToFM_C combiner fmap key elt; 13.00/5.28 }; 13.00/5.28 13.00/5.28 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 13.00/5.28 addToFM_C combiner EmptyFM key elt = unitFM key elt; 13.00/5.28 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 13.00/5.28 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 13.00/5.28 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 13.00/5.28 13.00/5.28 emptyFM :: FiniteMap b a; 13.00/5.28 emptyFM = EmptyFM; 13.00/5.28 13.00/5.28 findMax :: FiniteMap b a -> (b,a); 13.00/5.28 findMax (Branch key elt _ _ EmptyFM) = (key,elt); 13.00/5.28 findMax (Branch key elt _ _ fm_r) = findMax fm_r; 13.00/5.28 13.00/5.28 findMin :: FiniteMap b a -> (b,a); 13.00/5.28 findMin (Branch key elt _ EmptyFM _) = (key,elt); 13.00/5.28 findMin (Branch key elt _ fm_l _) = findMin fm_l; 13.00/5.28 13.00/5.28 listToFM :: Ord b => [(b,a)] -> FiniteMap b a; 13.00/5.28 listToFM = addListToFM emptyFM; 13.00/5.28 13.00/5.28 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.00/5.28 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 13.00/5.28 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 13.00/5.28 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 13.00/5.28 | otherwise = mkBranch 2 key elt fm_L fm_R where { 13.00/5.28 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); 13.00/5.28 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); 13.00/5.28 mkBalBranch0 fm_L fm_R (Branch _ _ _ fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 13.00/5.28 | otherwise = double_L fm_L fm_R; 13.00/5.28 mkBalBranch1 fm_L fm_R (Branch _ _ _ fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 13.00/5.28 | otherwise = double_R fm_L fm_R; 13.00/5.28 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; 13.00/5.28 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); 13.00/5.28 size_l = sizeFM fm_L; 13.00/5.28 size_r = sizeFM fm_R; 13.00/5.28 }; 13.00/5.28 13.00/5.28 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.00/5.28 mkBranch which key elt fm_l fm_r = let { 13.00/5.28 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 13.00/5.28 } in result where { 13.00/5.28 balance_ok = True; 13.00/5.28 left_ok = left_ok0 fm_l key fm_l; 13.00/5.28 left_ok0 fm_l key EmptyFM = True; 13.00/5.28 left_ok0 fm_l key (Branch left_key _ _ _ _) = let { 13.00/5.28 biggest_left_key = fst (findMax fm_l); 13.00/5.28 } in biggest_left_key < key; 13.00/5.28 left_size = sizeFM fm_l; 13.00/5.28 right_ok = right_ok0 fm_r key fm_r; 13.00/5.28 right_ok0 fm_r key EmptyFM = True; 13.00/5.28 right_ok0 fm_r key (Branch right_key _ _ _ _) = let { 13.00/5.28 smallest_right_key = fst (findMin fm_r); 13.00/5.28 } in key < smallest_right_key; 13.00/5.28 right_size = sizeFM fm_r; 13.00/5.28 unbox :: Int -> Int; 13.00/5.28 unbox x = x; 13.00/5.28 }; 13.00/5.28 13.00/5.28 sIZE_RATIO :: Int; 13.00/5.28 sIZE_RATIO = 5; 13.00/5.28 13.00/5.28 sizeFM :: FiniteMap a b -> Int; 13.00/5.28 sizeFM EmptyFM = 0; 13.00/5.28 sizeFM (Branch _ _ size _ _) = size; 13.00/5.28 13.00/5.28 unitFM :: a -> b -> FiniteMap a b; 13.00/5.28 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 13.00/5.28 13.00/5.28 } 13.00/5.28 module Maybe where { 13.00/5.28 import qualified FiniteMap; 13.00/5.28 import qualified Main; 13.00/5.28 import qualified Prelude; 13.00/5.28 } 13.00/5.28 module Main where { 13.00/5.28 import qualified FiniteMap; 13.00/5.28 import qualified Maybe; 13.00/5.28 import qualified Prelude; 13.00/5.28 } 13.00/5.28 13.00/5.28 ---------------------------------------- 13.00/5.28 13.00/5.28 (5) BR (EQUIVALENT) 13.00/5.28 Replaced joker patterns by fresh variables and removed binding patterns. 13.00/5.28 ---------------------------------------- 13.00/5.28 13.00/5.28 (6) 13.00/5.28 Obligation: 13.00/5.28 mainModule Main 13.00/5.28 module FiniteMap where { 13.00/5.28 import qualified Main; 13.00/5.28 import qualified Maybe; 13.00/5.28 import qualified Prelude; 13.00/5.28 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 13.00/5.28 13.00/5.28 instance (Eq a, Eq b) => Eq FiniteMap b a where { 13.00/5.28 } 13.00/5.28 addListToFM :: Ord b => FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.00/5.28 addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs; 13.00/5.28 13.00/5.28 addListToFM0 old new = new; 13.00/5.28 13.00/5.28 addListToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.00/5.28 addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 13.00/5.28 add fmap (key,elt) = addToFM_C combiner fmap key elt; 13.00/5.28 }; 13.00/5.28 13.00/5.28 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 13.00/5.28 addToFM_C combiner EmptyFM key elt = unitFM key elt; 13.00/5.28 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 13.00/5.28 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) 13.00/5.28 | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; 13.00/5.28 13.00/5.28 emptyFM :: FiniteMap a b; 13.00/5.28 emptyFM = EmptyFM; 13.00/5.28 13.00/5.28 findMax :: FiniteMap a b -> (a,b); 13.00/5.28 findMax (Branch key elt xv xw EmptyFM) = (key,elt); 13.00/5.28 findMax (Branch key elt xx xy fm_r) = findMax fm_r; 13.00/5.28 13.00/5.28 findMin :: FiniteMap a b -> (a,b); 13.00/5.28 findMin (Branch key elt vux EmptyFM vuy) = (key,elt); 13.00/5.28 findMin (Branch key elt vuz fm_l vvu) = findMin fm_l; 13.00/5.28 13.00/5.28 listToFM :: Ord a => [(a,b)] -> FiniteMap a b; 13.00/5.28 listToFM = addListToFM emptyFM; 13.00/5.28 13.00/5.28 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.00/5.28 mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R 13.00/5.28 | size_r > sIZE_RATIO * size_l = mkBalBranch0 fm_L fm_R fm_R 13.00/5.28 | size_l > sIZE_RATIO * size_r = mkBalBranch1 fm_L fm_R fm_L 13.00/5.28 | otherwise = mkBranch 2 key elt fm_L fm_R where { 13.00/5.28 double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu 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); 13.00/5.28 double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv 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); 13.00/5.28 mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) | sizeFM fm_rl < 2 * sizeFM fm_rr = single_L fm_L fm_R 13.00/5.28 | otherwise = double_L fm_L fm_R; 13.35/5.44 mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) | sizeFM fm_lr < 2 * sizeFM fm_ll = single_R fm_L fm_R 13.35/5.44 | otherwise = double_R fm_L fm_R; 13.35/5.44 single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 13.35/5.44 single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 13.35/5.44 size_l = sizeFM fm_L; 13.35/5.44 size_r = sizeFM fm_R; 13.35/5.44 }; 13.35/5.44 13.35/5.44 mkBranch :: Ord b => Int -> b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.35/5.44 mkBranch which key elt fm_l fm_r = let { 13.35/5.44 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 13.35/5.44 } in result where { 13.35/5.44 balance_ok = True; 13.35/5.44 left_ok = left_ok0 fm_l key fm_l; 13.35/5.44 left_ok0 fm_l key EmptyFM = True; 13.35/5.44 left_ok0 fm_l key (Branch left_key vz wu wv ww) = let { 13.35/5.44 biggest_left_key = fst (findMax fm_l); 13.35/5.44 } in biggest_left_key < key; 13.35/5.44 left_size = sizeFM fm_l; 13.35/5.44 right_ok = right_ok0 fm_r key fm_r; 13.35/5.44 right_ok0 fm_r key EmptyFM = True; 13.35/5.44 right_ok0 fm_r key (Branch right_key wx wy wz xu) = let { 13.35/5.44 smallest_right_key = fst (findMin fm_r); 13.35/5.44 } in key < smallest_right_key; 13.35/5.44 right_size = sizeFM fm_r; 13.35/5.44 unbox :: Int -> Int; 13.35/5.44 unbox x = x; 13.35/5.44 }; 13.35/5.44 13.35/5.44 sIZE_RATIO :: Int; 13.35/5.44 sIZE_RATIO = 5; 13.35/5.44 13.35/5.44 sizeFM :: FiniteMap b a -> Int; 13.35/5.44 sizeFM EmptyFM = 0; 13.35/5.44 sizeFM (Branch zz vuu size vuv vuw) = size; 13.35/5.44 13.35/5.44 unitFM :: a -> b -> FiniteMap a b; 13.35/5.44 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 13.35/5.44 13.35/5.44 } 13.35/5.44 module Maybe where { 13.35/5.44 import qualified FiniteMap; 13.35/5.44 import qualified Main; 13.35/5.44 import qualified Prelude; 13.35/5.44 } 13.35/5.44 module Main where { 13.35/5.44 import qualified FiniteMap; 13.35/5.44 import qualified Maybe; 13.35/5.44 import qualified Prelude; 13.35/5.44 } 13.35/5.44 13.35/5.44 ---------------------------------------- 13.35/5.44 13.35/5.44 (7) COR (EQUIVALENT) 13.35/5.44 Cond Reductions: 13.35/5.44 The following Function with conditions 13.35/5.44 "undefined |Falseundefined; 13.35/5.44 " 13.35/5.44 is transformed to 13.35/5.44 "undefined = undefined1; 13.35/5.44 " 13.35/5.44 "undefined0 True = undefined; 13.35/5.44 " 13.35/5.44 "undefined1 = undefined0 False; 13.35/5.44 " 13.35/5.44 The following Function with conditions 13.35/5.44 "addToFM_C combiner EmptyFM key elt = unitFM key elt; 13.35/5.44 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; 13.35/5.44 " 13.35/5.44 is transformed to 13.35/5.44 "addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 13.35/5.44 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; 13.35/5.44 " 13.35/5.44 "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; 13.35/5.44 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); 13.35/5.44 " 13.35/5.44 "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; 13.35/5.44 " 13.35/5.44 "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); 13.35/5.44 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; 13.35/5.44 " 13.35/5.44 "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); 13.35/5.44 " 13.35/5.44 "addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 13.35/5.44 addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu; 13.35/5.44 " 13.35/5.44 The following Function with conditions 13.35/5.44 "mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R; 13.35/5.44 " 13.35/5.44 is transformed to 13.35/5.44 "mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr); 13.35/5.44 " 13.35/5.44 "mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R; 13.35/5.44 " 13.35/5.44 "mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R; 13.35/5.44 mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise; 13.35/5.44 " 13.35/5.44 "mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 13.35/5.44 " 13.35/5.44 The following Function with conditions 13.35/5.44 "mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R; 13.35/5.44 " 13.35/5.44 is transformed to 13.35/5.44 "mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr); 13.35/5.44 " 13.35/5.44 "mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R; 13.35/5.44 mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise; 13.35/5.44 " 13.35/5.44 "mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R; 13.35/5.44 " 13.35/5.44 "mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 13.35/5.44 " 13.35/5.44 The following Function with conditions 13.35/5.44 "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 { 13.35/5.44 double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu 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); 13.35/5.44 ; 13.35/5.44 double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv 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); 13.35/5.44 ; 13.35/5.44 mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr)|sizeFM fm_rl < 2 * sizeFM fm_rrsingle_L fm_L fm_R|otherwisedouble_L fm_L fm_R; 13.35/5.44 ; 13.35/5.44 mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr)|sizeFM fm_lr < 2 * sizeFM fm_llsingle_R fm_L fm_R|otherwisedouble_R fm_L fm_R; 13.35/5.44 ; 13.35/5.44 single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 13.35/5.44 ; 13.35/5.44 single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 13.35/5.44 ; 13.35/5.44 size_l = sizeFM fm_L; 13.35/5.44 ; 13.35/5.44 size_r = sizeFM fm_R; 13.35/5.44 } 13.35/5.44 ; 13.35/5.44 " 13.35/5.44 is transformed to 13.35/5.44 "mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 13.35/5.44 " 13.35/5.44 "mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 13.35/5.44 double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu 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); 13.35/5.44 ; 13.35/5.44 double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv 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); 13.35/5.44 ; 13.35/5.44 mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr); 13.35/5.44 ; 13.35/5.44 mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R; 13.35/5.44 ; 13.35/5.44 mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R; 13.35/5.44 mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise; 13.35/5.44 ; 13.35/5.44 mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 13.35/5.44 ; 13.35/5.44 mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr); 13.35/5.44 ; 13.35/5.44 mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R; 13.35/5.44 ; 13.35/5.44 mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R; 13.35/5.44 mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise; 13.35/5.44 ; 13.35/5.44 mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 13.35/5.44 ; 13.35/5.44 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 13.35/5.44 ; 13.35/5.44 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 13.35/5.44 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 13.35/5.44 ; 13.35/5.44 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 13.35/5.44 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 13.35/5.44 ; 13.35/5.44 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 13.35/5.44 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 13.35/5.44 ; 13.35/5.44 single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 13.71/5.46 ; 13.71/5.46 single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 13.71/5.46 ; 13.71/5.46 size_l = sizeFM fm_L; 13.71/5.46 ; 13.71/5.46 size_r = sizeFM fm_R; 13.71/5.46 } 13.71/5.46 ; 13.71/5.46 " 13.71/5.46 13.71/5.46 ---------------------------------------- 13.71/5.46 13.71/5.46 (8) 13.71/5.46 Obligation: 13.71/5.46 mainModule Main 13.71/5.46 module FiniteMap where { 13.71/5.46 import qualified Main; 13.71/5.46 import qualified Maybe; 13.71/5.46 import qualified Prelude; 13.71/5.46 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 13.71/5.46 13.71/5.46 instance (Eq a, Eq b) => Eq FiniteMap a b where { 13.71/5.46 } 13.71/5.46 addListToFM :: Ord a => FiniteMap a b -> [(a,b)] -> FiniteMap a b; 13.71/5.46 addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs; 13.71/5.46 13.71/5.46 addListToFM0 old new = new; 13.71/5.46 13.71/5.46 addListToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.71/5.46 addListToFM_C combiner fm key_elt_pairs = foldl add fm key_elt_pairs where { 13.71/5.46 add fmap (key,elt) = addToFM_C combiner fmap key elt; 13.71/5.46 }; 13.71/5.46 13.71/5.46 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 13.71/5.47 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 13.71/5.47 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; 13.71/5.47 13.71/5.47 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; 13.71/5.47 13.71/5.47 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); 13.71/5.47 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; 13.71/5.47 13.71/5.47 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; 13.71/5.47 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); 13.71/5.47 13.71/5.47 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); 13.71/5.47 13.71/5.47 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 13.71/5.47 addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu; 13.71/5.47 13.71/5.47 emptyFM :: FiniteMap a b; 13.71/5.47 emptyFM = EmptyFM; 13.71/5.47 13.71/5.47 findMax :: FiniteMap a b -> (a,b); 13.71/5.47 findMax (Branch key elt xv xw EmptyFM) = (key,elt); 13.71/5.47 findMax (Branch key elt xx xy fm_r) = findMax fm_r; 13.71/5.47 13.71/5.47 findMin :: FiniteMap a b -> (a,b); 13.71/5.47 findMin (Branch key elt vux EmptyFM vuy) = (key,elt); 13.71/5.47 findMin (Branch key elt vuz fm_l vvu) = findMin fm_l; 13.71/5.47 13.71/5.47 listToFM :: Ord b => [(b,a)] -> FiniteMap b a; 13.71/5.47 listToFM = addListToFM emptyFM; 13.71/5.47 13.71/5.47 mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 13.71/5.47 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6 key elt fm_L fm_R = mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 13.71/5.47 double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu 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); 13.71/5.47 double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv 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); 13.71/5.47 mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr); 13.71/5.47 mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R; 13.71/5.47 mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R; 13.71/5.47 mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise; 13.71/5.47 mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 13.71/5.47 mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr); 13.71/5.47 mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R; 13.71/5.47 mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R; 13.71/5.47 mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise; 13.71/5.47 mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 13.71/5.47 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 13.71/5.47 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 13.71/5.47 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 13.71/5.47 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 13.71/5.47 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 13.71/5.47 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 13.71/5.47 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 13.71/5.47 single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 13.71/5.47 single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 13.71/5.47 size_l = sizeFM fm_L; 13.71/5.47 size_r = sizeFM fm_R; 13.71/5.47 }; 13.71/5.47 13.71/5.47 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 13.71/5.47 mkBranch which key elt fm_l fm_r = let { 13.71/5.47 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 13.71/5.47 } in result where { 13.71/5.47 balance_ok = True; 13.71/5.47 left_ok = left_ok0 fm_l key fm_l; 13.71/5.47 left_ok0 fm_l key EmptyFM = True; 13.71/5.47 left_ok0 fm_l key (Branch left_key vz wu wv ww) = let { 13.71/5.47 biggest_left_key = fst (findMax fm_l); 13.71/5.47 } in biggest_left_key < key; 13.71/5.47 left_size = sizeFM fm_l; 13.71/5.47 right_ok = right_ok0 fm_r key fm_r; 13.71/5.47 right_ok0 fm_r key EmptyFM = True; 13.71/5.47 right_ok0 fm_r key (Branch right_key wx wy wz xu) = let { 13.71/5.47 smallest_right_key = fst (findMin fm_r); 13.71/5.47 } in key < smallest_right_key; 13.71/5.47 right_size = sizeFM fm_r; 13.71/5.47 unbox :: Int -> Int; 13.71/5.47 unbox x = x; 13.71/5.47 }; 13.71/5.47 13.71/5.47 sIZE_RATIO :: Int; 13.71/5.47 sIZE_RATIO = 5; 13.71/5.47 13.71/5.47 sizeFM :: FiniteMap a b -> Int; 13.71/5.47 sizeFM EmptyFM = 0; 13.71/5.47 sizeFM (Branch zz vuu size vuv vuw) = size; 13.71/5.47 13.71/5.47 unitFM :: b -> a -> FiniteMap b a; 13.71/5.47 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 13.71/5.47 13.71/5.47 } 13.71/5.47 module Maybe where { 13.71/5.47 import qualified FiniteMap; 13.71/5.47 import qualified Main; 13.71/5.47 import qualified Prelude; 13.71/5.47 } 13.71/5.47 module Main where { 13.71/5.47 import qualified FiniteMap; 13.71/5.47 import qualified Maybe; 13.71/5.47 import qualified Prelude; 13.71/5.47 } 13.71/5.47 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (9) LetRed (EQUIVALENT) 13.71/5.47 Let/Where Reductions: 13.71/5.47 The bindings of the following Let/Where expression 13.71/5.47 "mkBalBranch5 key elt fm_L fm_R (size_l + size_r < 2) where { 13.71/5.47 double_L fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu 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); 13.71/5.47 ; 13.71/5.47 double_R (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv 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); 13.71/5.47 ; 13.71/5.47 mkBalBranch0 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr); 13.71/5.47 ; 13.71/5.47 mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr True = double_L fm_L fm_R; 13.71/5.47 ; 13.71/5.47 mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr True = single_L fm_L fm_R; 13.71/5.47 mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch00 fm_L fm_R zv zw zx fm_rl fm_rr otherwise; 13.71/5.47 ; 13.71/5.47 mkBalBranch02 fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch01 fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 13.71/5.47 ; 13.71/5.47 mkBalBranch1 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr); 13.71/5.47 ; 13.71/5.47 mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr True = double_R fm_L fm_R; 13.71/5.47 ; 13.71/5.47 mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr True = single_R fm_L fm_R; 13.71/5.47 mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch10 fm_L fm_R yw yx yy fm_ll fm_lr otherwise; 13.71/5.47 ; 13.71/5.47 mkBalBranch12 fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch11 fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 13.71/5.47 ; 13.71/5.47 mkBalBranch2 key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 13.71/5.47 ; 13.71/5.47 mkBalBranch3 key elt fm_L fm_R True = mkBalBranch1 fm_L fm_R fm_L; 13.71/5.47 mkBalBranch3 key elt fm_L fm_R False = mkBalBranch2 key elt fm_L fm_R otherwise; 13.71/5.47 ; 13.71/5.47 mkBalBranch4 key elt fm_L fm_R True = mkBalBranch0 fm_L fm_R fm_R; 13.71/5.47 mkBalBranch4 key elt fm_L fm_R False = mkBalBranch3 key elt fm_L fm_R (size_l > sIZE_RATIO * size_r); 13.71/5.47 ; 13.71/5.47 mkBalBranch5 key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 13.71/5.47 mkBalBranch5 key elt fm_L fm_R False = mkBalBranch4 key elt fm_L fm_R (size_r > sIZE_RATIO * size_l); 13.71/5.47 ; 13.71/5.47 single_L fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 key elt fm_l fm_rl) fm_rr; 13.71/5.47 ; 13.71/5.47 single_R (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 key elt fm_lr fm_r); 13.71/5.47 ; 13.71/5.47 size_l = sizeFM fm_L; 13.71/5.47 ; 13.71/5.47 size_r = sizeFM fm_R; 13.71/5.47 } 13.71/5.47 " 13.71/5.47 are unpacked to the following functions on top level 13.71/5.47 "mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R; 13.71/5.47 mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu); 13.71/5.47 " 13.71/5.47 "mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwx; 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 13.71/5.47 " 13.71/5.47 "mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwy vwz fm_lr fm_r); 13.71/5.47 " 13.71/5.47 "mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vxu; 13.71/5.47 " 13.71/5.47 "mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vwy vwz fm_lrr fm_r); 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise; 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr); 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu); 13.71/5.47 " 13.71/5.47 "mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vwy vwz fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr); 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 13.71/5.47 " 13.71/5.47 "mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwy vwz fm_l fm_rl) fm_rr; 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr); 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L; 13.71/5.47 mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise; 13.71/5.47 " 13.71/5.47 "mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise; 13.71/5.47 " 13.71/5.47 The bindings of the following Let/Where expression 13.71/5.47 "foldl add fm key_elt_pairs where { 13.71/5.47 add fmap (key,elt) = addToFM_C combiner fmap key elt; 13.71/5.47 } 13.71/5.47 " 13.71/5.47 are unpacked to the following functions on top level 13.71/5.47 "addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt; 13.71/5.47 " 13.71/5.47 The bindings of the following Let/Where expression 13.71/5.47 "let { 13.71/5.47 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 13.71/5.47 } in result where { 13.71/5.47 balance_ok = True; 13.71/5.47 ; 13.71/5.47 left_ok = left_ok0 fm_l key fm_l; 13.71/5.47 ; 13.71/5.47 left_ok0 fm_l key EmptyFM = True; 13.71/5.47 left_ok0 fm_l key (Branch left_key vz wu wv ww) = let { 13.71/5.47 biggest_left_key = fst (findMax fm_l); 13.71/5.47 } in biggest_left_key < key; 13.71/5.47 ; 13.71/5.47 left_size = sizeFM fm_l; 13.71/5.47 ; 13.71/5.47 right_ok = right_ok0 fm_r key fm_r; 13.71/5.47 ; 13.71/5.47 right_ok0 fm_r key EmptyFM = True; 13.71/5.47 right_ok0 fm_r key (Branch right_key wx wy wz xu) = let { 13.71/5.47 smallest_right_key = fst (findMin fm_r); 13.71/5.47 } in key < smallest_right_key; 13.71/5.47 ; 13.71/5.47 right_size = sizeFM fm_r; 13.71/5.47 ; 13.71/5.47 unbox x = x; 13.71/5.47 } 13.71/5.47 " 13.71/5.47 are unpacked to the following functions on top level 13.71/5.47 "mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxx vxw; 13.71/5.47 " 13.71/5.47 "mkBranchUnbox vxw vxx vxy x = x; 13.71/5.47 " 13.71/5.47 "mkBranchLeft_size vxw vxx vxy = sizeFM vxw; 13.71/5.47 " 13.71/5.47 "mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True; 13.71/5.47 mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 13.71/5.47 " 13.71/5.47 "mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxy vxx vxy; 13.71/5.47 " 13.71/5.47 "mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True; 13.71/5.47 mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r; 13.71/5.47 " 13.71/5.47 "mkBranchBalance_ok vxw vxx vxy = True; 13.71/5.47 " 13.71/5.47 "mkBranchRight_size vxw vxx vxy = sizeFM vxy; 13.71/5.47 " 13.71/5.47 The bindings of the following Let/Where expression 13.71/5.47 "let { 13.71/5.47 result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; 13.71/5.47 } in result" 13.71/5.47 are unpacked to the following functions on top level 13.71/5.47 "mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vxz vyw (1 + mkBranchLeft_size vyv vxz vyw + mkBranchRight_size vyv vxz vyw)) vyv vyw; 13.71/5.47 " 13.71/5.47 The bindings of the following Let/Where expression 13.71/5.47 "let { 13.71/5.47 biggest_left_key = fst (findMax fm_l); 13.71/5.47 } in biggest_left_key < key" 13.71/5.47 are unpacked to the following functions on top level 13.71/5.47 "mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx); 13.71/5.47 " 13.71/5.47 The bindings of the following Let/Where expression 13.71/5.47 "let { 13.71/5.47 smallest_right_key = fst (findMin fm_r); 13.71/5.47 } in key < smallest_right_key" 13.71/5.47 are unpacked to the following functions on top level 13.71/5.47 "mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy); 13.71/5.47 " 13.71/5.47 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (10) 13.71/5.47 Obligation: 13.71/5.47 mainModule Main 13.71/5.47 module FiniteMap where { 13.71/5.47 import qualified Main; 13.71/5.47 import qualified Maybe; 13.71/5.47 import qualified Prelude; 13.71/5.47 data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; 13.71/5.47 13.71/5.47 instance (Eq a, Eq b) => Eq FiniteMap a b where { 13.71/5.47 } 13.71/5.47 addListToFM :: Ord b => FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.71/5.47 addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs; 13.71/5.47 13.71/5.47 addListToFM0 old new = new; 13.71/5.47 13.71/5.47 addListToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.71/5.47 addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs; 13.71/5.47 13.71/5.47 addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt; 13.71/5.47 13.71/5.47 addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; 13.71/5.47 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 13.71/5.47 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; 13.71/5.47 13.71/5.47 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; 13.71/5.47 13.71/5.47 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); 13.71/5.47 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; 13.71/5.47 13.71/5.47 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; 13.71/5.47 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); 13.71/5.47 13.71/5.47 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); 13.71/5.47 13.71/5.47 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 13.71/5.47 addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu; 13.71/5.47 13.71/5.47 emptyFM :: FiniteMap a b; 13.71/5.47 emptyFM = EmptyFM; 13.71/5.47 13.71/5.47 findMax :: FiniteMap a b -> (a,b); 13.71/5.47 findMax (Branch key elt xv xw EmptyFM) = (key,elt); 13.71/5.47 findMax (Branch key elt xx xy fm_r) = findMax fm_r; 13.71/5.47 13.71/5.47 findMin :: FiniteMap a b -> (a,b); 13.71/5.47 findMin (Branch key elt vux EmptyFM vuy) = (key,elt); 13.71/5.47 findMin (Branch key elt vuz fm_l vvu) = findMin fm_l; 13.71/5.47 13.71/5.47 listToFM :: Ord a => [(a,b)] -> FiniteMap a b; 13.71/5.47 listToFM = addListToFM emptyFM; 13.71/5.47 13.71/5.47 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.71/5.47 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 fm_L key elt fm_R key elt fm_L fm_R (mkBalBranch6Size_l fm_L key elt fm_R + mkBalBranch6Size_r fm_L key elt fm_R < 2); 13.71/5.47 13.71/5.47 mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch 5 key_rl elt_rl (mkBranch 6 vwy vwz fm_l fm_rll) (mkBranch 7 key_r elt_r fm_rlr fm_rr); 13.71/5.47 13.71/5.47 mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch 10 key_lr elt_lr (mkBranch 11 key_l elt_l fm_ll fm_lrl) (mkBranch 12 vwy vwz fm_lrr fm_r); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < 2 * sizeFM fm_rr); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < 2 * sizeFM fm_ll); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 2 key elt fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L; 13.71/5.47 mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R; 13.71/5.47 mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch 1 key elt fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu); 13.71/5.47 13.71/5.47 mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch 3 key_r elt_r (mkBranch 4 vwy vwz fm_l fm_rl) fm_rr; 13.71/5.47 13.71/5.47 mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch 8 key_l elt_l fm_ll (mkBranch 9 vwy vwz fm_lr fm_r); 13.71/5.47 13.71/5.47 mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwx; 13.71/5.47 13.71/5.47 mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vxu; 13.71/5.47 13.71/5.47 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 13.71/5.47 mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r; 13.71/5.47 13.71/5.47 mkBranchBalance_ok vxw vxx vxy = True; 13.71/5.47 13.71/5.47 mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxx vxw; 13.71/5.47 13.71/5.47 mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True; 13.71/5.47 mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 13.71/5.47 13.71/5.47 mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx); 13.71/5.47 13.71/5.47 mkBranchLeft_size vxw vxx vxy = sizeFM vxw; 13.71/5.47 13.71/5.47 mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vxz vyw (1 + mkBranchLeft_size vyv vxz vyw + mkBranchRight_size vyv vxz vyw)) vyv vyw; 13.71/5.47 13.71/5.47 mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxy vxx vxy; 13.71/5.47 13.71/5.47 mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True; 13.71/5.47 mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r; 13.71/5.47 13.71/5.47 mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy); 13.71/5.47 13.71/5.47 mkBranchRight_size vxw vxx vxy = sizeFM vxy; 13.71/5.47 13.71/5.47 mkBranchUnbox :: Ord a => -> (FiniteMap a b) ( -> a ( -> (FiniteMap a b) (Int -> Int))); 13.71/5.47 mkBranchUnbox vxw vxx vxy x = x; 13.71/5.47 13.71/5.47 sIZE_RATIO :: Int; 13.71/5.47 sIZE_RATIO = 5; 13.71/5.47 13.71/5.47 sizeFM :: FiniteMap b a -> Int; 13.71/5.47 sizeFM EmptyFM = 0; 13.71/5.47 sizeFM (Branch zz vuu size vuv vuw) = size; 13.71/5.47 13.71/5.47 unitFM :: a -> b -> FiniteMap a b; 13.71/5.47 unitFM key elt = Branch key elt 1 emptyFM emptyFM; 13.71/5.47 13.71/5.47 } 13.71/5.47 module Maybe where { 13.71/5.47 import qualified FiniteMap; 13.71/5.47 import qualified Main; 13.71/5.47 import qualified Prelude; 13.71/5.47 } 13.71/5.47 module Main where { 13.71/5.47 import qualified FiniteMap; 13.71/5.47 import qualified Maybe; 13.71/5.47 import qualified Prelude; 13.71/5.47 } 13.71/5.47 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (11) NumRed (SOUND) 13.71/5.47 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (12) 13.71/5.47 Obligation: 13.71/5.47 mainModule Main 13.71/5.47 module FiniteMap where { 13.71/5.47 import qualified Main; 13.71/5.47 import qualified Maybe; 13.71/5.47 import qualified Prelude; 13.71/5.47 data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; 13.71/5.47 13.71/5.47 instance (Eq a, Eq b) => Eq FiniteMap a b where { 13.71/5.47 } 13.71/5.47 addListToFM :: Ord b => FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.71/5.47 addListToFM fm key_elt_pairs = addListToFM_C addListToFM0 fm key_elt_pairs; 13.71/5.47 13.71/5.47 addListToFM0 old new = new; 13.71/5.47 13.71/5.47 addListToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> [(b,a)] -> FiniteMap b a; 13.71/5.47 addListToFM_C combiner fm key_elt_pairs = foldl (addListToFM_CAdd combiner) fm key_elt_pairs; 13.71/5.47 13.71/5.47 addListToFM_CAdd vxv fmap (key,elt) = addToFM_C vxv fmap key elt; 13.71/5.47 13.71/5.47 addToFM_C :: Ord a => (b -> b -> b) -> FiniteMap a b -> a -> b -> FiniteMap a b; 13.71/5.47 addToFM_C combiner EmptyFM key elt = addToFM_C4 combiner EmptyFM key elt; 13.71/5.47 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; 13.71/5.47 13.71/5.47 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; 13.71/5.47 13.71/5.47 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); 13.71/5.47 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; 13.71/5.47 13.71/5.47 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; 13.71/5.47 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); 13.71/5.47 13.71/5.47 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); 13.71/5.47 13.71/5.47 addToFM_C4 combiner EmptyFM key elt = unitFM key elt; 13.71/5.47 addToFM_C4 vvx vvy vvz vwu = addToFM_C3 vvx vvy vvz vwu; 13.71/5.47 13.71/5.47 emptyFM :: FiniteMap a b; 13.71/5.47 emptyFM = EmptyFM; 13.71/5.47 13.71/5.47 findMax :: FiniteMap a b -> (a,b); 13.71/5.47 findMax (Branch key elt xv xw EmptyFM) = (key,elt); 13.71/5.47 findMax (Branch key elt xx xy fm_r) = findMax fm_r; 13.71/5.47 13.71/5.47 findMin :: FiniteMap b a -> (b,a); 13.71/5.47 findMin (Branch key elt vux EmptyFM vuy) = (key,elt); 13.71/5.47 findMin (Branch key elt vuz fm_l vvu) = findMin fm_l; 13.71/5.47 13.71/5.47 listToFM :: Ord a => [(a,b)] -> FiniteMap a b; 13.71/5.47 listToFM = addListToFM emptyFM; 13.71/5.47 13.71/5.47 mkBalBranch :: Ord b => b -> a -> FiniteMap b a -> FiniteMap b a -> FiniteMap b a; 13.71/5.47 mkBalBranch key elt fm_L fm_R = mkBalBranch6 key elt fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6 key elt fm_L fm_R = mkBalBranch6MkBalBranch5 fm_L key elt fm_R key elt fm_L fm_R (mkBalBranch6Size_l fm_L key elt fm_R + mkBalBranch6Size_r fm_L key elt fm_R < Pos (Succ (Succ Zero))); 13.71/5.47 13.71/5.47 mkBalBranch6Double_L vwx vwy vwz vxu fm_l (Branch key_r elt_r yz (Branch key_rl elt_rl zu fm_rll fm_rlr) fm_rr) = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ Zero)))))) key_rl elt_rl (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))) vwy vwz fm_l fm_rll) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))) key_r elt_r fm_rlr fm_rr); 13.71/5.47 13.71/5.47 mkBalBranch6Double_R vwx vwy vwz vxu (Branch key_l elt_l yu fm_ll (Branch key_lr elt_lr yv fm_lrl fm_lrr)) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))) key_lr elt_lr (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))))) key_l elt_l fm_ll fm_lrl) (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))))))) vwy vwz fm_lrr fm_r); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Double_L vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr True = mkBalBranch6Single_L vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr False = mkBalBranch6MkBalBranch00 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr otherwise; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch02 vwx vwy vwz vxu fm_L fm_R (Branch zv zw zx fm_rl fm_rr) = mkBalBranch6MkBalBranch01 vwx vwy vwz vxu fm_L fm_R zv zw zx fm_rl fm_rr (sizeFM fm_rl < Pos (Succ (Succ Zero)) * sizeFM fm_rr); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Double_R vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr True = mkBalBranch6Single_R vwx vwy vwz vxu fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr False = mkBalBranch6MkBalBranch10 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr otherwise; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch12 vwx vwy vwz vxu fm_L fm_R (Branch yw yx yy fm_ll fm_lr) = mkBalBranch6MkBalBranch11 vwx vwy vwz vxu fm_L fm_R yw yx yy fm_ll fm_lr (sizeFM fm_lr < Pos (Succ (Succ Zero)) * sizeFM fm_ll); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ (Succ Zero))) key elt fm_L fm_R; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch1 vwx vwy vwz vxu fm_L fm_R fm_L; 13.71/5.47 mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch2 vwx vwy vwz vxu key elt fm_L fm_R otherwise; 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R True = mkBalBranch6MkBalBranch0 vwx vwy vwz vxu fm_L fm_R fm_R; 13.71/5.47 mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch3 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_l vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_r vwx vwy vwz vxu); 13.71/5.47 13.71/5.47 mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R True = mkBranch (Pos (Succ Zero)) key elt fm_L fm_R; 13.71/5.47 mkBalBranch6MkBalBranch5 vwx vwy vwz vxu key elt fm_L fm_R False = mkBalBranch6MkBalBranch4 vwx vwy vwz vxu key elt fm_L fm_R (mkBalBranch6Size_r vwx vwy vwz vxu > sIZE_RATIO * mkBalBranch6Size_l vwx vwy vwz vxu); 13.71/5.47 13.71/5.47 mkBalBranch6Single_L vwx vwy vwz vxu fm_l (Branch key_r elt_r zy fm_rl fm_rr) = mkBranch (Pos (Succ (Succ (Succ Zero)))) key_r elt_r (mkBranch (Pos (Succ (Succ (Succ (Succ Zero))))) vwy vwz fm_l fm_rl) fm_rr; 13.71/5.47 13.71/5.47 mkBalBranch6Single_R vwx vwy vwz vxu (Branch key_l elt_l xz fm_ll fm_lr) fm_r = mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero))))))))) key_l elt_l fm_ll (mkBranch (Pos (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ (Succ Zero)))))))))) vwy vwz fm_lr fm_r); 13.71/5.47 13.71/5.47 mkBalBranch6Size_l vwx vwy vwz vxu = sizeFM vwx; 13.71/5.47 13.71/5.47 mkBalBranch6Size_r vwx vwy vwz vxu = sizeFM vxu; 13.71/5.47 13.71/5.47 mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; 13.71/5.47 mkBranch which key elt fm_l fm_r = mkBranchResult key elt fm_l fm_r; 13.71/5.47 13.71/5.47 mkBranchBalance_ok vxw vxx vxy = True; 13.71/5.47 13.71/5.47 mkBranchLeft_ok vxw vxx vxy = mkBranchLeft_ok0 vxw vxx vxy vxw vxx vxw; 13.71/5.47 13.71/5.47 mkBranchLeft_ok0 vxw vxx vxy fm_l key EmptyFM = True; 13.71/5.47 mkBranchLeft_ok0 vxw vxx vxy fm_l key (Branch left_key vz wu wv ww) = mkBranchLeft_ok0Biggest_left_key fm_l < key; 13.71/5.47 13.71/5.47 mkBranchLeft_ok0Biggest_left_key vyx = fst (findMax vyx); 13.71/5.47 13.71/5.47 mkBranchLeft_size vxw vxx vxy = sizeFM vxw; 13.71/5.47 13.71/5.47 mkBranchResult vxz vyu vyv vyw = Branch vxz vyu (mkBranchUnbox vyv vxz vyw (Pos (Succ Zero) + mkBranchLeft_size vyv vxz vyw + mkBranchRight_size vyv vxz vyw)) vyv vyw; 13.71/5.47 13.71/5.47 mkBranchRight_ok vxw vxx vxy = mkBranchRight_ok0 vxw vxx vxy vxy vxx vxy; 13.71/5.47 13.71/5.47 mkBranchRight_ok0 vxw vxx vxy fm_r key EmptyFM = True; 13.71/5.47 mkBranchRight_ok0 vxw vxx vxy fm_r key (Branch right_key wx wy wz xu) = key < mkBranchRight_ok0Smallest_right_key fm_r; 13.71/5.47 13.71/5.47 mkBranchRight_ok0Smallest_right_key vyy = fst (findMin vyy); 13.71/5.47 13.71/5.47 mkBranchRight_size vxw vxx vxy = sizeFM vxy; 13.71/5.47 13.71/5.47 mkBranchUnbox :: Ord a => -> (FiniteMap a b) ( -> a ( -> (FiniteMap a b) (Int -> Int))); 13.71/5.47 mkBranchUnbox vxw vxx vxy x = x; 13.71/5.47 13.71/5.47 sIZE_RATIO :: Int; 13.71/5.47 sIZE_RATIO = Pos (Succ (Succ (Succ (Succ (Succ Zero))))); 13.71/5.47 13.71/5.47 sizeFM :: FiniteMap a b -> Int; 13.71/5.47 sizeFM EmptyFM = Pos Zero; 13.71/5.47 sizeFM (Branch zz vuu size vuv vuw) = size; 13.71/5.47 13.71/5.47 unitFM :: a -> b -> FiniteMap a b; 13.71/5.47 unitFM key elt = Branch key elt (Pos (Succ Zero)) emptyFM emptyFM; 13.71/5.47 13.71/5.47 } 13.71/5.47 module Maybe where { 13.71/5.47 import qualified FiniteMap; 13.71/5.47 import qualified Main; 13.71/5.47 import qualified Prelude; 13.71/5.47 } 13.71/5.47 module Main where { 13.71/5.47 import qualified FiniteMap; 13.71/5.47 import qualified Maybe; 13.71/5.47 import qualified Prelude; 13.71/5.47 } 13.71/5.47 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (13) Narrow (SOUND) 13.71/5.47 Haskell To QDPs 13.71/5.47 13.71/5.47 digraph dp_graph { 13.71/5.47 node [outthreshold=100, inthreshold=100];1[label="FiniteMap.listToFM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 13.71/5.47 3[label="FiniteMap.listToFM vyz3",fontsize=16,color="black",shape="triangle"];3 -> 4[label="",style="solid", color="black", weight=3]; 13.71/5.47 4[label="FiniteMap.addListToFM FiniteMap.emptyFM vyz3",fontsize=16,color="black",shape="box"];4 -> 5[label="",style="solid", color="black", weight=3]; 13.71/5.47 5[label="FiniteMap.addListToFM_C FiniteMap.addListToFM0 FiniteMap.emptyFM vyz3",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 13.71/5.47 6 -> 20[label="",style="dashed", color="red", weight=0]; 13.71/5.47 6[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) FiniteMap.emptyFM vyz3",fontsize=16,color="magenta"];6 -> 21[label="",style="dashed", color="magenta", weight=3]; 13.71/5.47 6 -> 22[label="",style="dashed", color="magenta", weight=3]; 13.71/5.47 21[label="vyz3",fontsize=16,color="green",shape="box"];22[label="FiniteMap.emptyFM",fontsize=16,color="black",shape="triangle"];22 -> 27[label="",style="solid", color="black", weight=3]; 13.71/5.47 20[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz6 vyz311",fontsize=16,color="burlywood",shape="triangle"];59[label="vyz311/vyz3110 : vyz3111",fontsize=10,color="white",style="solid",shape="box"];20 -> 59[label="",style="solid", color="burlywood", weight=9]; 13.71/5.47 59 -> 28[label="",style="solid", color="burlywood", weight=3]; 13.71/5.47 60[label="vyz311/[]",fontsize=10,color="white",style="solid",shape="box"];20 -> 60[label="",style="solid", color="burlywood", weight=9]; 13.71/5.47 60 -> 29[label="",style="solid", color="burlywood", weight=3]; 13.71/5.47 27[label="FiniteMap.EmptyFM",fontsize=16,color="green",shape="box"];28[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz6 (vyz3110 : vyz3111)",fontsize=16,color="black",shape="box"];28 -> 30[label="",style="solid", color="black", weight=3]; 13.71/5.47 29[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) vyz6 []",fontsize=16,color="black",shape="box"];29 -> 31[label="",style="solid", color="black", weight=3]; 13.71/5.47 30 -> 20[label="",style="dashed", color="red", weight=0]; 13.71/5.47 30[label="foldl (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0) (FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz6 vyz3110) vyz3111",fontsize=16,color="magenta"];30 -> 32[label="",style="dashed", color="magenta", weight=3]; 13.71/5.47 30 -> 33[label="",style="dashed", color="magenta", weight=3]; 13.71/5.47 31[label="vyz6",fontsize=16,color="green",shape="box"];32[label="vyz3111",fontsize=16,color="green",shape="box"];33[label="FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz6 vyz3110",fontsize=16,color="burlywood",shape="box"];61[label="vyz3110/(vyz31100,vyz31101)",fontsize=10,color="white",style="solid",shape="box"];33 -> 61[label="",style="solid", color="burlywood", weight=9]; 13.71/5.47 61 -> 34[label="",style="solid", color="burlywood", weight=3]; 13.71/5.47 34[label="FiniteMap.addListToFM_CAdd FiniteMap.addListToFM0 vyz6 (vyz31100,vyz31101)",fontsize=16,color="black",shape="box"];34 -> 35[label="",style="solid", color="black", weight=3]; 13.71/5.47 35[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 vyz6 vyz31100 vyz31101",fontsize=16,color="burlywood",shape="box"];62[label="vyz6/FiniteMap.EmptyFM",fontsize=10,color="white",style="solid",shape="box"];35 -> 62[label="",style="solid", color="burlywood", weight=9]; 13.71/5.47 62 -> 36[label="",style="solid", color="burlywood", weight=3]; 13.71/5.47 63[label="vyz6/FiniteMap.Branch vyz60 vyz61 vyz62 vyz63 vyz64",fontsize=10,color="white",style="solid",shape="box"];35 -> 63[label="",style="solid", color="burlywood", weight=9]; 13.71/5.47 63 -> 37[label="",style="solid", color="burlywood", weight=3]; 13.71/5.47 36[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 FiniteMap.EmptyFM vyz31100 vyz31101",fontsize=16,color="black",shape="box"];36 -> 38[label="",style="solid", color="black", weight=3]; 13.71/5.47 37[label="FiniteMap.addToFM_C FiniteMap.addListToFM0 (FiniteMap.Branch vyz60 vyz61 vyz62 vyz63 vyz64) vyz31100 vyz31101",fontsize=16,color="black",shape="box"];37 -> 39[label="",style="solid", color="black", weight=3]; 13.71/5.47 38[label="FiniteMap.addToFM_C4 FiniteMap.addListToFM0 FiniteMap.EmptyFM vyz31100 vyz31101",fontsize=16,color="black",shape="box"];38 -> 40[label="",style="solid", color="black", weight=3]; 13.71/5.47 39[label="FiniteMap.addToFM_C3 FiniteMap.addListToFM0 (FiniteMap.Branch vyz60 vyz61 vyz62 vyz63 vyz64) vyz31100 vyz31101",fontsize=16,color="black",shape="box"];39 -> 41[label="",style="solid", color="black", weight=3]; 13.71/5.47 40[label="FiniteMap.unitFM vyz31100 vyz31101",fontsize=16,color="black",shape="box"];40 -> 42[label="",style="solid", color="black", weight=3]; 13.71/5.47 41[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz60 vyz61 vyz62 vyz63 vyz64 vyz31100 vyz31101 (vyz31100 < vyz60)",fontsize=16,color="black",shape="box"];41 -> 43[label="",style="solid", color="black", weight=3]; 13.71/5.47 42[label="FiniteMap.Branch vyz31100 vyz31101 (Pos (Succ Zero)) FiniteMap.emptyFM FiniteMap.emptyFM",fontsize=16,color="green",shape="box"];42 -> 44[label="",style="dashed", color="green", weight=3]; 13.71/5.47 42 -> 45[label="",style="dashed", color="green", weight=3]; 13.71/5.47 43[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz60 vyz61 vyz62 vyz63 vyz64 vyz31100 vyz31101 (compare vyz31100 vyz60 == LT)",fontsize=16,color="burlywood",shape="box"];64[label="vyz31100/()",fontsize=10,color="white",style="solid",shape="box"];43 -> 64[label="",style="solid", color="burlywood", weight=9]; 13.71/5.47 64 -> 46[label="",style="solid", color="burlywood", weight=3]; 13.71/5.47 44 -> 22[label="",style="dashed", color="red", weight=0]; 13.71/5.47 44[label="FiniteMap.emptyFM",fontsize=16,color="magenta"];45 -> 22[label="",style="dashed", color="red", weight=0]; 13.71/5.47 45[label="FiniteMap.emptyFM",fontsize=16,color="magenta"];46[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 vyz60 vyz61 vyz62 vyz63 vyz64 () vyz31101 (compare () vyz60 == LT)",fontsize=16,color="burlywood",shape="box"];65[label="vyz60/()",fontsize=10,color="white",style="solid",shape="box"];46 -> 65[label="",style="solid", color="burlywood", weight=9]; 13.71/5.47 65 -> 47[label="",style="solid", color="burlywood", weight=3]; 13.71/5.47 47[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (compare () () == LT)",fontsize=16,color="black",shape="box"];47 -> 48[label="",style="solid", color="black", weight=3]; 13.71/5.47 48[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (EQ == LT)",fontsize=16,color="black",shape="box"];48 -> 49[label="",style="solid", color="black", weight=3]; 13.71/5.47 49[label="FiniteMap.addToFM_C2 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 False",fontsize=16,color="black",shape="box"];49 -> 50[label="",style="solid", color="black", weight=3]; 13.71/5.47 50[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (() > ())",fontsize=16,color="black",shape="box"];50 -> 51[label="",style="solid", color="black", weight=3]; 13.71/5.47 51[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (compare () () == GT)",fontsize=16,color="black",shape="box"];51 -> 52[label="",style="solid", color="black", weight=3]; 13.71/5.47 52[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 (EQ == GT)",fontsize=16,color="black",shape="box"];52 -> 53[label="",style="solid", color="black", weight=3]; 13.71/5.47 53[label="FiniteMap.addToFM_C1 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 False",fontsize=16,color="black",shape="box"];53 -> 54[label="",style="solid", color="black", weight=3]; 13.71/5.47 54[label="FiniteMap.addToFM_C0 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 otherwise",fontsize=16,color="black",shape="box"];54 -> 55[label="",style="solid", color="black", weight=3]; 13.71/5.47 55[label="FiniteMap.addToFM_C0 FiniteMap.addListToFM0 () vyz61 vyz62 vyz63 vyz64 () vyz31101 True",fontsize=16,color="black",shape="box"];55 -> 56[label="",style="solid", color="black", weight=3]; 13.71/5.47 56[label="FiniteMap.Branch () (FiniteMap.addListToFM0 vyz61 vyz31101) vyz62 vyz63 vyz64",fontsize=16,color="green",shape="box"];56 -> 57[label="",style="dashed", color="green", weight=3]; 13.71/5.47 57[label="FiniteMap.addListToFM0 vyz61 vyz31101",fontsize=16,color="black",shape="box"];57 -> 58[label="",style="solid", color="black", weight=3]; 13.71/5.47 58[label="vyz31101",fontsize=16,color="green",shape="box"];} 13.71/5.47 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (14) 13.71/5.47 Obligation: 13.71/5.47 Q DP problem: 13.71/5.47 The TRS P consists of the following rules: 13.71/5.47 13.71/5.47 new_foldl(vyz6, :(vyz3110, vyz3111), h) -> new_foldl(new_addListToFM_CAdd(vyz6, vyz3110, h), vyz3111, h) 13.71/5.47 13.71/5.47 The TRS R consists of the following rules: 13.71/5.47 13.71/5.47 new_addListToFM_CAdd(Branch(@0, vyz61, vyz62, vyz63, vyz64), @2(@0, vyz31101), h) -> Branch(@0, vyz31101, vyz62, vyz63, vyz64) 13.71/5.47 new_addListToFM_CAdd(EmptyFM, @2(vyz31100, vyz31101), h) -> Branch(vyz31100, vyz31101, Pos(Succ(Zero)), new_emptyFM(h), new_emptyFM(h)) 13.71/5.47 new_emptyFM(h) -> EmptyFM 13.71/5.47 13.71/5.47 The set Q consists of the following terms: 13.71/5.47 13.71/5.47 new_addListToFM_CAdd(EmptyFM, @2(x0, x1), x2) 13.71/5.47 new_emptyFM(x0) 13.71/5.47 new_addListToFM_CAdd(Branch(@0, x0, x1, x2, x3), @2(@0, x4), x5) 13.71/5.47 13.71/5.47 We have to consider all minimal (P,Q,R)-chains. 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (15) QDPSizeChangeProof (EQUIVALENT) 13.71/5.47 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 13.71/5.47 13.71/5.47 From the DPs we obtained the following set of size-change graphs: 13.71/5.47 *new_foldl(vyz6, :(vyz3110, vyz3111), h) -> new_foldl(new_addListToFM_CAdd(vyz6, vyz3110, h), vyz3111, h) 13.71/5.47 The graph contains the following edges 2 > 2, 3 >= 3 13.71/5.47 13.71/5.47 13.71/5.47 ---------------------------------------- 13.71/5.47 13.71/5.47 (16) 13.71/5.47 YES 13.79/5.51 EOF