[Haskell-cafe] How to use randomized algorithm within the implementation of pure data structures?

[Travis Cardwell]

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