Hi, On 01/23/2018 02:39 PM, Jean-Marc Alliot wrote:
Thank you very much for your answer, but I still don't get it (I might be not bright enough :-))
Not at all! This is definitely not an obvious problem.
I rewrote the program to suppress all syntactic sugar; for me, the value of the first argument of >>= is never used, so I can't see why it changes anything to put acc as the first argument or anything else (such as return false for example...).
You can erase (acc :: IO Bool) only if acc is in fact pure (i.e., acc = return b), but how would GHC deduce such a fact? - inlining could take care of it on a case-by-case basis at each call site, but ins is recursive, which prevents inlining; - a more general solution for recursive definitions might be some kind of static analysis, that GHC doesn't do; - using Identity instead of IO, then all computations must be pure, and in fact the optimization would apply automatically as a consequence of the lazy (>>=) for Identity.
I would really appreciate a pointer to a chapter of any manual or introduction to Haskell which would be able to explain why with acc as first argument of (>==) the program runs at least 2 hours (I stopped it after 2 hours) and with (return False) it takes less than one second, while the actual value of the first argument of (>>=) is meaningless.
I don't have any good pointers unfortunately. But it may help to expand the folds. ins {1,2,3} acc = do acc ins {1+2,3} (ins {1+3,2} (ins {2+1,3} (... (ins {3+2, 1} acc)))) For the first recursive call to ins... ins {1+2,3} acc1 = do acc1 ins {1+2+3} (ins {3+1+2} acc1) ... substitute that in the former (acc1 = ins {1+3,2} (ins {2+1,3} (... acc))) ins {1,2,3} acc = do acc (ins {1+3,2} (... acc)) ins {1+2+3} (ins {3+1+2} (ins {1+3,2} (... acc))) etc. Li-yao