For languages that allow generators (iterables where elements are determined by a function), what are the pros and cons of having a unique type for generators?
For example, languages like python have a special type for generators, meaning there's no immediate shared superclass for lists and generators. Other languages like scala have it as a LazyList type (or similar), meaning the generators can be treated as normal lists.
Yes, in the context of a language that isn't otherwise lazy or memoised.
There are real semantic differences between generators and lists: you can index into a list arbitrarily, and retrieve a value more than once. Treating all generators as lists requires that every produced value be remembered for the life of the generator to support these. For most uses of generators, this would be all cost with no benefits.
You can explicitly convert a generator into a non-lazy list if desired (list(gen) in Python, enumerable.ToList() in C#, or just a loop anywhere). It would be reasonable to include a standard-library memoised-list type for this purpose too, for the cases where you want random access to a prefix of the sequence. It's not too hard to build one, either.
It isn't possible to recover this efficient generator behaviour from a list, so the right default is to produce an enumerable generator and let the programmer make the conversion explicitly in the cases where they need it.
However, some list operations can reasonably be applied to a generator, and it's appropriate for the generator type to support these. This wouldn't be making the generator a list, but extending the generator type with only suitable implementations of the operations that do make sense within its evaluation model. A generator type that is only iterable while lists offer, for example, map or filter operations, is subpar.
In a lazy language, like Haskell, "generators" are lists and all lists are lazy, and the system is (to some extent) clever enough to mitigate those costs, but that isn't generally possible. That works fine for those languages, whose overall semantics matches that approach and is amenable to optimising out unused values. This is a good fit for these languages, and a poor fit in others.
Why should you not be able to do generator.map(x => x * 2)? A generator is, at its core, a collection with a strict initial run and a function from an element to the next. When you access an element not in the run, all elements up to the one you want are computed with the function and pushed to the run (this can happen purely, as long as the function itself is pure). The choice to not make generators collections is either that of implementation issues (JS' function*(){}) returns a raw object, not a class, and therefore can't really have methods on it) or lack of functions on collections themselves.
generator.map(x => x * 2)?" Unless you have lazy evaluation, then what would happen when generator is infinite? To examine this more in depth generators aren't "collections-like". To some extend maybe yes. But they are sources of values, at the end. They can supply limited or unlimited amount of values. Now, lazy evaluation can mitigate this. Then you can chain your operations but will only run when you finalise it. For example generator.map(x => x*2).filter(x => x < 100).take(10).giveMeAList() will not walk through an infinite sequence.
$\endgroup$
generator.map returns another generator, which has eagerly mapped the run and replaced the function with one that incorporates the mapping (this is how Scala, usually eagerly evaluated, does it.) Generators are lazy in nature, even in eager languages.
$\endgroup$
Commented
May 19, 2023 at 8:10