details

property	value
status	complete
benchmark	FiniteMap_addToFM_2.hs
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n146.star.cs.uiowa.edu
space	full_haskell

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	6.72260189056 seconds
cpu usage	14.152978557
max memory	7.24492288E8

stage attributes

key	value
output-size	59182
starexec-result	YES

output

/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.hs /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.hs # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty H-Termination with start terms of the given HASKELL could be proven: (0) HASKELL (1) LR [EQUIVALENT, 0 ms] (2) HASKELL (3) CR [EQUIVALENT, 0 ms] (4) HASKELL (5) BR [EQUIVALENT, 0 ms] (6) HASKELL (7) COR [EQUIVALENT, 22 ms] (8) HASKELL (9) LetRed [EQUIVALENT, 0 ms] (10) HASKELL (11) NumRed [SOUND, 0 ms] (12) HASKELL (13) Narrow [EQUIVALENT, 22 ms] (14) YES ---------------------------------------- (0) Obligation: mainModule Main module FiniteMap where { import qualified Main; import qualified Maybe; import qualified Prelude; data FiniteMap b a = EmptyFM | Branch b a Int (FiniteMap b a) (FiniteMap b a) ; instance (Eq a, Eq b) => Eq FiniteMap a b where { } addToFM :: Ord a => FiniteMap a b -> a -> b -> FiniteMap a b; addToFM fm key elt = addToFM_C (\old new ->new) fm key elt; addToFM_C :: Ord b => (a -> a -> a) -> FiniteMap b a -> b -> a -> FiniteMap b a; addToFM_C combiner EmptyFM key elt = unitFM key elt; 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 | new_key > key = mkBalBranch key elt fm_l (addToFM_C combiner fm_r new_key new_elt) | otherwise = Branch new_key (combiner elt new_elt) size fm_l fm_r; emptyFM :: FiniteMap b a; emptyFM = EmptyFM; findMax :: FiniteMap a b -> (a,b); findMax (Branch key elt _ _ EmptyFM) = (key,elt); findMax (Branch key elt _ _ fm_r) = findMax fm_r; findMin :: FiniteMap a b -> (a,b); findMin (Branch key elt _ EmptyFM _) = (key,elt); findMin (Branch key elt _ fm_l _) = findMin fm_l; mkBalBranch :: Ord a => a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; mkBalBranch key elt fm_L fm_R | size_l + size_r < 2 = mkBranch 1 key elt fm_L fm_R | size_r > sIZE_RATIO * size_l = case fm_R of { Branch _ _ _ fm_rl fm_rr | sizeFM fm_rl < 2 * sizeFM fm_rr -> single_L fm_L fm_R | otherwise -> double_L fm_L fm_R; } | size_l > sIZE_RATIO * size_r = case fm_L of { Branch _ _ _ fm_ll fm_lr | sizeFM fm_lr < 2 * sizeFM fm_ll -> single_R fm_L fm_R | otherwise -> double_R fm_L fm_R; } | otherwise = mkBranch 2 key elt fm_L fm_R where { 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); 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); 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; 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); size_l = sizeFM fm_L; size_r = sizeFM fm_R; }; mkBranch :: Ord a => Int -> a -> b -> FiniteMap a b -> FiniteMap a b -> FiniteMap a b; mkBranch which key elt fm_l fm_r = let { result = Branch key elt (unbox (1 + left_size + right_size)) fm_l fm_r; } in result where { balance_ok = True; left_ok = case fm_l of { EmptyFM-> True; Branch left_key _ _ _ _-> let { biggest_left_key = fst (findMax fm_l); } in biggest_left_key < key; } ; left_size = sizeFM fm_l; right_ok = case fm_r of { EmptyFM-> True; Branch right_key _ _ _ _-> let { smallest_right_key = fst (findMin fm_r); } in key < smallest_right_key; } ; popout

output may be truncated. 'popout' for the full output.

job log

popout

actions

all output return to Haskell