8.83/3.77 YES 10.75/4.31 proof of /export/starexec/sandbox2/benchmark/theBenchmark.hs 10.75/4.31 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.75/4.31 10.75/4.31 10.75/4.31 H-Termination with start terms of the given HASKELL could be proven: 10.75/4.31 10.75/4.31 (0) HASKELL 10.75/4.31 (1) LR [EQUIVALENT, 0 ms] 10.75/4.31 (2) HASKELL 10.75/4.31 (3) BR [EQUIVALENT, 0 ms] 10.75/4.31 (4) HASKELL 10.75/4.31 (5) COR [EQUIVALENT, 0 ms] 10.75/4.31 (6) HASKELL 10.75/4.31 (7) Narrow [EQUIVALENT, 21 ms] 10.75/4.31 (8) YES 10.75/4.31 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (0) 10.75/4.31 Obligation: 10.75/4.31 mainModule Main 10.75/4.31 module Maybe where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Main where { 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Monad where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Prelude; 10.75/4.31 liftM3 :: Monad c => (e -> d -> b -> a) -> c e -> c d -> c b -> c a; 10.75/4.31 liftM3 f m1 m2 m3 = m1 >>= (\x1 ->m2 >>= (\x2 ->m3 >>= (\x3 ->return (f x1 x2 x3)))); 10.75/4.31 10.75/4.31 } 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (1) LR (EQUIVALENT) 10.75/4.31 Lambda Reductions: 10.75/4.31 The following Lambda expression 10.75/4.31 "\x3->return (f x1 x2 x3)" 10.75/4.31 is transformed to 10.75/4.31 "liftM30 f x1 x2 x3 = return (f x1 x2 x3); 10.75/4.31 " 10.75/4.31 The following Lambda expression 10.75/4.31 "\x2->m3 >>= liftM30 f x1 x2" 10.75/4.31 is transformed to 10.75/4.31 "liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 10.75/4.31 " 10.75/4.31 The following Lambda expression 10.75/4.31 "\x1->m2 >>= liftM31 m3 f x1" 10.75/4.31 is transformed to 10.75/4.31 "liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 10.75/4.31 " 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (2) 10.75/4.31 Obligation: 10.75/4.31 mainModule Main 10.75/4.31 module Maybe where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Main where { 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Monad where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Prelude; 10.75/4.31 liftM3 :: Monad c => (b -> a -> d -> e) -> c b -> c a -> c d -> c e; 10.75/4.31 liftM3 f m1 m2 m3 = m1 >>= liftM32 m2 m3 f; 10.75/4.31 10.75/4.31 liftM30 f x1 x2 x3 = return (f x1 x2 x3); 10.75/4.31 10.75/4.31 liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 10.75/4.31 10.75/4.31 liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 10.75/4.31 10.75/4.31 } 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (3) BR (EQUIVALENT) 10.75/4.31 Replaced joker patterns by fresh variables and removed binding patterns. 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (4) 10.75/4.31 Obligation: 10.75/4.31 mainModule Main 10.75/4.31 module Maybe where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Main where { 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Monad where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Prelude; 10.75/4.31 liftM3 :: Monad d => (b -> a -> c -> e) -> d b -> d a -> d c -> d e; 10.75/4.31 liftM3 f m1 m2 m3 = m1 >>= liftM32 m2 m3 f; 10.75/4.31 10.75/4.31 liftM30 f x1 x2 x3 = return (f x1 x2 x3); 10.75/4.31 10.75/4.31 liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 10.75/4.31 10.75/4.31 liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 10.75/4.31 10.75/4.31 } 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (5) COR (EQUIVALENT) 10.75/4.31 Cond Reductions: 10.75/4.31 The following Function with conditions 10.75/4.31 "undefined |Falseundefined; 10.75/4.31 " 10.75/4.31 is transformed to 10.75/4.31 "undefined = undefined1; 10.75/4.31 " 10.75/4.31 "undefined0 True = undefined; 10.75/4.31 " 10.75/4.31 "undefined1 = undefined0 False; 10.75/4.31 " 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (6) 10.75/4.31 Obligation: 10.75/4.31 mainModule Main 10.75/4.31 module Maybe where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Main where { 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Monad; 10.75/4.31 import qualified Prelude; 10.75/4.31 } 10.75/4.31 module Monad where { 10.75/4.31 import qualified Main; 10.75/4.31 import qualified Maybe; 10.75/4.31 import qualified Prelude; 10.75/4.31 liftM3 :: Monad e => (d -> a -> b -> c) -> e d -> e a -> e b -> e c; 10.75/4.31 liftM3 f m1 m2 m3 = m1 >>= liftM32 m2 m3 f; 10.75/4.31 10.75/4.31 liftM30 f x1 x2 x3 = return (f x1 x2 x3); 10.75/4.31 10.75/4.31 liftM31 m3 f x1 x2 = m3 >>= liftM30 f x1 x2; 10.75/4.31 10.75/4.31 liftM32 m2 m3 f x1 = m2 >>= liftM31 m3 f x1; 10.75/4.31 10.75/4.31 } 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (7) Narrow (EQUIVALENT) 10.75/4.31 Haskell To QDPs 10.75/4.31 10.75/4.31 digraph dp_graph { 10.75/4.31 node [outthreshold=100, inthreshold=100];1[label="Monad.liftM3",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3]; 10.75/4.31 3[label="Monad.liftM3 vy3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3]; 10.75/4.31 4[label="Monad.liftM3 vy3 vy4",fontsize=16,color="grey",shape="box"];4 -> 5[label="",style="dashed", color="grey", weight=3]; 10.75/4.31 5[label="Monad.liftM3 vy3 vy4 vy5",fontsize=16,color="grey",shape="box"];5 -> 6[label="",style="dashed", color="grey", weight=3]; 10.75/4.31 6[label="Monad.liftM3 vy3 vy4 vy5 vy6",fontsize=16,color="black",shape="triangle"];6 -> 7[label="",style="solid", color="black", weight=3]; 10.75/4.31 7[label="vy4 >>= Monad.liftM32 vy5 vy6 vy3",fontsize=16,color="burlywood",shape="box"];28[label="vy4/Nothing",fontsize=10,color="white",style="solid",shape="box"];7 -> 28[label="",style="solid", color="burlywood", weight=9]; 10.75/4.31 28 -> 8[label="",style="solid", color="burlywood", weight=3]; 10.75/4.31 29[label="vy4/Just vy40",fontsize=10,color="white",style="solid",shape="box"];7 -> 29[label="",style="solid", color="burlywood", weight=9]; 10.75/4.31 29 -> 9[label="",style="solid", color="burlywood", weight=3]; 10.75/4.31 8[label="Nothing >>= Monad.liftM32 vy5 vy6 vy3",fontsize=16,color="black",shape="box"];8 -> 10[label="",style="solid", color="black", weight=3]; 10.75/4.31 9[label="Just vy40 >>= Monad.liftM32 vy5 vy6 vy3",fontsize=16,color="black",shape="box"];9 -> 11[label="",style="solid", color="black", weight=3]; 10.75/4.31 10[label="Nothing",fontsize=16,color="green",shape="box"];11[label="Monad.liftM32 vy5 vy6 vy3 vy40",fontsize=16,color="black",shape="box"];11 -> 12[label="",style="solid", color="black", weight=3]; 10.75/4.31 12[label="vy5 >>= Monad.liftM31 vy6 vy3 vy40",fontsize=16,color="burlywood",shape="box"];30[label="vy5/Nothing",fontsize=10,color="white",style="solid",shape="box"];12 -> 30[label="",style="solid", color="burlywood", weight=9]; 10.75/4.31 30 -> 13[label="",style="solid", color="burlywood", weight=3]; 10.75/4.31 31[label="vy5/Just vy50",fontsize=10,color="white",style="solid",shape="box"];12 -> 31[label="",style="solid", color="burlywood", weight=9]; 10.75/4.31 31 -> 14[label="",style="solid", color="burlywood", weight=3]; 10.75/4.31 13[label="Nothing >>= Monad.liftM31 vy6 vy3 vy40",fontsize=16,color="black",shape="box"];13 -> 15[label="",style="solid", color="black", weight=3]; 10.75/4.31 14[label="Just vy50 >>= Monad.liftM31 vy6 vy3 vy40",fontsize=16,color="black",shape="box"];14 -> 16[label="",style="solid", color="black", weight=3]; 10.75/4.31 15[label="Nothing",fontsize=16,color="green",shape="box"];16[label="Monad.liftM31 vy6 vy3 vy40 vy50",fontsize=16,color="black",shape="box"];16 -> 17[label="",style="solid", color="black", weight=3]; 10.75/4.31 17[label="vy6 >>= Monad.liftM30 vy3 vy40 vy50",fontsize=16,color="burlywood",shape="box"];32[label="vy6/Nothing",fontsize=10,color="white",style="solid",shape="box"];17 -> 32[label="",style="solid", color="burlywood", weight=9]; 10.75/4.31 32 -> 18[label="",style="solid", color="burlywood", weight=3]; 10.75/4.31 33[label="vy6/Just vy60",fontsize=10,color="white",style="solid",shape="box"];17 -> 33[label="",style="solid", color="burlywood", weight=9]; 10.75/4.31 33 -> 19[label="",style="solid", color="burlywood", weight=3]; 10.75/4.31 18[label="Nothing >>= Monad.liftM30 vy3 vy40 vy50",fontsize=16,color="black",shape="box"];18 -> 20[label="",style="solid", color="black", weight=3]; 10.75/4.31 19[label="Just vy60 >>= Monad.liftM30 vy3 vy40 vy50",fontsize=16,color="black",shape="box"];19 -> 21[label="",style="solid", color="black", weight=3]; 10.75/4.31 20[label="Nothing",fontsize=16,color="green",shape="box"];21[label="Monad.liftM30 vy3 vy40 vy50 vy60",fontsize=16,color="black",shape="box"];21 -> 22[label="",style="solid", color="black", weight=3]; 10.75/4.31 22[label="return (vy3 vy40 vy50 vy60)",fontsize=16,color="black",shape="box"];22 -> 23[label="",style="solid", color="black", weight=3]; 10.75/4.31 23[label="Just (vy3 vy40 vy50 vy60)",fontsize=16,color="green",shape="box"];23 -> 24[label="",style="dashed", color="green", weight=3]; 10.75/4.31 24[label="vy3 vy40 vy50 vy60",fontsize=16,color="green",shape="box"];24 -> 25[label="",style="dashed", color="green", weight=3]; 10.75/4.31 24 -> 26[label="",style="dashed", color="green", weight=3]; 10.75/4.31 24 -> 27[label="",style="dashed", color="green", weight=3]; 10.75/4.31 25[label="vy40",fontsize=16,color="green",shape="box"];26[label="vy50",fontsize=16,color="green",shape="box"];27[label="vy60",fontsize=16,color="green",shape="box"];} 10.75/4.31 10.75/4.31 ---------------------------------------- 10.75/4.31 10.75/4.31 (8) 10.75/4.31 YES 11.06/4.35 EOF