/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.hs /export/starexec/sandbox2/output/output_files


--------------------------------------------------------------------------------


YES
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 be proven:

(0) HASKELL
(1) LR [EQUIVALENT, 0 ms]
(2) HASKELL
(3) IPR [EQUIVALENT, 0 ms]
(4) HASKELL
(5) BR [EQUIVALENT, 0 ms]
(6) HASKELL
(7) COR [EQUIVALENT, 0 ms]
(8) HASKELL
(9) Narrow [SOUND, 0 ms]
(10) AND
    (11) QDP
        (12) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (13) YES
    (14) QDP
        (15) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (16) YES


----------------------------------------

(0)
Obligation:
mainModule Main 
module Maybe where {
import qualified Main;
import qualified Monad;
import qualified Prelude;
}
module Main where {
import qualified Maybe;
import qualified Monad;
import qualified Prelude;
}
module Monad where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
mapAndUnzipM :: Monad c => (b  ->  c (a,d))  ->  [b]  ->  c ([a],[d]);
mapAndUnzipM f xs = sequence (map f xs) >>= return . unzip;

}

----------------------------------------

(1) LR (EQUIVALENT)
Lambda Reductions:
The following Lambda expression
"\(a,b)~(as,bs)->(a : as,b : bs)"
is transformed to
"unzip0 (a,b) ~(as,bs) = (a : as,b : bs);
"
The following Lambda expression
"\xs->return (x : xs)"
is transformed to
"sequence0 x xs = return (x : xs);
"
The following Lambda expression
"\x->sequence cs >>= sequence0 x"
is transformed to
"sequence1 cs x = sequence cs >>= sequence0 x;
"

----------------------------------------

(2)
Obligation:
mainModule Main 
module Maybe where {
import qualified Main;
import qualified Monad;
import qualified Prelude;
}
module Main where {
import qualified Maybe;
import qualified Monad;
import qualified Prelude;
}
module Monad where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
mapAndUnzipM :: Monad b => (a  ->  b (d,c))  ->  [a]  ->  b ([d],[c]);
mapAndUnzipM f xs = sequence (map f xs) >>= return . unzip;

}

----------------------------------------

(3) IPR (EQUIVALENT)
IrrPat Reductions:
The variables of the following irrefutable Pattern
"~(as,bs)"
are replaced by calls to these functions
"unzip00 (as,bs) = as;
"
"unzip01 (as,bs) = bs;
"

----------------------------------------

(4)
Obligation:
mainModule Main 
module Maybe where {
import qualified Main;
import qualified Monad;
import qualified Prelude;
}
module Main where {
import qualified Maybe;
import qualified Monad;
import qualified Prelude;
}
module Monad where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
mapAndUnzipM :: Monad a => (c  ->  a (b,d))  ->  [c]  ->  a ([b],[d]);
mapAndUnzipM f xs = sequence (map f xs) >>= return . unzip;

}

----------------------------------------

(5) BR (EQUIVALENT)
Replaced joker patterns by fresh variables and removed binding patterns.
----------------------------------------

(6)
Obligation:
mainModule Main 
module Maybe where {
import qualified Main;
import qualified Monad;
import qualified Prelude;
}
module Main where {
import qualified Maybe;
import qualified Monad;
import qualified Prelude;
}
module Monad where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
mapAndUnzipM :: Monad d => (b  ->  d (a,c))  ->  [b]  ->  d ([a],[c]);
mapAndUnzipM f xs = sequence (map f xs) >>= return . unzip;

}

----------------------------------------

(7) COR (EQUIVALENT)
Cond Reductions:
The following Function with conditions
"undefined |Falseundefined;
"
is transformed to
"undefined  = undefined1;
"
"undefined0 True = undefined;
"
"undefined1  = undefined0 False;
"

----------------------------------------

(8)
Obligation:
mainModule Main 
module Maybe where {
import qualified Main;
import qualified Monad;
import qualified Prelude;
}
module Main where {
import qualified Maybe;
import qualified Monad;
import qualified Prelude;
}
module Monad where {
import qualified Main;
import qualified Maybe;
import qualified Prelude;
mapAndUnzipM :: Monad b => (c  ->  b (d,a))  ->  [c]  ->  b ([d],[a]);
mapAndUnzipM f xs = sequence (map f xs) >>= return . unzip;

}

