(Partially) Sorting a lazy-evaluated collection

Question

So I'm trying to implement a lazy-evaluating data type (in PHP, though that shouldn't matter any) where you can queue up actions to take on a set of data. This data can come (theoretically) from any traversable object: arrays, generators, and other iterable objects.

So for instance, given a $collection object containing a unsorted array of integers, you could call methods on that object like map($callback) or filter($callback) and it will return a new Collection instance with the action queue of the original collection appended with the called method. No queued actions are executed until the absolute last possible moment, e.g. when the data is actually going to be used for output, reduction to a simple value, and even methods like some/every/find only iterate as much as they need to. This restriction is made easier to implement by the collection (currently) not exposing any sort of index access interface.

The underlying implementation once execution is triggered will try and iterate over the underlying data set as few times as possible by logically grouping the queued operations where possible to avoid creating any intermediate representations of the data as much as possible. So if you have multiple map() operations set up, then it'll compose those. Filter operations can be grouped in to this single execution loop too, all it means is that when the filter/rejection test function fails then the execution ends for that iteration element.

And this all works, right up until one edge case: sorting. Sorting (unless there's a better idea I'm missing here) requires a separate iteration cycle to begin so that the array can begin. Which I don't mind doing, except in certain cases like where I want only, say, exclusively the first n elements of the sorted collection. At that point, it seems to me that there's no way to know what those values are without sorting the entire collection. Is there any way to avoid that? Otherwise it's going to be a waste of (most of) the advantages of lazy evaluation, and I'd like to avoid that...

Answer 1

In short, no, there is no way to do sorting on an incomplete collection unless you will delay sorting until the very end wen the collection is already present.

Longer version: Sorting by definition involves evaluating the entire set of items and arranging them in the right order. I doubt you can do sorting on the the collection without having the entire collection instantiated.

If your collection consists of rather large complex objects, consider having object metadata that is required for sorting available upon sorting, and load the rest of the object data as required later on into the execution cycle.

Answer 2

Taking clues from LINQ, a typical way to workaround this fundamental impossibility is to implement a Take function, which takes the first N values from the lazy collection (or enumerator) and then process only those N values.

To use it, the user must specify how many values to "take" each time.

Collections which are already sorted or histogrammed (binned in a sorted order) can perform lazy take, because the sorting has already been done.

In some limited use cases, one could do something similar to:

• Suppose the values are integers in the range 0 - 99, inclusive.
• To retrieve all items in the range 0 - 9, do a Filter between 0 and 9 inclusive, whose result is then sorted.
• To retrieve all items in the next range of 10 - 19, do another Filter between 10 and 19 inclusive, and then sort that.

This requires some prior knowledge of the numerical distribution of data, but it does not require a complete sorting (ranking) of all of the data.

In particular, this range filtering approach will not be able to produce correct result unless a lower bound on the numerical data is known. (Any lower bound will work.)