MonadRandom and traversing infinite streams

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

MonadRandom and traversing infinite streams

Petr Pudlák
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)
```

that is, allow lazy traversals of streams (infinite lists). Namely those that don't produce any additional output.

And instances of MonadRandom seem to have valid implementations of `sequenceInf`, which would allow to produce lazy infinite randomized lists (basically a generalization of `getRandoms`).

My proposal is to add

```
class Applicative f => LazyApplicative f where
    sequenceInf :: S.Stream (f a) -> f (S.Stream a)
    sequenceInf = traverseInf id

    traverseInf :: (a -> f b) -> S.Stream a -> f (S.Stream b)
    traverseInf f = sequenceInf . S.map f
```

to a module in Stream package (for example `Control.Applicative.Lazy`), and add its instances into `MonadRandom`.

What do you think? I'd be willing to send patches.

  Best regards,
  Petr

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: MonadRandom and traversing infinite streams

Brent Yorgey-2
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

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: 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 <[hidden email]>:
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



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe