Re: Iterable for all natural numbers?

An idea I had for a more general solution would be to create a Stream implementation in which the tail pointer were a weak reference - if the reference is garbage collected, the stream regenerates it. Then you could freely create infinite streams, including but not limited to the integers, without worrying about the stream being cached and taking up huge amounts of memory.   On Tue, Jan 27, 2009 at 5:25 PM, Seth Tisue <seth@tisue.net> wrote:

>>>>> "mtopol" == mtopol  <mt4web@gmail.com> writes:

 mtopol> I still kind of expect to
 mtopol> have at least something like open-ended Ranges in the standard
 mtopol> library. For example, Range.from(Int), just like we have
 mtopol> Stream.from(Int), but without caching the computed
 mtopol> elements.

It seems like a good idea to me.

--
Seth Tisue / http://tisue.net
lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/

But this would still strain the GC, introduce slowdowns, etc. There is a
quite large and important class of sequences whose members are cheaper to
calculate than to look up (factoring in the overhead of memory allocation
and the maintenance of the data structure). This doesn't say that there
aren't many good uses for a weakly cached Stream.

Paul Chiusano-2 wrote:
>
> An idea I had for a more general solution would be to create a Stream
> implementation in which the tail pointer were a weak reference - if the
> reference is garbage collected, the stream regenerates it. Then you could
> freely create infinite streams, including but not limited to the integers,
> without worrying about the stream being cached and taking up huge amounts
> of
> memory.
>

In fact, I see two useful abstractions:

1. An infinite, random-accessible Iterable based on a user-provided function
from index to element;

2. An infinite, sequential-only Iterable based on user-provided initial
state and a function from state to the pair (newState, element).

>>>>> "mtopol" == mtopol writes:

mtopol> In fact, I see two useful abstractions:

mtopol> 1. An infinite, random-accessible Iterable based on a
mtopol> user-provided function from index to element;

If we had infinite Ranges, then you wouldn't need this abstraction, I
think, since you could just call map() on an infinite Range.

Seth Tisue wrote:
>
> mtopol> 1. An infinite, random-accessible Iterable based on a
> mtopol> user-provided function from index to element;
>
> If we had infinite Ranges, then you wouldn't need this abstraction, I
> think, since you could just call map() on an infinite Range.
>

True, indeed. The result type of map would then have to be an infinite
random-access sequence trait. The same trait would be extended by the
infinite Range.

For 1, you could just create a new Seq implementation:   class FunctionSeq[E](f: Int => E) extends Seq[E] {
  def length = Int.MaxValue
  def apply(i: Int) = f(i)
  def elements = (0 until length).elements.map(apply)
}
scala> new FunctionSeq[Int](_ * 2 + 1).take(7)
res8: Seq[Int] = List(1, 3, 5, 7, 9, 11, 13)
Likewise, for 2, I'd just create a new Iterable implementation, as you've already done. I would generalize it so that your state is not required to be an array -   class EphemeralStream[E,S](h: (E,S), f: (E,S) => (E,S)) extends Iterable[E] {
  def elements = Iterator.single(h._1) ++ new EphemeralStream(f(h._1,h._2),f).elements
}   scala> new EphemeralStream[Int,Int]((1,0),(lead,follow) => (lead+follow,lead)).take(7)
res9: Collection[Int] = ArrayBuffer(1, 1, 2, 3, 5, 8, 13)   Iterable.take has been deprecated, so you might want to define a new trait and extend that instead of Iterable directly. Alternately, you could probably extend Stream.   Paul   On Wed, Jan 28, 2009 at 9:48 AM, mtopol <mt4web@gmail.com> wrote:

In fact, I see two useful abstractions:

1. An infinite, random-accessible Iterable based on a user-provided function
from index to element;

2. An infinite, sequential-only Iterable based on user-provided initial
state and a function from state to the pair (newState, element).
--
View this message in context: http://www.nabble.com/Iterable-for-all-natural-numbers--tp21639715p21707191.html
Sent from the Scala mailing list archive at Nabble.com.

Paul Chiusano-2 wrote:
>
> For 1, you could just create a new Seq implementation:
>
> class FunctionSeq[E](f: Int => E) extends Seq[E] {
> def length = Int.MaxValue
> def apply(i: Int) = f(i)
> def elements = (0 until length).elements.map(apply)
> }
> scala> new FunctionSeq[Int](_ * 2 + 1).take(7)
> res8: Seq[Int] = List(1, 3, 5, 7, 9, 11, 13)
>

I was using Ints as an example, but a truly useful abstraction would for
sure have to handle BigInts for index. That excludes the possibility of
using the existing Range and the RichInt.until method.

Paul Chiusano-2 wrote:
>
> Likewise, for 2, I'd just create a new Iterable implementation, as you've
> already done. I would generalize it so that your state is not required to
> be
> an array -
>
> class EphemeralStream[E,S](h: (E,S), f: (E,S) => (E,S)) extends
> Iterable[E]
> {
> def elements = Iterator.single(h._1) ++ new
> EphemeralStream(f(h._1,h._2),f).elements
> }
>
> scala> new EphemeralStream[Int,Int]((1,0),(lead,follow) =>
> (lead+follow,lead)).take(7)
> res9: Collection[Int] = ArrayBuffer(1, 1, 2, 3, 5, 8, 13)
>

You don't need the previous element AND internal state separately as input;
state alone is enough. If needed, the client can define his state to contain
the previous element. Your way makes the specific case of Fibs more elegant
to implement, but it also becomes an impediment for different cases.

My improved version looks like this:

class InfiniteIterable[S, E](init: S, calcNext: S => (S, E)) { ... }
object InfiniteIterable {
def apply[S, E](init: S)(calcNext: S => (S, E)) = new
InfiniteIterable(init, calcNext)
}

Example:

val fibs = InfiniteIterable[(BigInt, BigInt), BigInt]((1,0)) {case(follow,
lead) =>
val next = follow+lead; ((lead, next), next)
}
def naturals(start:Int) = InfiniteIterable[Int, Int](start) (
prevNat => (prevNat + 1, prevNat)
)

Paul Chiusano-2 wrote:
>
> Iterable.take has been deprecated, so you might want to define a new trait
> and extend that instead of Iterable directly. Alternately, you could
> probably extend Stream.
>

It will very probably be un-deprecated because there was no reason to. On
the other hand, takeWhile is the one that should, and probably will, get
deprecated in Iterable because it doesn't make sense for unordered
collections. Same thing for drop/dropWhile and related methods. This was the
conclusion of a recent thread:

http://www.nabble.com/Re%3A--scala--Deprecations-in-Iterable-p21526128.html

Paul Chiusano schrieb:
> Iterable.take has been deprecated,

But that is a bug that will be fixed in 2.8:
http://www.nabble.com/Re%3A--scala--Deprecations-in-Iterable-p21526128.html

- Florian