<div>This monad seems to be basically the same as Prompt; see <a href="http://www.haskell.org/pipermail/haskell-cafe/2007-November/034830.html">http://www.haskell.org/pipermail/haskell-cafe/2007-November/034830.html</a>, the only difference I see is that Prompt allows the return value's type to be based on the request instead of forcing everything to be wrapped in a single result type.
</div>
<div> </div>
<div>You implemented the monad operations exactly the same as Prompt, and your bind operator suffers from the same quadratic behavior problem that was pointed out in that thread.</div>
<div> </div>
<div>As was pointed out there, what you are doing is turning the potential side effects of your computations into a term algebra, which allows you to write different "interpretation" functions to use when running the calculation (the reqf passed to runSC). As far as I can tell, this pattern is general enough to implement any computation, so it's not surprising that you found it possible to use it to implement parallel computation.
</div>
<div> </div>
<div>As an example, here's the State monad implemented in terms of SCalc:</div>
<div> </div>
<div>> data StateReq s = Get | Put s</div>
<div>> get :: SCalc (StateReq s) s s</div>
<div>> get = SCStage Get return</div>
<div>> put :: s -> SCalc (StateReq s) s ()</div>
<div>> put s = SCStage (Put s) (const $ return ())</div>
<div>></div>
<div>> runState :: SCalc (StateReq a) s b -> s -> (a, s)</div>
<div>> runState (SCResult v) s = (v, s)</div>
<div>> runState (SCStage Get cont) s = runState (cont s) s</div>
<div>> runState (SCStage (Put s) cont) _ = runState (cont s) s<br> </div>
<div>I think it's a useful pattern and I definitely am getting a lot of use out of Prompt in my code. But I'm trying to figure out the best way to eliminate the quadratic behavior of (>>=) that is exhibited by, for example:
</div>
<div> </div>
<div>foldl1 (>>=) $ take 100 $ repeat $ (\x -> put (x+1) >>= get) $ 0</div>
<div> </div>
<div>The only way I've found so far is to wrap Prompt inside of ContT which solves the problem in much the same way that difference lists (newtype DList a = [a] -> [a]) solve the problem of quadratic time append for lists.
</div>
<div> </div>
<div> -- ryan</div>