Lazy sequences

[jspahrsummers]

Sequences were originally suggested for Mantle in Mantle/Mantle#1, but after doing some work on a sequences branch there, I'm wondering if it makes more sense to provide this facility in ReactiveCocoa.

Conceptually, sequences and subscribables support many of the same kinds of operations (map, filter, concat, cons, etc.), and both represent streams of things.

There are a couple of major differences, though:

• Sequences can be lazy, and are inherently repeatable (i.e., not time-based). Subscribables are neither of those things.
• Subscribables model errors and completion, neither of which apply to a general-purpose sequence.

I think subscribables can be represented as sequences, but the opposite is not true – sending a sequence through a subscribable would require evaluating the entire thing.

@joshaber @xpaulbettsx @jonsterling Any thoughts on this?

[joshaber]

I think the usage of both is different enough that they can't be the same thing.

Subscribables are built around the idea of being pushed things while lazy sequences are built around resolving things as requested. Those two things seem inherently at odds. I'm not sure there's any way to resolve that without corrupting one or the other.

[jspahrsummers]

I think I agree with that assessment, but they're still conceptually similar enough that I think it makes sense to provide sequences within RAC, and perhaps offer operations that work on either sequences or subscribables.

And, again, subscribables can be modeled as sequences – not 100% accurately, but closely enough that some sort of adapter could be useful.

[anaisbetts]

Subscribables model errors and completion, neither of which apply to a general-purpose sequence.

Sequences and Observables from a theoretical perspective, are actually completely equivalent. When you ask for the next item in a Sequence, it could throw an error (in languages that actually have Exceptions, 🚎). That's how you'd model errors in a Sequence - and of course, when you ask for the next item, it could say "I don't have anything"; completion.

Now, modeling a async operation completion as a Sequence would of course be silly, since you'd have to park yourself until it completes, but these two concepts really are unified

sending a sequence through a subscribable would require evaluating the entire thing.

Not true, you can return a Subscribable that only upon subscription, evaluates the Sequence. Subscribe is the Rx equivalent of evaluating a Sequence.

[jspahrsummers]

Sequences and Observables from a theoretical perspective, are actually completely equivalent. When you ask for the next item in a Sequence, it could throw an error (in languages that actually have Exceptions, 🚎).

Exceptions are an exceptionally (pun intended) poor model for this, because they're not conceptually clean in pure F[R]P. It'd be much cleaner to force everything into an in-band communication stream.

… and of course, when you ask for the next item, it could say "I don't have anything"; completion.

This is more of a ReactiveCocoa-specific problem, but we don't have a way to represent this in a way that doesn't conflict with values already in use. nil is a perfectly valid "next" value in streams, RACUnit does other things, etc. If we added this, it'd be a breaking change.

Not true, you can return a Subscribable that only upon subscription, evaluates the Sequence. Subscribe is the Rx equivalent of evaluating a Sequence.

Sure. But that's still evaluating the whole sequence instead of doing it incrementally – for example, infinite sequences couldn't be modeled as subscribables. So you'd really be saying "only sequences that can be eagerly evaluated can become subscribables."

[anaisbetts]

So you'd really be saying "only sequences that can be eagerly evaluated can become subscribables."

Not true either :) Though seeing why is a bit more difficult:

IObservable<T> ToObservable(IEnumerable<T> inputSequence)
{
    return Observable.Create(subj => {
        bool hasUnsubscribed = false;
        var enumerator = inputSequence.GetEnumerator();

        while(hasUnsubscribed && enumerator.MoveNext()) {
            subj.OnNext(enumerator.Value);
        }

        subj.OnCompleted();

        // When they unsubscribe, we'll give up walking the list
        return Disposable.Create(() => hasUnsubscribed = true);
    });
}

So, if I do something like:

ToObservable(anInfiniteSequence).Take(5).Subscribe(Console.WriteLine);

The Take will terminate the parent Subscription early. But that infinite sequence is only evaluated on the Subscribe, it's Lazy.

[jspahrsummers]

Interesting. I think @joshaber did something conceptually similar to this for his implementation of generators, but it ended with a lot of race conditions/overworking because disposables aren't as deterministic as they could be.

[joshaber]

Yes, that's exactly what the old generator implementation did. The problem was that the generator could create more values than needed before the disposable was returned and the caller had a chance to terminate it.

[joshaber]

(See https://github.com/github/ReactiveCocoa/blob/18f9cce521fc426ee7945fa6ab64f8b69c0a1ee0/ReactiveCocoaFramework/ReactiveCocoa/RACSubscribable.m#L120 for reference.)

[jspahrsummers]

It seems like the use of backgroundScheduler would cause issues there. If the generator is synchronous with respect to take:, wouldn't it terminate appropriately?

[joshaber]

Right, you can make it work but the API is shit.

[jspahrsummers]

I think that's a good argument against generators as such, but it could work more cleanly for sequences. I'll see if I can come up with something interesting.