#4148: improve new recursive do syntax
---------------------------------+------------------------------------------
Reporter: guest | Owner:
Type: feature request | Status: new
Priority: low | Milestone: 7.6.1
Component: Compiler | Version: 6.12.3
Keywords: | Os: Unknown/Multiple
Architecture: Unknown/Multiple | Failure: None/Unknown
Difficulty: Unknown | Testcase:
Blockedby: | Blocking:
Related: |
---------------------------------+------------------------------------------
Comment(by lerkok):
Simon: Regarding your question why segmentation was ever implemented in
the first place, here's a concrete example that'll hopefully demonstrate
why segmentation is an essential part of monadic recursion.
Consider the following simple function:
{{{
produce :: [Int] -> IO [Int]
produce xs = return $ take 10 [1+x | x <- xs]
}}}
Clearly `produce` doesn't need to be in the IO monad, but that's besides
the point. The crucial thing is
that it represents some function doing IO before returning a result. (In a
more realistic instance, for
example, it can read the constant `10` it uses in the call to `take` from
a configuration file; or perform
some other similar IO action to implement some other behavior.)
Let's also imagine a caller to this function, of the following form:
{{{
run :: IO [Int]
run = do rec xs <- produce (1:xs)
return xs
}}}
For instance, `run` can be used to implement a recurrence based algorithm,
by passing a variant of its
result to itself. (Think Fibonacci, Hamming codes, etc; for example, where
the computation of the "next"
element requires some monadic action.)
The above code will work just as expected today in GHC, with `run`
evaluating to the list `[2..11]`. So far, everything is just fine.
Now, consider the following version of `run`, which simply prints the
length of the list before
returning its result, but it is otherwise equivalent to `run` above:
{{{
run2 :: IO [Int]
run2 = do rec xs <- produce (1:xs)
print $ length xs
return xs
}}}
For instance, I could imagine adding that `print` statement as part of
debugging my code; or doing some
other useful computation based on the result of the call to `produce`. If
you execute `run2` today in
GHC, you'll find that it'll work just as you expect: It'll first print
`10`, and then return the
list `[2..11]`.
'''Here's the problem:''' If you change the translation of `rec` so that
it no longer performs segmentation, then
`run2` will *diverge*. Why? Because the trailing computation in printing
the length of the final list
will interfere with the recursive computation. In more fancy terms, since
the `mfix` for the IO monad (the good old fixIO) does not satisfy the
right-shrinking law, the non-recursive computation in the `mfix` loop
cannot be lifted out. This is a fundamental limitation of the IO monad:
There's no `mfix` for it that satisfies the right-shrinking law. (Of
course, IO is just one example, many other monads have the same issue.)
So, what does this mean? In my mind, it really means two things:
* The promised correspondence that
{{{
mdo ...
e
}}}
is the same as
{{{
do rec ...
e
}}}
only holds provided the `rec` translation performs segmentation. If we
don't do segmentation, then the correspondence is no longer valid as
exemplified above.
* Segmentation is really an essential part of the `mdo` (or `do` `rec`)
semantics, if I write
{{{
do rec xs <- produce (1:xs)
print $ length xs
return xs
}}}
Whether I keep the `print` in there or not should change anything. But if
you do not do segmentation, the presence of `print` '''will''' change the
semantics, causing it to diverge. (Imagine how awkward it would be to
insert a "debugging" printf inside your `mdo` or `do` `rec` block, only to
have it diverge all of a sudden.)
I'm hoping the above example will convince us that segmentation is an
essential feature of recursive monadic bindings. Based on this, I think
proposal B provides a good compromise since it brings back `mdo` with its
original intent, while keeping `rec` simple.
To summarize, I'd humbly suggest we should do a minor variant of your
proposal B:
* Bring back `mdo` with segmentation (as was originally implemented in
GHC)
* Change `rec` so it does ''not'' do segmentation
* Furthermore, allow `rec` only inside an immediately enclosing `do`
block; syntactically rejecting it inside an `mdo`.
I think this proposal is in the spirit of the original work on recursive
monadic bindings, while also keeping `rec` quite simple as favored by Ross
and Ryan.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4148#comment:20>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
