Hi Ishii-san, On 2014年11月04日 17:53, Hiromi ISHII wrote:
On 2014/11/02 18:50, Travis Cardwell wrote:
Looking at your code [1], I see that you are exporting both `equalDegreeSplitM`, which uses `uniform` from `Control.Monad.Random`, and `equalDegreeFactorM`, which iteratively calls `equalDegreeSplitM`. One of the challenges of using a pure uniform stream is threading the state: since both functions are exported, implementation details would leak anyway.
"Threading the state" means "using ST monad", right? If so, I think we can use algebraic numbers only within ST monad, so it would be too restrictive to do some calculation.
When an algorithm requires values from a uniform distribution, we can generate a uniform stream purely, but progress through the stream must be tracked throughout the whole calculation. This can be done by adding an explicit parameter to each function or via the context of a monad. If the progress through the stream is not tracked, then the same values will be read during each call; that is not uniform, and the algorithm will not work. In my simple π example, "threading the state" is easy because there is only one function used to do the calculation (`step`). The uniform stream is passed as the first parameter, and two values are used during each iteration. The recursive call passes the rest of the stream, so already used values are not used again. It is more difficult to use this technique with complex algorithms because progress through the uniform stream must be tracked through a calculation that uses multiple, complicated functions. For example, if `factorise` is the top level of the CZ algorithm, then you would need to generate the stream there and thread it through `factorSquareFree`, `equalDegreeFactorM`, and `equalDegreeSplitM`. It is possible to do so using explicit parameters and augmented return values, but that would affect any other uses of the latter two functions, as they are exported. Travis