Alastair wrote:
> | It looks to me as though you've redicovered the importance of tail calls.
Koen replied:
> It is indead clear that this has to do with tail calls. But what is the
> solution? Is it possible to make a writer monad definition that allows
> functions like
>
> foo 0 = return ()
> foo n =
> do write "a"
> x <- foo (n-1)
> write "b"
> return x
>
> to run without space leak? Or are we forced to rewrite "foo"?
>
> Note that the described behavior doesn't hold for _all_ monads. We can of
> course take for the definition of W:
>
> type W = IO
>
> write = putStr
>
> And then (at least in Hugs) there is no space leak.
> But this is not what you want, because now we are forced to have "foo"
> only on toplevel...
I just tried this on Hugs. I was expecting it to run out of stack space
but, in fact, it runs out of heap space first. So your counterexample
turns out to be an example :-)
It was clear it was going to do one or the other because it's not tail
recursive. On some systems such as GHC, I expect you'll run out of stack
first, on Hugs you happen to run out of heap first. You can trade stack
space for heap space but whichever you run out of, you're still running
out of space.
I can't think of any non-degenerate monad for which this program
will run in constant space. For any useful monad, it's clear that
it must use (at least) O(n) space because it has to somehow remember to
write "b" as many times as it writes "a". Standard results tell us
that this is beyond a finite state machine (ie something that runs in
constant space). (You could imagine rewriting this particular program
to use a tail recursive function to print out n "a"s then another tail
recursive function to print out n "b"s - but I don't expect a compiler
to do this for me and I don't think it's possible to write a non-trivial
monad which somehow accomplished this either.)
In summary:
Tail calls are the problem here.
I don't believe there's anything deeper to look for - you just have to
write your monadic code in a tail recursive style.
I believe the problem applies to all non-trivial monads.
Alastair Reid, Yale Haskell Project
ps I didn't define the term "trivial monad" - let me give example:
The constant monad M_c where
return x = c
m >>= k = c
is certainly trivial - there are so many identities in this
monad that every program of this type can be run in constant
space. (Moggi has explored more formal definitions of triviality -
these might be applicable here.)
pps None of the above answers the original question which was:
Is it possible to write a monad such that this equality holds
both denotationally and operationally
do {x <- foo; return x} = foo
For all I know, the answer to this question is
"yes, with sufficient sneakiness".
