[Haskell-cafe] MonadRandom and traversing infinite streams

[Petr Pudlák]

Hi Brent,

thanks for pointing me to the distributive functors, I'll have a look at
them.

Indeed, `sequenceInf` is almost `sequenceA`. The difference is that
`sequenceA` doesn't work for infinite lists for most monads, including
`State` and  `Rand`, as in this example:

main = do
    let infSeq = sequence $ repeat getRandom
    (xs, y) <- evalRandIO ((,) <$> infSeq <*> getRandom) :: IO ([Int], Int)
    print (take 5 xs)
    print y

Here `y` will always diverge. Your example worked only because the
generator was never used for anything after producing a lazy infinite list.

But it can be implemented for `Rand` in a different way (as `sequenceInf`),
because it can split the generator, return one part as the output, and use
the other part to lazily generate an infinite randomized list.

  Petr


2014-05-31 21:35 GMT+02:00 Brent Yorgey <byorgey at seas.upenn.edu>:

> On Sat, May 31, 2014 at 08:58:40PM +0200, Petr Pudlák wrote:
> > Hi Brent and Wouter,
> >
> > looking at SO questions
> >
> > http://stackoverflow.com/q/14494648/1333025
> > http://codereview.stackexchange.com/q/52149/15600
> >
> > threre are monads and applicative functors that support
> >
> > ```
> > sequenceInf :: S.Stream (f a) -> f (S.Stream a)
> > ```
>
> Hi Petr,
>
> Perhaps what you are looking for is distributive functors:
>
>
> http://hackage.haskell.org/package/distributive-0.4/docs/Data-Distributive.html#t:Distributive
>
> Distributive functors g support
>
>   distribute :: Functor f => f (g a) -> g (f a)
>
> for all Functors f.  Also, a functor is distributive if and only if it
> is representable, that is, if it is isomorphic to (r -> a) for some
> type r.  Another way to think about this is that in order to be able
> to lazily zip an infinite number of copies of g, it must be that g is
> composed of only products; you can think of (r -> a) as an r-indexed
> product of a values.  If g contains any sums (e.g. Maybe and [] both
> have two constructors, i.e. are a sum of two types) then you need to
> examine the entire list before you can decide the structure of the
> output.
>
> As for instances of MonadRandom supporting sequenceInf or distribute
> or whatever, are you talking about e.g. Rand?  Now that I think about
> it, perhaps Distributive is not exactly what you are looking for: Rand
> is not distributive, because (State s) is not.  Intuitively the reason
> State is not distributive is that the order matters, so in order to do
> f (State s a) -> State s (f a), f must be Traversable.  But this is
> just 'sequenceA' from the Traversable instance for f; the only thing
> required of State s is that it is Applicative.  So I guess I am not
> sure whether you really need anything extra beyond what is already
> provided (there is an Applicative instance for Rand).  This works for me:
>
>   > rs <- evalRandIO . T.sequenceA . repeat . getRandomR $ (0,1 :: Double)
>   > take 3 rs
>   [0.2873830633564285,0.7737439541152851,0.5740433935180629]
>
> If you have something different in mind I'd love to hear it explained
> in more detail.
>
> Brent
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20140531/b8885176/attachment.html>