'Re: [Haskell-cafe] MonadRandom and traversing infinite streams'

[prev in list] [next in list] [prev in thread] [next in thread] 

List: haskell-cafe
Subject: Re: [Haskell-cafe] MonadRandom and traversing infinite streams
From: Petr Pudlák <petr.mvd () gmail ! com>
Date: 2014-05-31 19:59:58
Message-ID: CABSda-fgSTwJiiFL0+KqDVnqBO_mT-1sDGfWuLwvQd42-=iS1Q () mail ! gmail ! com
[Download RAW message or body]

[Attachment #2 (multipart/alternative)]

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@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
>
>

[Attachment #5 (text/html)]

<div dir="ltr"><div>Hi Brent, </div>thanks for pointing me to the distributive \
functors, I&#39;ll have a look at them. Indeed, `sequenceInf` is almost \
`sequenceA`. The difference is that `sequenceA` doesn&#39;t work for infinite lists \
for most monads, including `State` and `Rand`, as in this example:

<br>main = do<br>       let infSeq = sequence $ repeat getRandom<br>       (xs, y) \
&lt;- evalRandIO ((,) &lt;$&gt; infSeq &lt;*&gt; getRandom) :: IO ([Int], Int)<br>    \
print (take 5 xs)<br>       print y<br><br>Here `y` will always diverge. Your example \
worked only because the generator was never used for anything after producing a lazy \
infinite list.<br>

<br>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.<br>

<br>   Petr<br></div><div class="gmail_extra"><br><br><div \
class="gmail_quote">2014-05-31 21:35 GMT+02:00 Brent Yorgey <span dir="ltr">&lt;<a \
href="mailto:byorgey@seas.upenn.edu" \
target="_blank">byorgey@seas.upenn.edu</a>&gt;</span>:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"><div class="">On Sat, May 31, 2014 at 08:58:40PM +0200, Petr \
Pudlák wrote:<br> &gt; Hi Brent and Wouter,<br>
&gt;<br>
&gt; looking at SO questions<br>
&gt;<br>
&gt; <a href="http://stackoverflow.com/q/14494648/1333025" \
target="_blank">http://stackoverflow.com/q/14494648/1333025</a><br> &gt; <a \
href="http://codereview.stackexchange.com/q/52149/15600" \
target="_blank">http://codereview.stackexchange.com/q/52149/15600</a><br> &gt;<br>
&gt; threre are monads and applicative functors that support<br>
&gt;<br>
&gt; ```<br>
&gt; sequenceInf :: S.Stream (f a) -&gt; f (S.Stream a)<br>
&gt; ```<br>
<br>
</div>Hi Petr,<br>
<br>
Perhaps what you are looking for is distributive functors:<br>
<br>
   <a href="http://hackage.haskell.org/package/distributive-0.4/docs/Data-Distributive.html#t:Distributive" \
target="_blank">http://hackage.haskell.org/package/distributive-0.4/docs/Data-Distributive.html#t:Distributive</a><br>

Distributive functors g support 
 
 distribute :: Functor f =&gt; f (g a) -&gt; 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 -&gt; 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 -&gt; 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) -&gt; State s (f a), f must be Traversable. But this is 
just &#39;sequenceA&#39; 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: 
 
 &gt; rs &lt;- evalRandIO . T.sequenceA . repeat . getRandomR $ (0,1 :: Double) 
 &gt; take 3 rs 
 [0.2873830633564285,0.7737439541152851,0.5740433935180629] 
 
If you have something different in mind I&#39;d love to hear it explained 
in more detail. 
 
Brent 
 
</blockquote></div> </div>

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

[prev in list] [next in list] [prev in thread] [next in thread] 