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

Functions are expected to terminate; therefore, one needs the concept of a continuing computation. In Haskell, monads represent the continuing context containing the terminating functions. Having your functions run in a monad is not a limitation. -- -- Sent from an expensive device which will be obsolete in a few months! :D Casey On Nov 4, 2014 5:33 AM, "Carter Schonwald" wrote:

Threading the state can also mean using the STATE monad as suggested Earlier. On Nov 4, 2014 3:54 AM, "Hiromi ISHII" wrote:

...

Hi,

On 2014/11/02 18:50, Travis Cardwell wrote:

...

Indeed: many algorithms merely require values from a uniform distribution, not necessarily random numbers. I was hopeful that Cantor-Zassenhaus would be one of them.

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.

...

Great work, by the way! :)

Thanks!

-- Hiromi ISHII konn.jinro@gmail.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe