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

Li-yao Xia lysxia at gmail.com
Tue Jan 23 21:08:16 UTC 2018

```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
```