----------------------------------------

(9) Narrow (SOUND)
Haskell To QDPs

digraph dp_graph {
node [outthreshold=100, inthreshold=100];1[label="Monad.mapAndUnzipM",fontsize=16,color="grey",shape="box"];1 -> 3[label="",style="dashed", color="grey", weight=3];
3[label="Monad.mapAndUnzipM vz3",fontsize=16,color="grey",shape="box"];3 -> 4[label="",style="dashed", color="grey", weight=3];
4[label="Monad.mapAndUnzipM vz3 vz4",fontsize=16,color="black",shape="triangle"];4 -> 5[label="",style="solid", color="black", weight=3];
5[label="sequence (map vz3 vz4) >>= return . unzip",fontsize=16,color="black",shape="box"];5 -> 6[label="",style="solid", color="black", weight=3];
6 -> 174[label="",style="dashed", color="red", weight=0];
6[label="primbindIO (sequence (map vz3 vz4)) (return . unzip)",fontsize=16,color="magenta"];6 -> 175[label="",style="dashed", color="magenta", weight=3];
175[label="sequence (map vz3 vz4)",fontsize=16,color="burlywood",shape="triangle"];325[label="vz4/vz40 : vz41",fontsize=10,color="white",style="solid",shape="box"];175 -> 325[label="",style="solid", color="burlywood", weight=9];
325 -> 260[label="",style="solid", color="burlywood", weight=3];
326[label="vz4/[]",fontsize=10,color="white",style="solid",shape="box"];175 -> 326[label="",style="solid", color="burlywood", weight=9];
326 -> 261[label="",style="solid", color="burlywood", weight=3];
174[label="primbindIO vz11 (return . unzip)",fontsize=16,color="burlywood",shape="triangle"];327[label="vz11/IO vz110",fontsize=10,color="white",style="solid",shape="box"];174 -> 327[label="",style="solid", color="burlywood", weight=9];
327 -> 262[label="",style="solid", color="burlywood", weight=3];
328[label="vz11/AProVE_IO vz110",fontsize=10,color="white",style="solid",shape="box"];174 -> 328[label="",style="solid", color="burlywood", weight=9];
328 -> 263[label="",style="solid", color="burlywood", weight=3];
329[label="vz11/AProVE_Exception vz110",fontsize=10,color="white",style="solid",shape="box"];174 -> 329[label="",style="solid", color="burlywood", weight=9];
329 -> 264[label="",style="solid", color="burlywood", weight=3];
330[label="vz11/AProVE_Error vz110",fontsize=10,color="white",style="solid",shape="box"];174 -> 330[label="",style="solid", color="burlywood", weight=9];
330 -> 265[label="",style="solid", color="burlywood", weight=3];
260[label="sequence (map vz3 (vz40 : vz41))",fontsize=16,color="black",shape="box"];260 -> 266[label="",style="solid", color="black", weight=3];
261[label="sequence (map vz3 [])",fontsize=16,color="black",shape="box"];261 -> 267[label="",style="solid", color="black", weight=3];
262[label="primbindIO (IO vz110) (return . unzip)",fontsize=16,color="black",shape="box"];262 -> 268[label="",style="solid", color="black", weight=3];
263[label="primbindIO (AProVE_IO vz110) (return . unzip)",fontsize=16,color="black",shape="box"];263 -> 269[label="",style="solid", color="black", weight=3];
264[label="primbindIO (AProVE_Exception vz110) (return . unzip)",fontsize=16,color="black",shape="box"];264 -> 270[label="",style="solid", color="black", weight=3];
265[label="primbindIO (AProVE_Error vz110) (return . unzip)",fontsize=16,color="black",shape="box"];265 -> 271[label="",style="solid", color="black", weight=3];
266[label="sequence (vz3 vz40 : map vz3 vz41)",fontsize=16,color="black",shape="box"];266 -> 272[label="",style="solid", color="black", weight=3];
267[label="sequence []",fontsize=16,color="black",shape="box"];267 -> 273[label="",style="solid", color="black", weight=3];
268[label="error []",fontsize=16,color="red",shape="box"];269[label="return . unzip",fontsize=16,color="black",shape="box"];269 -> 274[label="",style="solid", color="black", weight=3];
270[label="AProVE_Exception vz110",fontsize=16,color="green",shape="box"];271[label="AProVE_Error vz110",fontsize=16,color="green",shape="box"];272[label="vz3 vz40 >>= sequence1 (map vz3 vz41)",fontsize=16,color="black",shape="box"];272 -> 275[label="",style="solid", color="black", weight=3];
273[label="return []",fontsize=16,color="black",shape="box"];273 -> 276[label="",style="solid", color="black", weight=3];
274[label="return (unzip vz110)",fontsize=16,color="black",shape="box"];274 -> 277[label="",style="solid", color="black", weight=3];
275 -> 278[label="",style="dashed", color="red", weight=0];
275[label="primbindIO (vz3 vz40) (sequence1 (map vz3 vz41))",fontsize=16,color="magenta"];275 -> 279[label="",style="dashed", color="magenta", weight=3];
276[label="primretIO []",fontsize=16,color="black",shape="box"];276 -> 280[label="",style="solid", color="black", weight=3];
277[label="primretIO (unzip vz110)",fontsize=16,color="black",shape="box"];277 -> 281[label="",style="solid", color="black", weight=3];
279[label="vz3 vz40",fontsize=16,color="green",shape="box"];279 -> 287[label="",style="dashed", color="green", weight=3];
278[label="primbindIO vz12 (sequence1 (map vz3 vz41))",fontsize=16,color="burlywood",shape="triangle"];331[label="vz12/IO vz120",fontsize=10,color="white",style="solid",shape="box"];278 -> 331[label="",style="solid", color="burlywood", weight=9];
331 -> 283[label="",style="solid", color="burlywood", weight=3];
332[label="vz12/AProVE_IO vz120",fontsize=10,color="white",style="solid",shape="box"];278 -> 332[label="",style="solid", color="burlywood", weight=9];
332 -> 284[label="",style="solid", color="burlywood", weight=3];
333[label="vz12/AProVE_Exception vz120",fontsize=10,color="white",style="solid",shape="box"];278 -> 333[label="",style="solid", color="burlywood", weight=9];
333 -> 285[label="",style="solid", color="burlywood", weight=3];
334[label="vz12/AProVE_Error vz120",fontsize=10,color="white",style="solid",shape="box"];278 -> 334[label="",style="solid", color="burlywood", weight=9];
334 -> 286[label="",style="solid", color="burlywood", weight=3];
280[label="AProVE_IO []",fontsize=16,color="green",shape="box"];281[label="AProVE_IO (unzip vz110)",fontsize=16,color="green",shape="box"];281 -> 288[label="",style="dashed", color="green", weight=3];
287[label="vz40",fontsize=16,color="green",shape="box"];283[label="primbindIO (IO vz120) (sequence1 (map vz3 vz41))",fontsize=16,color="black",shape="box"];283 -> 289[label="",style="solid", color="black", weight=3];
284[label="primbindIO (AProVE_IO vz120) (sequence1 (map vz3 vz41))",fontsize=16,color="black",shape="box"];284 -> 290[label="",style="solid", color="black", weight=3];
285[label="primbindIO (AProVE_Exception vz120) (sequence1 (map vz3 vz41))",fontsize=16,color="black",shape="box"];285 -> 291[label="",style="solid", color="black", weight=3];
286[label="primbindIO (AProVE_Error vz120) (sequence1 (map vz3 vz41))",fontsize=16,color="black",shape="box"];286 -> 292[label="",style="solid", color="black", weight=3];
288[label="unzip vz110",fontsize=16,color="black",shape="box"];288 -> 293[label="",style="solid", color="black", weight=3];
289[label="error []",fontsize=16,color="red",shape="box"];290[label="sequence1 (map vz3 vz41) vz120",fontsize=16,color="black",shape="box"];290 -> 294[label="",style="solid", color="black", weight=3];
291[label="AProVE_Exception vz120",fontsize=16,color="green",shape="box"];292[label="AProVE_Error vz120",fontsize=16,color="green",shape="box"];293[label="foldr unzip0 ([],[]) vz110",fontsize=16,color="burlywood",shape="triangle"];335[label="vz110/vz1100 : vz1101",fontsize=10,color="white",style="solid",shape="box"];293 -> 335[label="",style="solid", color="burlywood", weight=9];
335 -> 295[label="",style="solid", color="burlywood", weight=3];
336[label="vz110/[]",fontsize=10,color="white",style="solid",shape="box"];293 -> 336[label="",style="solid", color="burlywood", weight=9];
336 -> 296[label="",style="solid", color="burlywood", weight=3];
294 -> 297[label="",style="dashed", color="red", weight=0];
294[label="sequence (map vz3 vz41) >>= sequence0 vz120",fontsize=16,color="magenta"];294 -> 298[label="",style="dashed", color="magenta", weight=3];
295[label="foldr unzip0 ([],[]) (vz1100 : vz1101)",fontsize=16,color="black",shape="box"];295 -> 299[label="",style="solid", color="black", weight=3];
296[label="foldr unzip0 ([],[]) []",fontsize=16,color="black",shape="box"];296 -> 300[label="",style="solid", color="black", weight=3];
298 -> 175[label="",style="dashed", color="red", weight=0];
298[label="sequence (map vz3 vz41)",fontsize=16,color="magenta"];298 -> 301[label="",style="dashed", color="magenta", weight=3];
297[label="vz13 >>= sequence0 vz120",fontsize=16,color="black",shape="triangle"];297 -> 302[label="",style="solid", color="black", weight=3];
299 -> 303[label="",style="dashed", color="red", weight=0];
299[label="unzip0 vz1100 (foldr unzip0 ([],[]) vz1101)",fontsize=16,color="magenta"];299 -> 304[label="",style="dashed", color="magenta", weight=3];
300[label="([],[])",fontsize=16,color="green",shape="box"];301[label="vz41",fontsize=16,color="green",shape="box"];302[label="primbindIO vz13 (sequence0 vz120)",fontsize=16,color="burlywood",shape="box"];337[label="vz13/IO vz130",fontsize=10,color="white",style="solid",shape="box"];302 -> 337[label="",style="solid", color="burlywood", weight=9];
337 -> 305[label="",style="solid", color="burlywood", weight=3];
338[label="vz13/AProVE_IO vz130",fontsize=10,color="white",style="solid",shape="box"];302 -> 338[label="",style="solid", color="burlywood", weight=9];
338 -> 306[label="",style="solid", color="burlywood", weight=3];
339[label="vz13/AProVE_Exception vz130",fontsize=10,color="white",style="solid",shape="box"];302 -> 339[label="",style="solid", color="burlywood", weight=9];
339 -> 307[label="",style="solid", color="burlywood", weight=3];
340[label="vz13/AProVE_Error vz130",fontsize=10,color="white",style="solid",shape="box"];302 -> 340[label="",style="solid", color="burlywood", weight=9];
340 -> 308[label="",style="solid", color="burlywood", weight=3];
304 -> 293[label="",style="dashed", color="red", weight=0];
304[label="foldr unzip0 ([],[]) vz1101",fontsize=16,color="magenta"];304 -> 309[label="",style="dashed", color="magenta", weight=3];
303[label="unzip0 vz1100 vz14",fontsize=16,color="burlywood",shape="triangle"];341[label="vz1100/(vz11000,vz11001)",fontsize=10,color="white",style="solid",shape="box"];303 -> 341[label="",style="solid", color="burlywood", weight=9];
341 -> 310[label="",style="solid", color="burlywood", weight=3];
305[label="primbindIO (IO vz130) (sequence0 vz120)",fontsize=16,color="black",shape="box"];305 -> 311[label="",style="solid", color="black", weight=3];
306[label="primbindIO (AProVE_IO vz130) (sequence0 vz120)",fontsize=16,color="black",shape="box"];306 -> 312[label="",style="solid", color="black", weight=3];
307[label="primbindIO (AProVE_Exception vz130) (sequence0 vz120)",fontsize=16,color="black",shape="box"];307 -> 313[label="",style="solid", color="black", weight=3];
308[label="primbindIO (AProVE_Error vz130) (sequence0 vz120)",fontsize=16,color="black",shape="box"];308 -> 314[label="",style="solid", color="black", weight=3];
309[label="vz1101",fontsize=16,color="green",shape="box"];310[label="unzip0 (vz11000,vz11001) vz14",fontsize=16,color="black",shape="box"];310 -> 315[label="",style="solid", color="black", weight=3];
311[label="error []",fontsize=16,color="red",shape="box"];312[label="sequence0 vz120 vz130",fontsize=16,color="black",shape="box"];312 -> 316[label="",style="solid", color="black", weight=3];
313[label="AProVE_Exception vz130",fontsize=16,color="green",shape="box"];314[label="AProVE_Error vz130",fontsize=16,color="green",shape="box"];315[label="(vz11000 : unzip00 vz14,vz11001 : unzip01 vz14)",fontsize=16,color="green",shape="box"];315 -> 317[label="",style="dashed", color="green", weight=3];
315 -> 318[label="",style="dashed", color="green", weight=3];
316[label="return (vz120 : vz130)",fontsize=16,color="black",shape="box"];316 -> 319[label="",style="solid", color="black", weight=3];
317[label="unzip00 vz14",fontsize=16,color="burlywood",shape="box"];342[label="vz14/(vz140,vz141)",fontsize=10,color="white",style="solid",shape="box"];317 -> 342[label="",style="solid", color="burlywood", weight=9];
342 -> 320[label="",style="solid", color="burlywood", weight=3];
318[label="unzip01 vz14",fontsize=16,color="burlywood",shape="box"];343[label="vz14/(vz140,vz141)",fontsize=10,color="white",style="solid",shape="box"];318 -> 343[label="",style="solid", color="burlywood", weight=9];
343 -> 321[label="",style="solid", color="burlywood", weight=3];
319[label="primretIO (vz120 : vz130)",fontsize=16,color="black",shape="box"];319 -> 322[label="",style="solid", color="black", weight=3];
320[label="unzip00 (vz140,vz141)",fontsize=16,color="black",shape="box"];320 -> 323[label="",style="solid", color="black", weight=3];
321[label="unzip01 (vz140,vz141)",fontsize=16,color="black",shape="box"];321 -> 324[label="",style="solid", color="black", weight=3];
322[label="AProVE_IO (vz120 : vz130)",fontsize=16,color="green",shape="box"];323[label="vz140",fontsize=16,color="green",shape="box"];324[label="vz141",fontsize=16,color="green",shape="box"];}

----------------------------------------

(10)
Complex Obligation (AND)

----------------------------------------

(11)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_foldr(:(vz1100, vz1101), h, ba) -> new_foldr(vz1101, h, ba)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(12) QDPSizeChangeProof (EQUIVALENT)
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. 

From the DPs we obtained the following set of size-change graphs:
*new_foldr(:(vz1100, vz1101), h, ba) -> new_foldr(vz1101, h, ba)
The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3


----------------------------------------

(13)
YES

----------------------------------------

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   new_sequence(vz3, :(vz40, vz41), h, ba, bb) -> new_primbindIO(vz3, vz41, h, ba, bb)
   new_primbindIO(vz3, vz41, h, ba, bb) -> new_sequence(vz3, vz41, h, ba, bb)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(15) QDPSizeChangeProof (EQUIVALENT)
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. 

From the DPs we obtained the following set of size-change graphs:
*new_primbindIO(vz3, vz41, h, ba, bb) -> new_sequence(vz3, vz41, h, ba, bb)
The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4, 5 >= 5


*new_sequence(vz3, :(vz40, vz41), h, ba, bb) -> new_primbindIO(vz3, vz41, h, ba, bb)
The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3, 4 >= 4, 5 >= 5


----------------------------------------

(16)
YES