8.02/3.62 YES 10.08/4.16 proof of /export/starexec/sandbox/benchmark/theBenchmark.hs 10.08/4.16 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.08/4.16 10.08/4.16 10.08/4.16 H-Termination with start terms of the given HASKELL could be proven: 10.08/4.16 10.08/4.16 (0) HASKELL 10.08/4.16 (1) BR [EQUIVALENT, 0 ms] 10.08/4.16 (2) HASKELL 10.08/4.16 (3) COR [EQUIVALENT, 0 ms] 10.08/4.16 (4) HASKELL 10.08/4.16 (5) NumRed [SOUND, 0 ms] 10.08/4.16 (6) HASKELL 10.08/4.16 (7) Narrow [EQUIVALENT, 74 ms] 10.08/4.16 (8) YES 10.08/4.16 10.08/4.16 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (0) 10.08/4.16 Obligation: 10.08/4.16 mainModule Main 10.08/4.16 module Main where { 10.08/4.16 import qualified Prelude; 10.08/4.16 } 10.08/4.16 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (1) BR (EQUIVALENT) 10.08/4.16 Replaced joker patterns by fresh variables and removed binding patterns. 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (2) 10.08/4.16 Obligation: 10.08/4.16 mainModule Main 10.08/4.16 module Main where { 10.08/4.16 import qualified Prelude; 10.08/4.16 } 10.08/4.16 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (3) COR (EQUIVALENT) 10.08/4.16 Cond Reductions: 10.08/4.16 The following Function with conditions 10.08/4.16 "toEnum 0 = (); 10.08/4.16 " 10.08/4.16 is transformed to 10.08/4.16 "toEnum vz = toEnum1 vz; 10.08/4.16 " 10.08/4.16 "toEnum0 True vz = (); 10.08/4.16 " 10.08/4.16 "toEnum1 vz = toEnum0 (vz == 0) vz; 10.08/4.16 " 10.08/4.16 The following Function with conditions 10.08/4.16 "takeWhile p [] = []; 10.08/4.16 takeWhile p (x : xs)|p xx : takeWhile p xs|otherwise[]; 10.08/4.16 " 10.08/4.16 is transformed to 10.08/4.16 "takeWhile p [] = takeWhile3 p []; 10.08/4.16 takeWhile p (x : xs) = takeWhile2 p (x : xs); 10.08/4.16 " 10.08/4.16 "takeWhile0 p x xs True = []; 10.08/4.16 " 10.08/4.16 "takeWhile1 p x xs True = x : takeWhile p xs; 10.08/4.16 takeWhile1 p x xs False = takeWhile0 p x xs otherwise; 10.08/4.16 " 10.08/4.16 "takeWhile2 p (x : xs) = takeWhile1 p x xs (p x); 10.08/4.16 " 10.08/4.16 "takeWhile3 p [] = []; 10.08/4.16 takeWhile3 ww wx = takeWhile2 ww wx; 10.08/4.16 " 10.08/4.16 The following Function with conditions 10.08/4.16 "undefined |Falseundefined; 10.08/4.16 " 10.08/4.16 is transformed to 10.08/4.16 "undefined = undefined1; 10.08/4.16 " 10.08/4.16 "undefined0 True = undefined; 10.08/4.16 " 10.08/4.16 "undefined1 = undefined0 False; 10.08/4.16 " 10.08/4.16 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (4) 10.08/4.16 Obligation: 10.08/4.16 mainModule Main 10.08/4.16 module Main where { 10.08/4.16 import qualified Prelude; 10.08/4.16 } 10.08/4.16 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (5) NumRed (SOUND) 10.08/4.16 Num Reduction:All numbers are transformed to their corresponding representation with Succ, Pred and Zero. 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (6) 10.08/4.16 Obligation: 10.08/4.16 mainModule Main 10.08/4.16 module Main where { 10.08/4.16 import qualified Prelude; 10.08/4.16 } 10.08/4.16 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (7) Narrow (EQUIVALENT) 10.08/4.16 Haskell To QDPs 10.08/4.16 10.08/4.16 digraph dp_graph { 10.08/4.16 node [outthreshold=100, inthreshold=100];1[label="enumFromTo",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 10.08/4.16 3[label="enumFromTo wy3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 10.08/4.16 4[label="enumFromTo wy3 wy4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3]; 10.08/4.16 5[label="map toEnum (enumFromTo (fromEnum wy3) (fromEnum wy4))",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3]; 10.08/4.16 6[label="map toEnum (numericEnumFromTo (fromEnum wy3) (fromEnum wy4))",fontsize=16,color="black",shape="box"];6 -> 7[label="",style="solid", color="black", weight=3]; 10.08/4.16 7[label="map toEnum (takeWhile (flip (<=) (fromEnum wy4)) (numericEnumFrom (fromEnum wy3)))",fontsize=16,color="black",shape="box"];7 -> 8[label="",style="solid", color="black", weight=3]; 10.08/4.16 8[label="map toEnum (takeWhile (flip (<=) (fromEnum wy4)) (fromEnum wy3 : (numericEnumFrom $! fromEnum wy3 + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];8 -> 9[label="",style="solid", color="black", weight=3]; 10.08/4.16 9[label="map toEnum (takeWhile2 (flip (<=) (fromEnum wy4)) (fromEnum wy3 : (numericEnumFrom $! fromEnum wy3 + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];9 -> 10[label="",style="solid", color="black", weight=3]; 10.08/4.16 10[label="map toEnum (takeWhile1 (flip (<=) (fromEnum wy4)) (fromEnum wy3) (numericEnumFrom $! fromEnum wy3 + fromInt (Pos (Succ Zero))) (flip (<=) (fromEnum wy4) (fromEnum wy3)))",fontsize=16,color="black",shape="box"];10 -> 11[label="",style="solid", color="black", weight=3]; 10.08/4.16 11[label="map toEnum (takeWhile1 (flip (<=) (fromEnum wy4)) (fromEnum wy3) (numericEnumFrom $! fromEnum wy3 + fromInt (Pos (Succ Zero))) ((<=) fromEnum wy3 fromEnum wy4))",fontsize=16,color="black",shape="box"];11 -> 12[label="",style="solid", color="black", weight=3]; 10.08/4.16 12[label="map toEnum (takeWhile1 (flip (<=) (fromEnum wy4)) (fromEnum wy3) (numericEnumFrom $! fromEnum wy3 + fromInt (Pos (Succ Zero))) (compare (fromEnum wy3) (fromEnum wy4) /= GT))",fontsize=16,color="black",shape="box"];12 -> 13[label="",style="solid", color="black", weight=3]; 10.08/4.16 13[label="map toEnum (takeWhile1 (flip (<=) (fromEnum wy4)) (fromEnum wy3) (numericEnumFrom $! fromEnum wy3 + fromInt (Pos (Succ Zero))) (not (compare (fromEnum wy3) (fromEnum wy4) == GT)))",fontsize=16,color="black",shape="box"];13 -> 14[label="",style="solid", color="black", weight=3]; 10.08/4.16 14[label="map toEnum (takeWhile1 (flip (<=) (fromEnum wy4)) (fromEnum wy3) (numericEnumFrom $! fromEnum wy3 + fromInt (Pos (Succ Zero))) (not (primCmpInt (fromEnum wy3) (fromEnum wy4) == GT)))",fontsize=16,color="burlywood",shape="box"];53[label="wy3/()",fontsize=10,color="white",style="solid",shape="box"];14 -> 53[label="",style="solid", color="burlywood", weight=9]; 10.08/4.16 53 -> 15[label="",style="solid", color="burlywood", weight=3]; 10.08/4.16 15[label="map toEnum (takeWhile1 (flip (<=) (fromEnum wy4)) (fromEnum ()) (numericEnumFrom $! fromEnum () + fromInt (Pos (Succ Zero))) (not (primCmpInt (fromEnum ()) (fromEnum wy4) == GT)))",fontsize=16,color="black",shape="box"];15 -> 16[label="",style="solid", color="black", weight=3]; 10.08/4.16 16[label="map toEnum (takeWhile1 (flip (<=) (fromEnum wy4)) (Pos Zero) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))) (not (primCmpInt (Pos Zero) (fromEnum wy4) == GT)))",fontsize=16,color="burlywood",shape="box"];54[label="wy4/()",fontsize=10,color="white",style="solid",shape="box"];16 -> 54[label="",style="solid", color="burlywood", weight=9]; 10.08/4.16 54 -> 17[label="",style="solid", color="burlywood", weight=3]; 10.08/4.16 17[label="map toEnum (takeWhile1 (flip (<=) (fromEnum ())) (Pos Zero) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))) (not (primCmpInt (Pos Zero) (fromEnum ()) == GT)))",fontsize=16,color="black",shape="box"];17 -> 18[label="",style="solid", color="black", weight=3]; 10.08/4.16 18[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos Zero) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))) (not (primCmpInt (Pos Zero) (Pos Zero) == GT)))",fontsize=16,color="black",shape="box"];18 -> 19[label="",style="solid", color="black", weight=3]; 10.08/4.16 19[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos Zero) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))) (not (EQ == GT)))",fontsize=16,color="black",shape="box"];19 -> 20[label="",style="solid", color="black", weight=3]; 10.08/4.16 20[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos Zero) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))) (not False))",fontsize=16,color="black",shape="box"];20 -> 21[label="",style="solid", color="black", weight=3]; 10.08/4.16 21[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos Zero) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))) True)",fontsize=16,color="black",shape="box"];21 -> 22[label="",style="solid", color="black", weight=3]; 10.08/4.16 22[label="map toEnum (Pos Zero : takeWhile (flip (<=) (Pos Zero)) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))",fontsize=16,color="black",shape="box"];22 -> 23[label="",style="solid", color="black", weight=3]; 10.08/4.16 23[label="toEnum (Pos Zero) : map toEnum (takeWhile (flip (<=) (Pos Zero)) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))",fontsize=16,color="green",shape="box"];23 -> 24[label="",style="dashed", color="green", weight=3]; 10.08/4.16 23 -> 25[label="",style="dashed", color="green", weight=3]; 10.08/4.16 24[label="toEnum (Pos Zero)",fontsize=16,color="black",shape="box"];24 -> 26[label="",style="solid", color="black", weight=3]; 10.08/4.16 25[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (numericEnumFrom $! Pos Zero + fromInt (Pos (Succ Zero))))",fontsize=16,color="black",shape="box"];25 -> 27[label="",style="solid", color="black", weight=3]; 10.08/4.16 26[label="toEnum1 (Pos Zero)",fontsize=16,color="black",shape="box"];26 -> 28[label="",style="solid", color="black", weight=3]; 10.08/4.16 27[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (Pos Zero + fromInt (Pos (Succ Zero)) `seq` numericEnumFrom (Pos Zero + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];27 -> 29[label="",style="solid", color="black", weight=3]; 10.08/4.16 28[label="toEnum0 (Pos Zero == Pos Zero) (Pos Zero)",fontsize=16,color="black",shape="box"];28 -> 30[label="",style="solid", color="black", weight=3]; 10.08/4.16 29[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (enforceWHNF (WHNF (Pos Zero + fromInt (Pos (Succ Zero)))) (numericEnumFrom (Pos Zero + fromInt (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];29 -> 31[label="",style="solid", color="black", weight=3]; 10.08/4.16 30[label="toEnum0 (primEqInt (Pos Zero) (Pos Zero)) (Pos Zero)",fontsize=16,color="black",shape="box"];30 -> 32[label="",style="solid", color="black", weight=3]; 10.08/4.16 31[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (enforceWHNF (WHNF (primPlusInt (Pos Zero) (fromInt (Pos (Succ Zero))))) (numericEnumFrom (primPlusInt (Pos Zero) (fromInt (Pos (Succ Zero)))))))",fontsize=16,color="black",shape="box"];31 -> 33[label="",style="solid", color="black", weight=3]; 10.08/4.16 32[label="toEnum0 True (Pos Zero)",fontsize=16,color="black",shape="box"];32 -> 34[label="",style="solid", color="black", weight=3]; 10.08/4.16 33[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (enforceWHNF (WHNF (primPlusInt (Pos Zero) (Pos (Succ Zero)))) (numericEnumFrom (primPlusInt (Pos Zero) (Pos (Succ Zero))))))",fontsize=16,color="black",shape="box"];33 -> 35[label="",style="solid", color="black", weight=3]; 10.08/4.16 34[label="()",fontsize=16,color="green",shape="box"];35[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (enforceWHNF (WHNF (Pos (primPlusNat Zero (Succ Zero)))) (numericEnumFrom (Pos (primPlusNat Zero (Succ Zero))))))",fontsize=16,color="black",shape="box"];35 -> 36[label="",style="solid", color="black", weight=3]; 10.08/4.16 36[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (numericEnumFrom (Pos (primPlusNat Zero (Succ Zero)))))",fontsize=16,color="black",shape="box"];36 -> 37[label="",style="solid", color="black", weight=3]; 10.08/4.16 37[label="map toEnum (takeWhile (flip (<=) (Pos Zero)) (Pos (primPlusNat Zero (Succ Zero)) : (numericEnumFrom $! Pos (primPlusNat Zero (Succ Zero)) + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];37 -> 38[label="",style="solid", color="black", weight=3]; 10.08/4.16 38[label="map toEnum (takeWhile2 (flip (<=) (Pos Zero)) (Pos (primPlusNat Zero (Succ Zero)) : (numericEnumFrom $! Pos (primPlusNat Zero (Succ Zero)) + fromInt (Pos (Succ Zero)))))",fontsize=16,color="black",shape="box"];38 -> 39[label="",style="solid", color="black", weight=3]; 10.08/4.16 39[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (primPlusNat Zero (Succ Zero))) (numericEnumFrom $! Pos (primPlusNat Zero (Succ Zero)) + fromInt (Pos (Succ Zero))) (flip (<=) (Pos Zero) (Pos (primPlusNat Zero (Succ Zero)))))",fontsize=16,color="black",shape="box"];39 -> 40[label="",style="solid", color="black", weight=3]; 10.08/4.16 40[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (primPlusNat Zero (Succ Zero))) (numericEnumFrom $! Pos (primPlusNat Zero (Succ Zero)) + fromInt (Pos (Succ Zero))) ((<=) Pos (primPlusNat Zero (Succ Zero)) Pos Zero))",fontsize=16,color="black",shape="box"];40 -> 41[label="",style="solid", color="black", weight=3]; 10.08/4.16 41[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (primPlusNat Zero (Succ Zero))) (numericEnumFrom $! Pos (primPlusNat Zero (Succ Zero)) + fromInt (Pos (Succ Zero))) (compare (Pos (primPlusNat Zero (Succ Zero))) (Pos Zero) /= GT))",fontsize=16,color="black",shape="box"];41 -> 42[label="",style="solid", color="black", weight=3]; 10.08/4.16 42[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (primPlusNat Zero (Succ Zero))) (numericEnumFrom $! Pos (primPlusNat Zero (Succ Zero)) + fromInt (Pos (Succ Zero))) (not (compare (Pos (primPlusNat Zero (Succ Zero))) (Pos Zero) == GT)))",fontsize=16,color="black",shape="box"];42 -> 43[label="",style="solid", color="black", weight=3]; 10.08/4.16 43[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (primPlusNat Zero (Succ Zero))) (numericEnumFrom $! Pos (primPlusNat Zero (Succ Zero)) + fromInt (Pos (Succ Zero))) (not (primCmpInt (Pos (primPlusNat Zero (Succ Zero))) (Pos Zero) == GT)))",fontsize=16,color="black",shape="box"];43 -> 44[label="",style="solid", color="black", weight=3]; 10.08/4.16 44[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (Succ Zero)) (numericEnumFrom $! Pos (Succ Zero) + fromInt (Pos (Succ Zero))) (not (primCmpInt (Pos (Succ Zero)) (Pos Zero) == GT)))",fontsize=16,color="black",shape="box"];44 -> 45[label="",style="solid", color="black", weight=3]; 10.08/4.16 45[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (Succ Zero)) (numericEnumFrom $! Pos (Succ Zero) + fromInt (Pos (Succ Zero))) (not (primCmpNat (Succ Zero) Zero == GT)))",fontsize=16,color="black",shape="box"];45 -> 46[label="",style="solid", color="black", weight=3]; 10.08/4.16 46[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (Succ Zero)) (numericEnumFrom $! Pos (Succ Zero) + fromInt (Pos (Succ Zero))) (not (GT == GT)))",fontsize=16,color="black",shape="box"];46 -> 47[label="",style="solid", color="black", weight=3]; 10.08/4.16 47[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (Succ Zero)) (numericEnumFrom $! Pos (Succ Zero) + fromInt (Pos (Succ Zero))) (not True))",fontsize=16,color="black",shape="box"];47 -> 48[label="",style="solid", color="black", weight=3]; 10.08/4.16 48[label="map toEnum (takeWhile1 (flip (<=) (Pos Zero)) (Pos (Succ Zero)) (numericEnumFrom $! Pos (Succ Zero) + fromInt (Pos (Succ Zero))) False)",fontsize=16,color="black",shape="box"];48 -> 49[label="",style="solid", color="black", weight=3]; 10.08/4.16 49[label="map toEnum (takeWhile0 (flip (<=) (Pos Zero)) (Pos (Succ Zero)) (numericEnumFrom $! Pos (Succ Zero) + fromInt (Pos (Succ Zero))) otherwise)",fontsize=16,color="black",shape="box"];49 -> 50[label="",style="solid", color="black", weight=3]; 10.08/4.16 50[label="map toEnum (takeWhile0 (flip (<=) (Pos Zero)) (Pos (Succ Zero)) (numericEnumFrom $! Pos (Succ Zero) + fromInt (Pos (Succ Zero))) True)",fontsize=16,color="black",shape="box"];50 -> 51[label="",style="solid", color="black", weight=3]; 10.08/4.16 51[label="map toEnum []",fontsize=16,color="black",shape="box"];51 -> 52[label="",style="solid", color="black", weight=3]; 10.08/4.16 52[label="[]",fontsize=16,color="green",shape="box"];} 10.08/4.16 10.08/4.16 ---------------------------------------- 10.08/4.16 10.08/4.16 (8) 10.08/4.16 YES 10.08/4.20 EOF