[Haskell-cafe] I really don't understand this

[Li-yao Xia]

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