Generators? Iterators?

Christopher Howard

23 Apr 2016 23 Apr '16

5:28 a.m.

Hi. I'm more in the shallow end of the Haskell pool right now, so forgive me if this is really basic... In Haskell, what is the class for things that can provide an infinite sequence? I mean, things that produce a value as well as function for producing the next value? Clearly RandomGen does this, but what is the next level of abstraction above RandomGen (i.e., RandomGen minus the randomness aspect). -- http://justonemoremathproblem.com To protect my privacy, please use PGP encryption. It's free and easy to use! My public key ID is 0x340EA95A (pgp.mit.edu).

Show replies by date

Erik de Castro Lopo

23 Apr 23 Apr

5:47 a.m.

Christopher Howard wrote:

...

Hi. I'm more in the shallow end of the Haskell pool right now, so forgive me if this is really basic... In Haskell, what is the class for things that can provide an infinite sequence?

People generally do this with lists and Haskell's lazy evaluation. For instance: let x = [1 .. ] produces the infinite list [1,2,3, .....]. Haskell's lazily evaluated lists allow for incredibly elegant solutions for some sorts of problems, like the spigot algorithm for generating (among other things) the digits of PI: http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/

Michael Burge

6:36 a.m.

There's Foldable for 'things that can be converted to lists', or Traversable for 'things that can be converted to lists underneath a Functor'. https://wiki.haskell.org/Foldable_and_Traversable On Fri, Apr 22, 2016 at 10:47 PM, Erik de Castro Lopo wrote:

...

Christopher Howard wrote:

...
Hi. I'm more in the shallow end of the Haskell pool right now, so forgive me if this is really basic... In Haskell, what is the class for things that can provide an infinite sequence?

People generally do this with lists and Haskell's lazy evaluation. For instance:

let x = [1 .. ]

produces the infinite list [1,2,3, .....].

Haskell's lazily evaluated lists allow for incredibly elegant solutions for some sorts of problems, like the spigot algorithm for generating (among other things) the digits of PI:

http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

Erik -- ---------------------------------------------------------------------- Erik de Castro Lopo http://www.mega-nerd.com/ _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

Jack Henahan

6:07 a.m.

Types that admit a Monad instance can be used to represent such sequences (and more general ones besides).

...

On Apr 23, 2016, at 01:28, Christopher Howard wrote:

Hi. I'm more in the shallow end of the Haskell pool right now, so forgive me if this is really basic... In Haskell, what is the class for things that can provide an infinite sequence? I mean, things that produce a value as well as function for producing the next value? Clearly RandomGen does this, but what is the next level of abstraction above RandomGen (i.e., RandomGen minus the randomness aspect).

-- http://justonemoremathproblem.com To protect my privacy, please use PGP encryption. It's free and easy to use! My public key ID is 0x340EA95A (pgp.mit.edu).

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

Joachim Durchholz

7:22 a.m.

Am 23.04.2016 um 07:28 schrieb Christopher Howard:

...

I mean, things that produce a value as well as function for producing the next value?

In Haskell, the runtime decides when to evaluate things, so the compiler already compiles every single subexpression into code that can double as a generator. So... you have a list? The code that defines how everything after the first element should be constructed is already your generator. You have a tree? The code that defines the content of the child nodes is already your generator. You have an arbitrary recursively-defined data structure? The code that defines things "in the depth" is already a generator. You don't need to code generators. Also, you don't need to explicitly call them; you just pull up the values from the depth of the data structure, and the runtime will decide when to pull up a cached value or call the generator. Quite nifty, very flexible (because you never need to rearrange your code from function to generator or vice versa), somewhat hard to control.

3362

Age (days ago)

3362

Last active (days ago)

List overview

Download

4 comments

5 participants

participants (5)

Christopher Howard
Erik de Castro Lopo
Jack Henahan
Joachim Durchholz
Michael Burge