details

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

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	104.904231787 seconds
cpu usage	140.643373078
max memory	6.082768896E9

stage attributes

key	value
output-size	61941
starexec-result	MAYBE

output

/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.hs /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- MAYBE proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty H-Termination with start terms of the given HASKELL could not be shown: (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, 17 ms] (8) HASKELL (9) LetRed [EQUIVALENT, 0 ms] (10) HASKELL (11) NumRed [SOUND, 0 ms] (12) HASKELL ---------------------------------------- (0) Obligation: mainModule Main module FiniteMap where { import qualified Main; import qualified Maybe; import qualified Prelude; data FiniteMap a b = EmptyFM | Branch a b Int (FiniteMap a b) (FiniteMap a b) ; instance (Eq a, Eq b) => Eq FiniteMap a b where { } delFromFM :: Ord a => FiniteMap a b -> a -> FiniteMap a b; delFromFM EmptyFM del_key = emptyFM; delFromFM (Branch key elt size fm_l fm_r) del_key | del_key > key = mkBalBranch key elt fm_l (delFromFM fm_r del_key) | del_key < key = mkBalBranch key elt (delFromFM fm_l del_key) fm_r | key == del_key = glueBal fm_l fm_r; deleteMax :: Ord b => FiniteMap b a -> FiniteMap b a; deleteMax (Branch key elt _ fm_l EmptyFM) = fm_l; deleteMax (Branch key elt _ fm_l fm_r) = mkBalBranch key elt fm_l (deleteMax fm_r); deleteMin :: Ord b => FiniteMap b a -> FiniteMap b a; deleteMin (Branch key elt _ EmptyFM fm_r) = fm_r; deleteMin (Branch key elt _ fm_l fm_r) = mkBalBranch key elt (deleteMin fm_l) fm_r; emptyFM :: FiniteMap b a; emptyFM = EmptyFM; findMax :: FiniteMap b a -> (b,a); findMax (Branch key elt _ _ EmptyFM) = (key,elt); findMax (Branch key elt _ _ fm_r) = findMax fm_r; findMin :: FiniteMap b a -> (b,a); findMin (Branch key elt _ EmptyFM _) = (key,elt); findMin (Branch key elt _ fm_l _) = findMin fm_l; glueBal :: Ord b => FiniteMap b a -> FiniteMap b a -> FiniteMap b a; glueBal EmptyFM fm2 = fm2; glueBal fm1 EmptyFM = fm1; glueBal fm1 fm2 | sizeFM fm2 > sizeFM fm1 = mkBalBranch mid_key2 mid_elt2 fm1 (deleteMin fm2) | otherwise = mkBalBranch mid_key1 mid_elt1 (deleteMax fm1) fm2 where { mid_elt1 = (\(_,mid_elt1) ->mid_elt1) vv2; mid_elt2 = (\(_,mid_elt2) ->mid_elt2) vv3; mid_key1 = (\(mid_key1,_) ->mid_key1) vv2; mid_key2 = (\(mid_key2,_) ->mid_key2) vv3; vv2 = findMax fm1; vv3 = findMin fm2; }; 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 { popout

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

job log

popout

actions

all output return to Funct Progr 77531